Bài toán

Cho một cây gồm ~ n ~ đỉnh. Nhiệm vụ của bạn là tìm một centroid của cây. Centroid là một đỉnh sao cho khi chọn nó làm gốc, kích thước của mỗi cây con không vượt quá ~ \lfloor n / 2 \rfloor ~.

Đầu vào

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng đỉnh trong cây (~ 1 \leq n \leq 2 \cdot 10^5 ~).
• Tiếp theo là ~ n-1 ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: biểu diễn một cạnh giữa hai đỉnh ~ a ~ và ~ b ~.

Đầu ra

• In ra một số nguyên: một đỉnh là centroid của cây. Nếu có nhiều centroid, chọn một đỉnh bất kỳ.

Ví dụ

Input:

5
1 2
2 3
3 4
3 5

Output:

3

Giải thích:

• Kích thước cây con:
  • ~ \text{subtree}[1] = 5 ~, ~ \text{subtree}[2] = 4 ~, ~ \text{subtree}[3] = 5 ~, ~ \text{subtree}[4] = 1 ~, ~ \text{subtree}[5] = 1 ~.
• Centroid là đỉnh ~ 3 ~ vì tất cả các cây con của nó không vượt quá ~ n/2 = 2 ~.