問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
木を構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ辺の情報と頂点番号 X が与えられるので、頂点 X からの距離が 3 である頂点の番号を全て出力してください。
なお、木の 2 頂点 X, Y 間の距離とは、頂点 X から頂点 Y までを最短経路で移動したときに通る辺の数のことを指します。
--- ヒント ---
頂点 X から実際に 3 回移動するシミュレーションをしても良いですが、このような問題についても幅優先探索が利用できます。
グリッドにおける幅優先探索において、「3 マス移動することで新たに行けるようになるマス」を
「2 マス移動することで新たに到達できるようになったマス」から新たな移動を行うことで求めた手法を木でも同様に用いてみましょう。
具体的には「頂点 X からの距離が 3 である頂点」を「『頂点 X からの距離が 2 である頂点』に隣接している頂点のうち、未訪問の頂点」であると考えてみましょう。
N X
a_1 b_1
...
a_{N-1} b_{N-1}
・頂点 X からの距離が 3 である頂点の番号を、番号が昇順となるように改行区切りで全て出力してください。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100,000
・1 ≦ X ≦ N
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ N-1)
・a_i ≠ b_i (1 ≦ i ≦ N-1)
5 1
1 2
2 3
3 4
4 5
4
7 7
7 5
5 6
1 5
1 4
1 2
1 3
2
3
4