Tìm Centroid của cây

Trong lý thuyết đồ thị, Centroid (trọng tâm) của một cây là một nút đặc biệt. Một cây có thể có một hoặc hai centroid. Với mỗi nút \(u\) trong cây, ta xét tất cả các cây con khi loại bỏ nút \(u\). Centroid của cây là một nút \(c\) sao cho kích thước của cây con lớn nhất khi bỏ \(c\) là nhỏ nhất. Một cách định nghĩa khác, nếu ta chọn \(c\) làm gốc, kích thước của mọi cây con (được tạo bởi các nhánh nối với \(c\)) không vượt quá một nửa tổng số nút của cây. Thuật toán tìm centroid thường sử dụng phương pháp duyệt cây (DFS) để tính kích thước cây con và sau đó tìm nút thỏa mãn điều kiện.

Bạn được cho một cây vô hướng với \(n\) nút. Nhiệm vụ của bạn là tìm một trọng tâm (centroid) của cây. Một nút \(c\) được gọi là trọng tâm nếu khi ta loại bỏ nó, kích thước của mỗi cây con còn lại không vượt quá \(\lfloor n/2 \rfloor\).

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số nút của cây. Các nút được đánh số từ \(1\) đến \(n\).
• \(n-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n\)), biểu thị có một cạnh nối giữa nút \(a\) và nút \(b\).

Output

In ra một số nguyên duy nhất là chỉ số của một nút trọng tâm. Nếu có nhiều hơn một nút thỏa mãn, bạn có thể in ra bất kỳ nút nào trong số đó.

Example

5
1 2
2 3
3 4
3 5

3