問題
$N$頂点$N-1$辺の連結なグラフ(木)が与えられます。
辺$i$は頂点$U_i$と頂点$V_i$をつないでいます。
頂点$x$から頂点$y$への最短距離を出力し、具体的な経路を1つ出力してください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $x$ $y$
$U_1$ $V_1$
$U_2$ $V_2$
...
$U_{N-1}$ $V_{N-1}$
出力
1行目に頂点$x$から頂点$y$への最短距離を、2行目からは具体的な最短経路上の頂点を改行区切りで出力してください。 出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 50000$
- $1 \leq x,y,U_i,V_i \leq 50000 (1 \leq i \leq N-1)$
- グラフは連結であり、多重辺や自己ループを含まない。
- 入力はすべて整数
- $x≠y$
入出力例
入力例1
4 1 4 1 2 2 3 3 4
出力例1
3 1 2 3 4
頂点1から頂点4への最短距離は3です。最短経路は1→2→3→4なので、この順に改行区切りで出力してください。
入力例2
5 2 5 1 2 1 3 1 4 1 5
出力例2
2 2 1 5
最短距離は2、最短経路は2→1→5なのでこの出力になります。