Gia tộc họ Nguyễn có \(N\) thành viên, được đánh số từ 1 đến N. Mối quan hệ cha-con giữa các thành viên được biểu diễn bằng một cây phả hệ, trong đó thành viên \(1\) là tổ tiên chung (gốc của cây).

Với mỗi thành viên \(u\), hãy đếm số lượng thành viên trong nhánh của u (tức là số người thuộc hậu duệ của u, tính cả \(u\)).

\(|1| \le 20\) | 10 | \(|2| \le 5000\) | 20 | \(|3| \le 2 \cdot 10^5\) | 30 | \(|4| \le 2 \cdot 10^5\) | 40 |

Đầu vào:

• Dòng đầu gồm số nguyên \(N\). - N - \(1\) dòng sau, mỗi dòng gồm hai số \(u, v\) mô tả một mối quan hệ cha-con (cạnh của cây).

Đầu ra:

• In ra \(N\) số nguyên, số thứ u là kích thước nhánh của thành viên \(u\).

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\) mô tả mối quan hệ cha-con với gốc tại đỉnh 1.

Định dạng đầu ra

• \(N\) số nguyên trên một dòng, số thứ i là kích thước cây con gốc \(i\) (kể cả chính nó).

Ví dụ

Input:

4
1 2
1 3
3 4

Output:

4 1 2 1

Giải thích: Cây con gốc 1 có 4 đỉnh, gốc 2 có 1 đỉnh, gốc 3 có 2 đỉnh, gốc 4 có 1 đỉnh.

Ràng buộc & Subtasks