Задача №115163. Прямоугольное дерево
После двух своих любимых уроков — геометрии и информатики, маленький Игорь пришел на урок по истории и тут же уснул. Ему приснилось, что он сидит где-то на острове Самос и рисует на песке прямоугольные деревья. Прямоугольным Игорь называет дерево, в котором есть \(3\) различные вершины \(a\), \(b\) и \(c\), образующие прямоугольный треугольник, то есть такие, что \(dist(a, b)^2 + dist(b, c)^2 = dist(a, c)^2\).
\(dist(a, b)\) — это расстояние в дереве между вершинами \(a\) и \(b\), то есть количество ребер на единственном пути между ними.
Игорь сильно увелекся и нарисовал на песке очень много деревьев, и теперь для каждого из них он хочет понять, является ли оно прямоугольным. Помогите ему справиться с этой задачей, пока он не проснулся!
В первой строке вводится \(t\) (\(1 \le t \le 33\,333\)) — количество деревьев, нарисованных Игорем. В следующих строках содержатся описания каждого дерева.
В первой строке каждого описания вводится одно целое число \(n\) (\(3 \le n \le 100\,000\)) — количество вершин в дереве.
В следующих \(n - 1\) строках вводятся по два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — две вершины, которые соединены ребром.
Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра. Гарантируется, что сумма \(n\) из всех наборов входных данных не превосходит \(100\,000\).
Выведите ответ для каждого дерева:
Если в дереве нет прямоугольного треугольника, в отдельной строке выведите No .
Если хотя бы один прямоугольный треугольник есть, в первой строке выведите Yes , во второй — \(3\) числа, через пробел \(a, b, c\), (\(1 \le a, b, c, \le n\)) — номера любых \(3\)-х вершин, образующих прямоугольный треугольник в данном дереве. Вершины можно выводить в любом порядке. Обратите внимание, что вершины должны быть различными.
Буквы в Yes и No можно выводить в любом регистре.
Пояснения к примерам:
-
Для первого дерева, существует только одна тройка вершин: \(1\), \(2\), \(3\).
\(dist(1, 2) = 1\), \(dist(2, 3) = 1\), \(dist(1, 3) = 2\). Но \(1^2 + 1^2 \neq 2^2\) и \(1^2 + 2^2 \neq 1^2\), а значит, эти \(3\) вершины не образуют прямоугольный треугольник.
Следовательно, это дерево не является прямоугольным.
-
Во втором дереве есть прямоугольные треугольники. Например: \(2\), \(8\), \(20\).
\(dist(2, 8) = 10\), \(dist(2, 20) = 8\), \(dist(8, 20) = 6\), и \(6^2 + 8^2 = 10^2\).
Следовательно, это дерево является прямоугольным.
2 3 1 2 2 3 20 1 12 12 17 9 17 17 10 6 10 14 20 14 10 6 5 5 4 18 4 18 19 9 7 9 15 15 8 9 11 12 13 3 18 3 16 2 3
NO YES 6 8 11