Calculate Subtree Sizes for a Tree

You are given an undirected tree with n nodes. The tree is provided as a list of n-1 edges. Consider the tree to be rooted at node 1. Your task is to compute the size of the subtree for every node. The subtree of a node is defined as the node itself along with all of its descendants.

Formally, for each node i (\(1 \le i \le n\)), you should find the number of nodes in the subtree rooted at i. Use a Depth-First Search (DFS) or any tree traversal technique to accomplish the task.

Note: The input guarantees a tree structure (i.e. a connected and acyclic graph).

inputFormat

The input is given via stdin and has the following format:

n
u1 v1
...
un-1 vn-1

Here, n is an integer representing the number of nodes. Each of the following n-1 lines contains two integers u and v, indicating that there is an edge between nodes u and v.

outputFormat

Output to stdout a single line containing n space‐separated integers. The i-th integer should represent the size of the subtree rooted at node i (with the tree rooted at node 1).

5
1 2
1 3
3 4
3 5

5 1 3 1 1