Задача. "Белый, черный и зеленый"

Дан неориентированный граф без петель и кратных ребер. В нем все вершины с четными номерами покрасили в белый цвет, а с нечетными номерами - в черный. После этого те черные вершины, у которых было не меньше 3-х белых соседей, перекрасили в зеленый цвет. Выведите, какого цвета в итоге стала каждая вершина.

Входные данные

Сначала вводится число N (1≤N≤50). Далее вводится матрица смежности этого графа.

Выходные данные

Выведите N чисел - цвета вершин в порядке их номеров. 0 обозачает черный цвет, 1 - белый, 2 - зеленый.

Пример

Пример вводаПример вывода
8
0 1 0 1 1 1 1 0
1 0 1 1 0 0 0 0 
0 1 0 1 1 1 1 1
1 1 1 0 0 1 0 1
1 0 1 0 0 0 1 0
1 0 1 1 0 0 0 1
1 0 1 0 1 0 0 0
0 0 1 1 0 1 0 0
2 1 2 1 0 1 0 1