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

1128. Деление на группы

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
В детском саду N детей. К сожалению, дети иногда ссорятся, хотя и не часто. У каждого ребёнка есть не более трёх недругов. Можно ли разделить детей на две группы (не обязательно равные) так, чтобы у каждого ребёнка в одной с ним группе было бы не более одного неприятеля?

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

В первой строке находится положительное число N, не превосходящее 7163. В последующих N строках указаны списки недругов для каждого из детей. В начале каждой строки указывается количество недругов для очередного ребёнка, затем перечисляются номера недругов. Числа в одной строке отделяются друг от друга пробелом.

Результат

В первой строке указывается количество детей в той из групп, которая содержит меньшее число детей. Затем во второй строке указывается список детей в этой группе. Числа во второй строке разделяются пробелом. Если в обеих группах одинаковое число детей, то следует выводить описание той, в которой оказывается ребёнок номер 1. Заметим, что вполне возможна ситуация, когда ответ состоит из единственного числа 0. Если возможных разбиений несколько, достаточно вывести любое из них. Если разбить детей на группы невозможно, то в первую строку следует вывести строку «NO SOLUTION»

Пример

исходные данныерезультат
8
3 2 3 7
3 1 3 7
3 1 2 7
1 6
0
2 4 8
3 1 2 3
1 6
4
1 2 5 6
Автор задачи: Дмитрий Филимоненков
Источник задачи: VI Ural State University Collegiate Programming Contest (21.10.2001)