The first line of the standard input contains a single integer N(1<=N<=1000000) that denotes the number of stations. These are numbered from 1 to n . The following n -1 lines specify the track segments, one per line. Each of them holds two integers a,b(1<=A,B<=N,A<>B), separated by a single space, indicating that there is a track segment connecting the stations a and b. Each track segments appears exactly once in the description.
In tests worth at least 30% of the points it holds additionally that n<=2000.