Сегодня Яхуб изобрел новое дерево под названием дерево XOR. После этого революционного открытия юноша изобрел игру для детей на деревьях XOR.
Игра проходит на корневом дереве с n вершинами, пронумерованными от 1 до n. Каждая вершина i имеет начальное значение initi, равное 0 или 1. Корень дерева — вершина с номером 1.
Во время игры нужно выполнить несколько (возможно, ноль) операций с деревом. Единственный доступный тип операции — выбрать вершину x. Как только вершина x выбрана, значение в ней меняется на противоположное (с 1 на 0, а с 0 на 1), значения сыновей вершины x не меняются, значения сыновей сыновей вершины x меняются на противоположные, значения сыновей сыновей сыновей вершины x остаются прежними и так далее.
Цель игры — присвоить каждой вершине i значение goali. Вам же надо достигнуть цели игры за минимальное количество операций.
Выходные данные
В первой строке выведите целое cnt, которое обозначает минимальное количество операций. В каждой из следующих cnt строк надо вывести целое число xi, обозначающее, что на i-м ходу вы выбрали вершину xi.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
|
2
4
7
|