Subtree Node Count by Parity

Given a tree with n nodes, where the tree is rooted at node 1, compute the value for each node as follows:

For node i, let its value be the number of nodes in its subtree whose parity (odd or even) is the same as i.

A subtree of a node includes the node itself and all its descendants.

Output the values of the nodes in increasing order of node number.

The formulas used are defined in LaTeX as follows:

\(\text{Value}(i)=\#\{j \in \text{subtree}(i) : (j \bmod 2)=(i \bmod 2)\}\)

inputFormat

The first line contains a single integer n (number of nodes).

Each of the following n-1 lines contains two space-separated integers u and v, indicating there is an edge between nodes u and v.

outputFormat

Output a single line with n space-separated integers. The i-th integer is the computed value for node i.

sample

5
1 2
1 3
2 4
2 5

3 3 1 1 1