Even Walk in Tree

You are given a tree with \( n \) nodes numbered \( 1, 2, \ldots, n \). A walk on this tree is defined as follows: starting from any vertex \( u \), at each step you can move to an adjacent vertex. A walk is considered valid if it stops after an even number of steps (note that 0 steps is allowed).

Your task is to compute, for every vertex \( u \) as the starting point, the number of vertices \( v \) such that there exists a walk from \( u \) to \( v \) that is exactly of even length. Note that vertices (and even edges) may be revisited during the walk.

Hint: In a tree, any walk with an even number of steps from \( u \) to \( v \) exists if and only if the parity of the unique simple path between \( u \) and \( v \) is even. By performing a bipartite (2-color) partition of the tree, you can determine for any vertex \( u \) with a given color how many vertices share the same color.

Let \( count_0 \) be the total number of vertices colored 0 and \( count_1 \) be the total number of vertices colored 1. Then for each vertex \( u \), if its color is 0 the answer is \( count_0 \) and if the color is 1 then the answer is \( count_1 \).

inputFormat

The first line contains an integer \( n \) (\( 1 \leq n \leq 10^5 \)) representing the number of vertices in the tree. The next \( n-1 \) lines each contain two integers \( u \) and \( v \) (\( 1 \leq u,v \leq n \)), denoting an undirected edge between vertices \( u \) and \( v \).

outputFormat

Output \( n \) space-separated integers. The \( i\)-th integer should be the number of vertices that can be the endpoint of a walk starting from vertex \( i \) with an even number of steps.

sample

1

1