Cuối cùng cũng bị dồn vào đường cùng, Bessie đã lẩn trốn trong một trang trại hẻo lánh. Trang trại gồm \(N\) chuồng bò (\(2 \leq N \leq 7 \cdot 10^4\)) và \(N-1\) đường hầm hai chiều nối các chuồng, sao cho giữa mọi cặp chuồng đều có một đường đi duy nhất. Mỗi chuồng có đúng một đường hầm nối với nó đều là một lối thoát. Khi trời sáng, Bessie sẽ xuất hiện tại một chuồng nào đó và cố gắng đi đến một lối thoát.

Nhưng ngay khi Bessie xuất hiện tại một chuồng nào đó, lực lượng hành pháp sẽ có thể xác định chính xác vị trí của cô. Khi đó, một số nông dân sẽ bắt đầu từ các chuồng là lối thoát và cố gắng bắt Bessie. Những người nông dân di chuyển với cùng tốc độ như Bessie (vì vậy trong mỗi bước thời gian, mỗi nông dân có thể đi từ một chuồng sang một chuồng kề nó). Những người nông dân luôn biết Bessie ở đâu, và Bessie cũng luôn biết họ ở đâu. Những người nông dân bắt được Bessie nếu tại bất kỳ thời điểm nào có một nông dân ở cùng chuồng với Bessie hoặc đang đi qua cùng một đường hầm với Bessie. Ngược lại, Bessie trốn thoát nếu thời điểm cô đến được một chuồng là lối thoát sớm hơn nghiêm ngặt so với thời điểm bất kỳ nông dân nào bắt được cô.

Bessie không chắc mình nên xuất hiện tại chuồng nào. Với mỗi chuồng trong số \(N\) chuồng, hãy giúp cô xác định số nông dân ít nhất cần có để bắt được cô nếu cô xuất hiện tại đó, giả sử những người nông dân phân bố tối ưu giữa các chuồng là lối thoát.

Lưu ý rằng giới hạn thời gian của bài này lớn hơn mặc định một chút: \(4\) giây đối với C/C++/Pascal và \(8\) giây đối với Java/Python.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên, mỗi số thuộc khoảng \(1 \ldots N\), mô tả một đường hầm nối hai chuồng.

Dữ liệu ra

In ra \(N\) dòng, trong đó dòng thứ \(i\) cho biết số nông dân ít nhất cần có để bắt Bessie nếu cô xuất hiện tại chuồng thứ \(i\).

Ví dụ

7
1 2
1 3
3 4
3 5
4 6
5 7

3
1
3
3
3
1
1

Nguồn

USACO 2018 January Contest, Platinum — Cow at Large

Tác giả bài toán: Dhruv Rohatgi.