Định nghĩa:

Tree (Cây): Là đồ thị vô hướng liên thông và không có chu trình.

Distance of two nodes (khoảng cách giữa hai đỉnh): là đường đi ngắn nhất giữa hai đỉnh đó trên cây.

Centroid of a tree: là đỉnh mà khi ta lấy nó làm gốc của cây, thì tất cả các nhánh cây con đều có kích thước (số lượng đỉnh) không quá \(\lfloor\frac{N}{2}\rfloor\), với \(N\) là số đỉnh của cây ban đầu.

Diameter of a tree (đường kính): là khoảng cách lớn nhất có thể giữa hai đỉnh bất kỳ trên cây.

Cho một cây gồm \(N\ (1\leq N\leq2\times10^5)\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(N\). Yêu cầu xác định centroid và diameter của nó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\);
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u,\ v\) thể hiện có cạnh nối giữa hai đỉnh đó.

Dữ liệu đảm bảo đồ thị được nhập vào là một cây.

Output

• In ra hai số nguyên dương \(c\) và \(d\), lần lượt là centroid và diameter của cây.

Ví dụ

Sample input

6
1 3
2 4
3 4
3 5
5 6

Sample output

3 4