Có ~N~ trạm căn cứ được thiết lập, giữa các trạm căn cứ có đường đi bí mật để di chuyển qua lại. Độ dài đường đi giữa các trạm là tương đương nhau, không có đường vòng để di chuyển giữa các trạm mà chỉ có thể đi và về trên một đường. Quy ước quãng đường giữa hai trạm kề nhau là ~1~.

Yêu cầu: Hãy tính tổng đường đi từ mỗi trạm căn cứ đến mọi trạm còn lại trên bản đồ.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ (~1 < N \le 10^5~).
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ (~1 \le x, y \le N, x \ne y~) thể hiện cho một con đường kết nối hai trạm ~x~ và ~y~. Mỗi cặp số nguyên ~x, y~ chỉ xuất hiện một lần.

Output

• Gồm ~N~ dòng, dòng thứ ~i~ (~1 \le i \le N~) là tổng đường đi từ trạm ~i~ đến mọi trạm còn lại trên bản đồ.

Sample Input 1

6
1 2
1 3
2 4
2 5
5 6

Sample Output 1

9
7
13
11
9
13