Nguồn:
Mr Kiên
Cho một
đơn đồ thị liên thông gồm N đỉnh và N-1 cạnh. Mỗi cạnh có độ
dài bằng 1. Ta nói đây là một cây không trọng số.
Đường
kính của cây là khoảng cách giữa hai đỉnh xa nhau nhất. Tâm của cây là đỉnh mà
có khoảng cách từ nó tới nút xa nó nhất là nhỏ nhất. Một cây có thể có nhiều
tâm.
Hãy
tìm đường kính của cây và các tâm của cây.
Dữ liệu vào: Từ tệp văn bản BFS2.INP
+ Dòng
đầu tiên chứa số nguyên dương N (1≤N≤105)
+ N-1
dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x và y chỉ một cạnh nối giữa
hai đỉnh x và y trên cây.
Dữ liệu ra: Ghi vào tệp văn bản BFS2.OUT
+ Dòng
đầu tiên, in ra đường kính của cây.
+ Dòng
thứ hai, in ra số lượng tâm của cây.
+ Dòng
thứ ba, in ra các đỉnh là tâm của cây theo thứ tự tăng dần. Các số cách nhau bởi
1 dấu cách.
Ví dụ:
|
BFS2.INP
|
BFS2.OUT
|
|
5
1 2
2 3
3 4
2 5
|
4
2
2 3
|
