TopCoder

abcabcabc

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Description

某天小 Q 發現自己在一棵陌生的樹上醒來，身為 APCSC 的學員小 Q 馬上發現這棵樹總共有 $N$ 個節點。但是，在某個節點上有一隻飢餓的獅子（對沒錯，懂圖論的獅子也會爬樹），獅子也發現了小 Q，並且以最短的路徑朝小 Q 前進。已知小 Q 與獅子每單位時間內都只能跳到相鄰的節點上，且小 Q 會選最慢才被獅子追上的逃生路線。每單位時間中會是小 Q 先移動，獅子再移動。請你寫個程式計算獅子最快需要移動多少步數才能抓到小 Q ？

Input Format

輸入的第一行有三個以空個分隔的數字 $N, u, v$，分別代表樹的節點數 $N$（$2\le N \le 10^ 5$）、小 Q 的初始節點編號、獅子的初始節點編號（$1\le u,v \le N$ 且 $u \ne v$）。樹的節點編號是從 $1$ 到 $N$。

接下來會有 $N-1$ 行，每行有兩個以空個分隔的數字 $a_i, b_i$（$1\le a_i,b_i \le N$），表示編號 $a_i$ 的節點與編號 $b_i$ 的節點之間有邊，即小 Q 與獅子可以在 $a_i, b_i$ 之間跳躍。

Output Format

輸出一個整數 $t$，表示獅子需要移動的最少步數。

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

Hints

Problem Source

AtCoder

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~17	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2

773 . 會爬樹的獅子