In the first line of the standard input there is a single integer N(2<=N<=500000) , denoting the number of intersections in Byteburg. Each of the following N-1 lines holds a pair of distinct integers Ai and Bi(1<=Ai,Bi<=N) separated by a single space, that represent the street linking the intersections no. Ai and Bi.