Quân tìm trọ

Quân là một sinh viên tỉnh lẻ vừa chuyển lên thành phố nhập học. Để tiện giao lưu bạn bè và sinh hoạt chung, nhóm bạn của Quân đã quyết định thuê trọ quanh một khu vực có nhiều dãy phòng kết nối với nhau như một hệ thống nơi mỗi phòng có đường đi đến nhau – về bản chất là một đồ thị cây với \(n\) phòng trọ.

Quân không thích ở quá đông một nhóm bạn nào — dễ mất riêng tư, mà cũng không muốn ở quá xa tất cả — sẽ cảm thấy cô lập. Cậu muốn tìm một vị trí ở cân bằng, sao cho nếu xem vị trí đó là trung tâm và tạm loại bỏ nó khỏi hệ thống, thì không có cụm bạn bè nào còn lại quá đông người.

Nói cách khác, Quân muốn chọn một phòng sao cho nếu loại bỏ nó, thì mọi nhóm phòng còn lại (mỗi thành phần liên thông còn lại) đều có không quá \(\lfloor n/2 \rfloor\) phòng.

Yêu cầu: Hãy giúp Quân tìm ra chỉ số của phòng trọ theo sở thích của Quân. Nếu có nhiều phòng thỏa mãn, hãy in ra phòng có chỉ số nhỏ nhất.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) — số lượng phòng trọ (\(1 \le n \le 2 \cdot 10^5\)).
• Sau đó là \(n - 1\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n\)) mô tả một lối đi giữa hai phòng \(a\) và \(b\).

Output

In ra một số nguyên — chỉ số của phòng trọ thỏa mãn (nhỏ nhất nếu có nhiều phòng thỏa mãn).

Scoring

• Subtask 1: \(n \le 5000\).
• Subtask 2: Không có ràng buộc nào thêm.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2

Notes

Cả phòng \(2\) và phòng \(3\) đều thỏa mãn; phòng \(2\) có chỉ số nhỏ hơn.