Monk is given a tree rooted at node 1.The tree has N nodes and $N-1$ edges. Each edge has some strength associated with it. The strength of an edge is determined by the number of pair of nodes which are connected with the help of that particular edge.

Alternatively consider all the paths between every pair of nodes and the strength of an edge will be equal to the number of paths in which that edge comes.

Monk wants to know the strength of each edge of the tree.

Note: Node pair (i,j) is same as node pair (j,i).

Input Format
First line consists of an integer N denoting the number of nodes in the tree. Then there are 2 integers N-1 and 2.
Then $N-1$ lines follow. Each line consists of two integers x and y denoting there is an edge between vertex x and vertex y.

Output Format

Output strength of each edge in a separate line. The order of edges in the output should be the same as that in the input.

Constraints

$1\le N \le 10^5$
$1 \le x,y \le N; x!=y$