Рассмотрим географическую карту с N странами, занумерованными от 1 до N (0 < N < 99). Для каждой страны известны номера соседних стран, т.е. имеющих общую границу с данной. Из каждой страны можно попасть в любую другую, перейдя некоторое количество границ. Напишите программу, которая определит, возможно ли покрасить карту только в два цвета — красный и синий — так, что если две страны имеют общую границу, их цвета различаются. Цвет первой страны — красный. Ваша программа должна вывести одну возможную раскраску для остальных стран или сообщить, что такая раскраска невозможна.
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В первой строке записано число N. Из следующих N строк i-я строка содержит номера стран, с которыми i-я страна имеет границу. Каждое целое число в i-й строке больше, чем i, кроме последнего, которое равно 0 и обозначает конец списка соседей i-й страны. Если строка содержит 0, это значит, что i-я страна не соединена ни с одной страной с бoльшим номером.
Вывод содержит ровно одну строку. Если раскраска возможна, эта строка должна содержать список нулей и единиц без разделителей между ними. i-я цифра в этой последовательности обозначает цвет i-й страны. 0 соответствует красному цвету, единица — синему. Если раскраска невозможна, выведите целое число –1.
| Исходные данные | Результат |
|---|---|
| 3 2 0 3 0 0 |
010 |