Дано целое число \(n\). Определим следующее дерево деревом McDic:
Дано дерево. Определите, является ли это дерево деревом McDic. Если да, найдите предка удаленной вершины.
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 17\)).
\(i\)-я из следующих \(2^{n} - 3\) строк содержит два целых числа \(a_{i}\) и \(b_{i}\) (\(1 \le a_{i} \lt b_{i} \le 2^{n} - 2\)), которые значат, что существует ребро между \(a_{i}\) и \(b_{i}\). Гарантируется, что граф — дерево.
Выведите две строки.
В первой строке выведите одно целое число — количество ответов. Если это дерево не является деревом McDic, то выведите \(0\).
Во второй строке выведите все возможные ответы в возрастающем порядке. Если это дерево не является деревом McDic, то ничего не выводите.
В первом примере \(3\) — это единственный возможный ответ.
Во втором примере есть \(2\) возможных ответа.
В третьем примере дерево не является деревом McDic.
4 1 2 1 3 2 4 2 5 3 6 3 13 3 14 4 7 4 8 5 9 5 10 6 11 6 12
1 3
2 1 2
3 1 2 2 3 3 4 4 5 5 6
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач