You are given a tree consisting of n nodes.
Your task is to determine for each node the sum of the distances from the node to all other nodes.
The first line contains an integer n(1≤n≤2⋅105): the number of nodes. The nodes are numbered 1,2,...,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b(1≤a,b≤n): there is an edge between nodes a and b.
Print n integers: for each node 1,2,...,n, the sum of the distances.