Дано дерево из \(n\) вершин. Некоторые вершины дерева (хотя бы две) — черные, остальные — белые.
Вы ставите фишку в какую-то из вершин дерева и после этого проводите следующие операции:
- пусть фишка сейчас находится в вершине \(x\). Вы выбираете черную вершину \(y\), а затем перемещаете фишку по первому ребру в простом пути из \(x\) в \(y\).
Вы не можете выбирать одну и ту же вершину \(y\) в двух операциях подряд (то есть для любых двух последовательных операций выбранные черные вершины должны быть различны).
Вы заканчиваете операции, когда фишка оказывается в черной вершине (если она изначально в черной вершине — вы не выполняете операции вообще), или когда количество выполненных операций становится больше \(100^{500}\).
Для каждой вершины \(i\) вы должны определить, существует ли (не обязательно непустая) последовательность операций, в результате которой фишка окажется в черной вершине, если изначально фишка расположена в вершине \(i\).
Выходные данные
Выведите \(n\) целых чисел. \(i\)-е из них должно быть равно \(1\), если существует (возможно, пустая) последовательность операций, которая перемещает фишку в черную вершину, если изначально расположить ее в вершине \(i\), или \(0\), если такой последовательности операций не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
0 1 0 0 0 0 1 0
8 6
2 5
7 8
6 5
4 5
6 1
7 3
|
0 1 1 1 1 0 1 1
|