Mô tả và yêu cầu

ĐƯỜNG ĐI BFS
Cho đ thị có hướ ng 𿿿 = (򟿿, ) gồm đỉ nh và cung, ݏ và ݐ là hai đỉ nh c ủa . M ột dãy các
đỉ nh 񯿿 = 〈ݏ = ݌0, ݌1, … , ݌󿿿 = ݐ〉 sao cho ( ݌󏿿−1, ݌󏿿) ∈ , ∀󏿿: 1 ≤ 󏿿 ≤ 󿿿 đượ c g ọi là m ột đườ ng
đi từ t ới .

Biết rằng t ồn t ại ít nh ất một đường đi từ t ới , hãy ch ỉ ra đường đi đơn qua ít cung
nhất. N ếu có nhiều đường đi đơn cùng qua ít cung nhấ t, hãy ch ỉ ra đường đi có thứ
tự t ừ điển nh ỏ nh ất trong s ố đó.

Dữ li ệu: Vào t ừ file văn bả n BFS.INP
 Dòng 1 ch ứa s ố đỉ nh ݊ ≤ 10 5, s ố cung ݉ ≤ 10 6, đỉ nh xu ất phát , đỉ nh c ần đế n .
 dòng ti ếp theo, m ỗi dòng ch ứa hai s ố nguyên dương ݑ, ݒ thể hi ện có cung n ối từ
đỉnh t ới đỉnh trong đồ thị.

Kết quả: Ghi ra trên m ột dòng c ủa file văn bản BFS.OUT các đỉnh theo đúng thứ tự trên
đường đi tìm đượ c, b ắt đầ u t ừ đỉ nh , k ết thúc ở đỉ nh

Các s ố trên m ột dòng c ủa Input/Output files đượ c/phải ghi cách nhau ít nh ất một dấu
cách

Ví dụ

BFS.INP            BFS.OUT
                                        8 12 1 8           1 3 7 8                                             1
                                        1 2
                                        1 3                                                         2                     3
                                        2 3
                                        2 4                                                         4          7          5
                                        3 1
                                        3 5                                                         6          8
                                        3 7
                                        4 6
                                        6 2
                                        6 8
                                        7 8
                                        7 6