ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Winter Mathematical Festival Varna '2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Раскраска карты

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

Исходные данные

В первой строке записано число N. Из следующих N строк i-я строка содержит номера стран, с которыми i-я страна имеет границу. Каждое целое число в i-й строке больше, чем i, кроме последнего, которое равно 0 и обозначает конец списка соседей i-й страны. Если строка содержит 0, это значит, что i-я страна не соединена ни с одной страной с бoльшим номером.

Результат

Вывод содержит ровно одну строку. Если раскраска возможна, эта строка должна содержать список нулей и единиц без разделителей между ними. i-я цифра в этой последовательности обозначает цвет i-й страны. 0 соответствует красному цвету, единица — синему. Если раскраска невозможна, выведите целое число –1.

Пример

исходные данныерезультат
3
2 0
3 0
0
010
Автор задачи: Emil Kelevedzhiev
Источник задачи: Winter Mathematical Festival Varna '2001 Informatics Tournament
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1080. Раскраска карты