Cho một đồ thị vô hướng liên thông không có chu trình (cây) với đỉnh.
Với một tập con gồm 3 đỉnh phân biệt , ta định nghĩa là đồ thị con liên thông nhỏ nhất của chứa tất cả các đỉnh trong . Tính chất "nhỏ nhất" ở đây được hiểu là đồ thị con có số lượng cạnh ít nhất.
Nhiệm vụ của bạn là tìm một tập gồm 3 đỉnh phân biệt sao cho số lượng cạnh của đồ thị con là lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên () — số lượng đỉnh của cây.
dòng tiếp theo mô tả các cạnh của cây dưới dạng (). Đảm bảo rằng đồ thị cho trước là một cây.
Kết quả:
Dòng đầu tiên in ra một số nguyên — số lượng cạnh của đồ thị con cực đại tìm được.
Dòng thứ hai in ra ba số nguyên là nhãn của 3 đỉnh trong tập ( và đôi một khác nhau). Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.
Ví dụ:
Dữ liệu:
4
1 2
2 3
3 4
Kết quả:
3
1 2 4
Dữ liệu:
5
1 2
1 3
1 4
1 5
Kết quả:
3
2 3 4
Dữ liệu:
8
1 2
2 3
3 4
4 5
4 6
3 7
7 8
Kết quả:
6
1 5 8
Giải thích:
Trong ví dụ đầu tiên, cây là một đường thẳng . Chọn tập , đồ thị con liên thông nhỏ nhất chứa chúng bao gồm các cạnh . Tổng số cạnh là 3.
Trong ví dụ thứ hai, cây có dạng hình sao với tâm là 1. Chọn 3 lá bất kỳ (ví dụ 2, 3, 4), ta cần các cạnh để kết nối chúng. Tổng số cạnh là 3.
Trong ví dụ thứ ba, chọn 3 đỉnh , đồ thị con nhỏ nhất chứa chúng gồm các cạnh: . Tổng cộng có 6 cạnh.
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (30% số điểm): .
Subtask #3 (20% số điểm): Đồ thị có dạng đường thẳng (đỉnh nối với ).
Subtask #4 (30% số điểm): , không có ràng buộc gì thêm.
