Cho một cây \(n\) đỉnh có đỉnh gốc là \(1\). Với mỗi đỉnh \(i\), xác định số lượng đỉnh nằm trong cây con gốc \(i\).

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) có cạnh nối giữa \(u\) và \(v\).

Dữ liệu ra

• In ra \(n\) số nguyên, số nguyên thứ \(i\) là số lượng đỉnh trong cây con gốc \(i\).

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le u,v \le n\)

Input 1

5
1 2
1 3
3 4
3 5

Output 1

5 1 3 1 1