\text{Phân tách cây}

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

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Sau khi tìm được trọng tâm, nhà thám hiểm Tèo muốn xây dựng Centroid Tree - một cấu trúc dạng cây mới từ cây ban đầu. Quy tắc xây dựng như sau:

• Tìm centroid của cây hiện tại, đặt nó làm gốc.
• Loại bỏ centroid, tiếp tục xây dựng trên từng thành phần còn lại.
• Centroid của thành phần con sẽ có cha là centroid của cây cha.

Yêu cầu: Cho một cây \(N\) đỉnh, hãy xác định cha của mỗi đỉnh trong Centroid Tree. Với đỉnh gốc (không có cha), in ra \(-1\).

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\).

Đầu ra

• In ra \(N\) số, số thứ \(i\) là cha của đỉnh \(i\) trong Centroid Tree (hoặc \(-1\) nếu là gốc).

Ví dụ

Đầu vào:

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

Đầu ra:

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

Giải thích

Centroid tree có gốc là 1. Con của 1 là 2 và 3. Lá là 4,5,6,7 (cha tương ứng 2,2,3,3).

Subtask