You are given a tree with N nodes and N-1 edges. The tree is rooted at the node 1. Each edge has a strength associated with it.
For an edge i, the strength of the edge is determined as follows:
Find the strength of each edge in the tree.
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≤N≤105
1≤x,y≤N;x!=y
In the 1st case if we remove the 4th edge (1-5) then the node pairs which are not connected are (5,1),(5,2),(5,3),(5,4),(6,1),(6,2),(6,3),(6,4). Hence there are 8 pairs.