Có $N$ chú sóc đang cất giữ hạt dẻ trên một cái cây. Cây này cũng là một cây theo lý thuyết đồ thị: một đồ thị liên thông với $N$ đỉnh được đánh số từ $1$ đến $N$ và $N - 1$ cạnh vô hướng. Mỗi chú sóc ngồi tại một đỉnh khác nhau của cây và hai chú sóc được coi là hàng xóm nếu các đỉnh của chúng có chung một cạnh.

Theo thứ tự tăng dần của nhãn đỉnh bắt đầu từ chú sóc ở đỉnh $1$, mỗi chú sóc sẽ lấy trộm một hạt dẻ từ mỗi chú sóc hàng xóm hiện đang có nhiều hạt dẻ nhất. Nếu có nhiều hàng xóm cùng có số lượng hạt dẻ nhiều nhất, chú sóc đó sẽ lấy trộm một hạt dẻ từ mỗi người trong số họ!

Để hạn chế hậu quả của những trò nghịch ngợm này, bạn muốn phân phát hạt dẻ cho các chú sóc sao cho mỗi chú sóc bắt đầu với ít nhất $N$ hạt dẻ (để không chú sóc nào bị hết hạt dẻ do bị lấy trộm) và kết thúc với cùng số lượng hạt dẻ như ban đầu sau khi tất cả $N$ chú sóc đã thực hiện xong việc lấy trộm lẫn nhau. Có thể chứng minh rằng tồn tại một cách phân phát như vậy, trong đó mỗi chú sóc bắt đầu với tối đa $2N - 1$ hạt dẻ. Hãy tìm bất kỳ cách phân phát nào thỏa mãn các điều kiện này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $N$ ($2 \le N \le 10^5$), số lượng đỉnh (và số lượng sóc).

Mỗi dòng trong số $N - 1$ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách $u$ và $v$ ($1 \le u, v \le N, u \neq v$), biểu thị rằng có một cạnh tồn tại giữa đỉnh $u$ và đỉnh $v$. Có tối đa một cạnh giữa bất kỳ cặp đỉnh nào và các cạnh tạo thành một cây.

Dữ liệu ra

In ra $N$ số nguyên cách nhau bởi dấu cách $d_1, d_2, \dots, d_N$ thỏa mãn $N \le d_i \le 2N - 1$, trong đó $d_i$ là số lượng hạt dẻ bạn muốn phân phát cho chú sóc ở đỉnh $i$. Giải pháp của bạn sẽ được chấp nhận nếu mọi chú sóc đều kết thúc với cùng số lượng hạt dẻ như khi chúng bắt đầu sau khi tất cả $N$ vụ trộm đã xảy ra. Có thể chứng minh rằng một cách phân phát hạt dẻ như vậy luôn tồn tại.

Ví dụ