Tý cần giải bài toán sau:

\text{Tìm trọng tâm}

Đị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

Trong khu rừng già FPTOJ có \(N\) cái cây được nối với nhau bởi \(N-1\) con đường, tạo thành một mạng lưới liên thông. Các nhà thám hiểm muốn tìm một vị trí đặt trạm cứu hộ sao cho khi trạm này gặp sự cố và phải đóng cửa, mỗi khu vực còn lại đều không quá \(N/2\) cây.

Vị trí đặc biệt đó được gọi là trọng tâm (centroid) của khu rừng.

Yêu cầu: Cho một cây \(N\) đỉnh, hãy tìm một centroid bất kỳ của cây.

Đầ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\) (\(1 \le u, v \le N\)) mô tả một cạnh của cây.

Đầu ra

• In ra một số nguyên duy nhất là chỉ số của centroid tìm được.

Ví dụ

Đầu vào:

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

Đầu ra:

1

Giải thích

Centroid của cây là đỉnh 1. Khi loại bỏ đỉnh 1, hai thành phần (2,4,5) và (3,6,7) đều có kích thước \(3 \le \lfloor 7/2 \rfloor = 3\).

Subtask