某天小 Q 發現自己在一棵陌生的樹上醒來,身為 APCSC 的學員小 Q 馬上發現這棵樹總共有 N 個節點。但是,在某個節點上有一隻飢餓的獅子(對沒錯,懂圖論的獅子也會爬樹),獅子也發現了小 Q,並且以最短的路徑朝小 Q 前進。已知小 Q 與獅子每單位時間內都只能跳到相鄰的節點上,且小 Q 會選最慢才被獅子追上的逃生路線。每單位時間中會是小 Q 先移動,獅子再移動。請你寫個程式計算獅子最快需要移動多少步數才能抓到小 Q ?
輸入的第一行有三個以空個分隔的數字 N,u,v,分別代表樹的節點數 N(2≤N≤105)、小 Q 的初始節點編號、獅子的初始節點編號(1≤u,v≤N 且 u≠v)。樹的節點編號是從 1 到 N。
接下來會有 N−1 行,每行有兩個以空個分隔的數字 ai,bi(1≤ai,bi≤N),表示編號 ai 的節點與編號 bi 的節點之間有邊,即小 Q 與獅子可以在 ai,bi 之間跳躍。
輸出一個整數 t,表示獅子需要移動的最少步數。
AtCoder