Tìm đường kính và tâm cây (Tree Diameter & Center) bằng 2 lượt BFS

Mục tiêu kiến thức

• Hiểu định nghĩa Đường kính cây (Tree Diameter): Độ dài đường đi đơn dài nhất giữa hai đỉnh bất kỳ trên cây.
• Thuật toán 2 lượt BFS/DFS:
• Lượt 1: BFS từ đỉnh bất kỳ tìm đỉnh xa nhất A.
• Lượt 2: BFS từ A tìm đỉnh xa nhất B. Đoạn nối từ A đến B là đường kính cây.
• Tâm cây (Tree Center): Đỉnh nằm chính giữa đường kính cây, giúp cực tiểu hóa khoảng cách lớn nhất tới các đỉnh khác.

Mô tả bài toán

Cho một cây gồm N đỉnh (1 ≤ N ≤ 2 · 10⁵) được đánh số từ 1 đến N. Hãy tìm:

• Độ dài đường kính cây (số lượng cạnh).
• Số hiệu đỉnh tâm của cây (nút nằm chính giữa đường kính). Nếu đường kính có 2 tâm (độ dài đường kính là số lẻ), in ra đỉnh tâm có số hiệu nhỏ hơn.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 2 · 10⁵.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.