Subtree Sum in a Tree

You are given a tree with n nodes, where the root of the tree is node 1. Each node has a weight of 1. Your task is to compute for each node i the sum of weights in its subtree (i.e. the number of nodes in the subtree rooted at i).

The tree is given as an undirected graph with n nodes and n-1 edges, and it is guaranteed to form a valid tree. The input edges do not necessarily follow the parent-to-child order. Use the fact that node 1 is the root to construct the tree and compute the answer.

The answer for each node should be output in a single line separated by spaces (i.e. the subtree sums for nodes 1 through n).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10^5), the number of nodes in the tree.

Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) representing an edge between nodes u and v.

outputFormat

Output a single line containing n integers separated by spaces, where the i-th integer is the sum of the subtree rooted at node i.

sample

1

1