410268: GYM103994 J Прямоугольное дерево

J. Прямоугольное деревоограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

После двух своих любимых уроков — геометрии и информатики, маленький Игорь пришел на урок по истории и тут же уснул. Ему приснилось, что он сидит где-то на острове Самос и рисует на песке прямоугольные деревья. Прямоугольным Игорь называет дерево, в котором есть $$$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 можно выводить в любом регистре.

ПримерВходные данные

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
2 8 20

Примечание

Пояснения к примерам:

• Для первого дерева, существует только одна тройка вершин: $$$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$$$.

  Следовательно, это дерево является прямоугольным.