Вам задано невзвешенное дерево с \(n\) вершинами. Напомним, что дерево — это связный неориентированный граф без циклов.
Ваша задача — выбрать три различных вершины \(a, b, c\) в этом дереве таких, что количество ребер, принадлежащих как минимум одному из простых путей между \(a\) и \(b\), \(b\) и \(c\), или \(a\) и \(c\), максимально. Обратите внимание на примечания для лучшего понимания.
Простой путь — это путь, который посещает каждую вершину не более одного раза.
Выходные данные
Первой строкой выведите одно целое число \(res\) — максимальное количество ребер, принадлежащих как минимум одному из простых путей между \(a\) и \(b\), \(b\) и \(c\), или \(a\) и \(c\).
Во второй строке выведите три целых числа \(a, b, c\) таких, что \(1 \le a, b, c \le n\) и \(a \ne, b \ne c, a \ne c\).
Если существует несколько подходящих ответов, вы можете вывести любой.
Примечание
Изображение, соответствующее первому примеру (и другой правильный ответ):
Если выбрать вершины \(1, 5, 6\), то путь между вершинами \(1\) и \(5\) состоит из ребер \((1, 2), (2, 3), (3, 4), (4, 5)\), путь между \(1\) и \(6\) состоит из ребер \((1, 2), (2, 3), (3, 4), (4, 6)\) и путь между \(5\) и \(6\) состоит из ребер \((4, 5), (4, 6)\). Объединение этих путей — \((1, 2), (2, 3), (3, 4), (4, 5), (4, 6)\), следовательно, ответ — \(5\). Можно показать, что лучшего ответа не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 2
2 3
3 4
4 5
4 6
3 7
3 8
|
5
1 8 6
|