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:

• Delete the edge i from the tree.
• Count the number of unordered pairs of nodes that are no longer connected. The number of pairs is the strength of the edge.

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\le N \le 10^5 \)
\( 1 \le x,y \le N; x!=y\)