Description
Problem brought to you by NTHU Amusement Programming Club.
After being kicked out of NTHU due to lack of talents in programming, GY Lin had no choice but to start living in a tree (a connected, acyclic graph). If you fail this course, you will meet the same fate.
Knowing this, his friend and tutor Shepherd comes to visit GY. Unfortunately for him, GY is not at home, but he doesn’t realized this until he has already traversed every node. During that, he discovered something interesting: when he steps onto a node, the view may change dramatically.
The tree has N nodes, and nodes are numbered distinctly from 1 to N. The view from a node u can be quantified as a single integer val(u), which can be obtained using the following algorithm:
set root := u
set val(root) := 0
set boolean array vis[i]:=false for i=1...N
call dfs(root,0)
The dfs algorithm is defined as follows:
dfs(v, lv):
set vis[v] := true
val(root) := val(root) + lv
for any neighbor w of v
if vis[w]=false:
call dfs(w,lv+1)
Shepherd is now standing on node S, so he wants you to help him calculate val(S), for he doesn't have the computer right now.
Input
There is only one testcase per input file, each describing the structure of a tree.
On the first line, there two integers N S, the number of nodes and the node that Sheep is standing on; N−1 lines follow, each containing two integers u v, meaning there is an edge between node u and v.
1 <= N <= 2*105
Output
Output a single integer that is val(S).