Tên trộm OBI thâm nhập vào trung tâm điều khiển của thị trấn A. Trung tâm điều khiển này có dạng một đồ thị ~N~ đỉnh vô hướng liên thông không có chu trình. Mỗi đỉnh tương ứng là một phòng và các cạnh là đường hầm nối hai phòng đó. Những phòng chỉ có duy nhất một đường hầm nối với nó sẽ có một lối ra (vào), được coi là nút lá trên đồ thị.

Biết có tên trộm đột nhập, giám đốc trung tâm điều khiển điều động các lính canh tại các lối thoát hiểm nhằm truy bắt tên trộm. Tên trộm cố gắng di chuyển ra một nút lá nào đó để thoát thân; các lính canh cố gắng di chuyển để chặn được tên trộm.

Yêu cầu: Với mỗi phòng từ ~1~ đến ~N~, nếu tên trộm di chuyển ra phòng ~i~ thì cần tối thiểu bao nhiêu tên lính để chặn đứng tên trộm. Giả sử tên trộm và các lính canh đều di chuyển tối ưu: tên trộm di chuyển tối ưu để cực tiểu hóa số tên lính mình phải đối đầu, còn lính canh luôn di chuyển về phía tên trộm. Mỗi một bước di chuyển sẽ đi qua được một cạnh. Các lính canh sẽ được đi vào qua các nút lá.

Input

• Dòng đầu chứa số nguyên ~N~ ~(N \le 7 \cdot 10^4)~;

• ~N-1~ dòng sau, mỗi dòng chứa hai số nguyên ~u, v~ thể hiện có đường hầm nối giữa hai phòng ~u~ và ~v~ ~(u, v \le N)~.

Output

Ghi ra ~N~ dòng, dòng thứ ~i~ là số tên lính tối thiểu cần để chặn đứng tên trộm nếu hắn di chuyển ra phòng thứ ~i~.

Scoring

Sample Input 1

6
1 2
1 3
2 4
3 5
5 6

Sample Output 1

2
2
2
1
2
1