Дано целое число \(n\). Определим следующее дерево деревом McDic:
- Создадим полное бинарное дерево с \(2^{n} - 1\) вершинами. То есть дерево, где ровно одна вершина является корнем, все листы имеют одинаковую высоту (расстояние до корня) и все не листовые вершины имеют по два прямых потомка.
- Выберем любую некорневую вершину \(v\) из этого бинарного дерева.
- Удалим \(v\) из дерева и проведем ребра между предком \(v\) и прямыми потомками \(v\). Если у \(v\) нет потомков, тогда ребра не добавляются.
Дано дерево. Определите, является ли это дерево деревом McDic. Если да, найдите предка удаленной вершины.
Выходные данные
Выведите две строки.
В первой строке выведите одно целое число — количество ответов. Если это дерево не является деревом McDic, то выведите \(0\).
Во второй строке выведите все возможные ответы в возрастающем порядке. Если это дерево не является деревом McDic, то ничего не выводите.
Примечание
В первом примере \(3\) — это единственный возможный ответ.
Во втором примере есть \(2\) возможных ответа.
В третьем примере дерево не является деревом McDic.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
2
1 2
|
2
1 2
|
|
3
|
3
1 2
2 3
3 4
4 5
5 6
|
0
|