Count Greater Nodes in Subtree

Given a rooted tree with \( n \) nodes numbered from \( 1 \) to \( n \) and \( n-1 \) edges, the tree is rooted at node \( 1 \). For each node \( i \), your task is to determine the number of nodes in its subtree (including \( i \) itself) that have a value greater than \( i \). The subtree of a node is defined as the node and all of its descendants in the tree.

Note: It is guaranteed that the given graph is a tree. Use depth-first search (DFS) or any other tree traversal strategy to solve the problem.

Example:

Input:
5
1 2
1 3
3 4
3 5
Output:
4 0 2 0 0

</p>

The output for node 1 is \(4\) because in its subtree \( \{1,2,3,4,5\} \), the nodes \(2, 3, 4, 5\) are greater than \(1\); and similarly for the other nodes.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \( n \), the number of nodes.
• The next \( n-1 \) lines each contain two integers \( u \) and \( v \), representing an edge between nodes \( u \) and \( v \).

outputFormat

Output a single line on standard output (stdout) containing \( n \) space-separated integers. The \( i \)-th integer denotes the number of nodes in the subtree of node \( i \) (with the tree rooted at 1) that have a value greater than \( i \).

## sample

5
1 2
1 3
3 4
3 5

4 0 2 0 0