Sau sáp nhập, tỉnh mới trở nên rộng lớn hơn với sự kết hợp giữa rừng và biển, các địa điểm tham quan cũng phong phú và đa dạng hơn, có những bãi biển trong xanh thơ mộng và cũng có những khu du lịch sinh thái mang bản sắc của núi rừng Tây Nguyên. Nhân dịp kỷ niệm 80 năm Quốc Khánh, nhà trường tổ chức cho các em học sinh giỏi môn Tin học đi tham quan các địa điểm du lịch đặc trưng của tỉnh nhà.

Ban tổ chức chọn được ~N~ địa điểm tham quan và đánh số từ ~1~ đến ~N~. Có ~N-1~ con đường hai chiều nối trực tiếp các địa điểm với nhau. Con đường thứ ~i~ nối hai địa điểm ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le N; u_i \ne v_i)~, các con đường này luôn đảm bảo sự đi lại giữa hai địa điểm tham quan bất kỳ.

Chuyến tham quan diễn ra trong ~N-1~ ngày, ngày thứ ~i~ đoàn tham quan xuất phát từ địa điểm ~i~ và kết thúc tại địa điểm ~i+1~, có thể đi qua các địa điểm trung gian khác sao cho lộ trình di chuyển là ngắn nhất. Mỗi ngày, đoàn tham quan di chuyển qua một địa điểm (tính cả địa điểm xuất phát và địa điểm kết thúc) sẽ được tặng một món quà lưu niệm đặc trưng của địa phương. Hỏi sau khi kết thúc chuyến tham quan, đoàn đã nhận được bao nhiêu món quà của từng địa điểm?

Yêu cầu: Tại mỗi địa điểm, hãy tính số lượng quà mà đoàn tham quan đã nhận được.

Input

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

• ~N-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i~ và ~v_i~ cách nhau một khoảng trắng thể hiện có con đường nối trực tiếp giữa hai điểm ~u_i~ và ~v_i~.

Output

Gồm ~N~ dòng, dòng thứ ~i~ ghi một số nguyên cho biết số lượng quà mà đoàn tham quan đã nhận được tại địa điểm thứ ~i~.

Scoring

Sample Input 1

5
5 4
2 5
1 3
5 1

Sample Output 1

3
2
2
2
4

Notes

Lộ trình tham quan trong ~4~ ngày:

• Ngày 1: ~1 \rightarrow 5 \rightarrow 2~

• Ngày 2: ~2 \rightarrow 5 \rightarrow 1 \rightarrow 3~

• Ngày 3: ~3 \rightarrow 1 \rightarrow 5 \rightarrow 4~

• Ngày 4: ~4 \rightarrow 5~