D - Takahashi Tour

Contest Duration: 2021-08-08(Sun) 12:00 - 2021-08-08(Sun) 13:40 (local time) (100 minutes) Back to Home

D - Takahashi Tour Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

AtCoder 国には $1$ から $N$ の番号がついた $N$ 個の都市と、 $1$ から $N-1$ の番号がついた $N-1$ 個の道路があります。
道路 $i$ を通ると都市 $A_i$ と都市 $B_i$ の間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。

高橋くんは都市 $1$ を出発し、次のルールで旅をします。

いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
そのような都市が存在しないとき
- いまいる都市が都市 $1$ なら旅を終了する
- そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する

高橋くんが旅の過程で訪れる都市を順に答えてください。

制約

$2 \leq N \leq 2\times 10^5$
$1\leq A_i,B_i \leq N$
全ての都市は道路を使って互いに行き来できる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $B_1$ 
 $\vdots$ 
 $A_{N-1}$   $B_{N-1}$

出力

高橋くんが訪れる都市を、旅の開始時及び終了時の都市 $1$ も含めて順に空白区切りで出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

1 2 4 2 1 3 1

高橋くんの旅は次のようになります。

最初都市 $1$ にいます。
都市 $1$ から道路で直接つながっている都市のうち未訪問なのは都市 $2,3$ です。番号が小さい都市 $2$ へ移動します。
都市 $2$ から道路で直接つながっている都市のうち未訪問なのは都市 $4$ です。都市 $4$ へ移動します。
都市 $4$ から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 $2$ へ移動します。
都市 $2$ から道路で直接つながっている都市のうち未訪問の都市はありません。初めて都市 $2$ に来る直前にいた都市 $1$ へ移動します。
都市 $1$ から道路で直接つながっている都市のうち未訪問なのは都市 $3$ です。都市 $3$ へ移動します。
都市 $3$ から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 $1$ へ移動します。
都市 $1$ から道路で直接つながっている都市のうち未訪問の都市はありません。旅を終了します。

入力例 2Copy

Copy

出力例 2Copy

Copy

1 2 1 3 1 4 1 5 1

Score : $400$ points

Problem Statement

The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $N-1$ roads numbered $1$ through $N-1$ . Road $i$ connects City $A_i$ and City $B_i$ bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.

Takahashi will depart City $1$ and have a journey by repeating the following.

If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
Otherwise,
- if he is in City $1$ , he ends the journey;
- otherwise, he goes to the city he was in just before visiting the current city for the first time.

Find the sequence of cities visited by Takahashi in the order he visits them.

Constraints

$2 \leq N \leq 2\times 10^5$
$1\leq A_i,B_i \leq N$
It is possible to travel between every pair of cities using roads.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $B_1$ 
 $\vdots$ 
 $A_{N-1}$   $B_{N-1}$

Output

Print the sequence of cities visited by Takahashi in the order he visits them, including City $1$ at the beginning and end of the journey, with spaces in between.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

1 2 4 2 1 3 1

His journey will be as follows.

Start in City $1$ .
The unvisited cities directly connected to City $1$ are City $2$ and $3$ . Go to the city with the smaller number, that is, City $2$ .
The unvisited city directly connected to City $2$ is City $4$ . Go there.
There is no unvisited city directly connected to City $4$ . Go back to City $2$ .
There is no unvisited city directly connected to City $2$ . Go to City $1$ , where he was in just before visiting City $2$ for the first time.
The unvisited city directly connected to City $1$ is City $3$ . Go there.
There is no unvisited city directly connected to City $3$ . Go back to City $1$ .
There is no unvisited city directly connected to City $1$ . End the journey.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

1 2 1 3 1 4 1 5 1