As you might be knowing, Vijay is the favourite student of his teachers. So, today his algorithms course instructor has given him a task. But today he is going on date with his girlfriend, so he will not be able to give time for the task. You being his best friend, should help him in this situation. The task is as follows:
You are given a rooted tree. Weights of all the edges in tree are 1. Now we define a value mysteryValue for each node in the tree as, the sum of distances of all other nodes from that node (i.e. sum of path lengths). Now you have to calculate the mysteryValue for each node in the tree.

INPUT:
First line of input contains an integer n.
$1\leq n \leq 1000000$
Next $n-1$ lines follow.
Each line contains two integers i and j.
$1 \leq i, j \leq n$ ($i \neq j$) such that there is an edge from i to j in the tree.

Node 1 is always the root of the tree.

OUTPUT:
Print n integers, where $K^{th}$ value is mysteryValue for node K.