Description

第一行是一个整数N（1≤N ≤50000），表示计算机的台数，计算机被编号为1..N。 下面N-1行，每行包括两个整数X, Y，表示X和Y这两台计算机之间由一条网线连接。 1号点为根

Format

Input

第一行给出数字N

接下来N-1行描述这个树

Output

给出N行，分别表示从1号到N号点，以之为根的子树有多少个点，将结果-1后再输出

Samples

3
1 2
1 3

2
0
0