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

ĐƯỜNG ĐI DFS
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 . Một đường đi gọ i là đơn giả n (hay đường đi đơn ) nếu t ất cả các đỉnh
trên đường đi là hoàn toàn phân bi ệt.

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 có thứ tự t ừ
điển nhỏ nhất.

Dữ li ệu: Vào t ừ file văn bả n DFS.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 DFS .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ụ

DFS.INP            DFS.OUT
                                     8 12 1 8           1 2 3 7 6 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