Вам задано невзвешенное дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\), и список из \(n-1\) целого числа \(a_1, a_2, \ldots, a_{n-1}\). Дерево — это связный неориентированный граф без циклов. Вы можете использовать каждый элемент списка, чтобы пометить одну из вершин дерева. Никакая вершина не должна быть помечена дважды. Вы можете пометить единственную оставшуюся непомеченной вершину любым целым числом.
Вершина \(x\) называется хорошей, если можно так пометить вершины, чтобы для каждой вершины \(i\) ее метка была равна расстоянию между \(x\) и \(i\). Расстояние между двумя вершинами \(s\) и \(t\) на дереве — это минимальное количество ребер на пути, который начинается в вершине \(s\) и заканчивается в вершине \(t\).
Найдите все хорошие вершины.
Выходные данные
В первой строке выведите количество хороших вершин.
Во второй строке выведите номера всех хороших вершин в порядке возрастания.
Примечание
На рисунке ниже показано дерево для первого примера:
На рисунке ниже показаны две возможные разметки, такие что \(2\) — хорошая вершина (слева) и \(4\) — хорошая вершина (справа).
Квадрат под каждой вершиной означает ее метку. Черные квадраты содержат числа, которые были в данном списке, а единственный белый квадрат содержит единственное число, которого не было в данном списке.
Во втором примере единственной хорошей вершиной является вершина \(3\).
В третьем примере хороших вершин нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 1 0 1 2
1 2
2 3
2 4
4 5
4 6
|
2
2 4
|
|
2
|
5
1 2 1 2
1 2
3 2
3 4
5 4
|
1
3
|
|
3
|
3
2 2
1 2
2 3
|
0
|