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

1182. Team Them Up!

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Your task is to divide a number of persons into two teams, in such a way, that:
  • everyone belongs to one of the teams;
  • every team has at least one member;
  • every person in the team knows every other person in his team;
  • teams are as close in their sizes as possible.
This task may have many solutions. You are to find and output any solution, or to report that the solution does not exist.

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

For simplicity, all persons are assigned a unique integer identifier from 1 to N.
The first line contains a single integer number N (2 ≤ N ≤ 100) - the total number of persons to divide into teams, followed by N lines - one line per person in ascending order of their identifiers. Each line contains the list of distinct numbers Aij (1 ≤ Aij ≤ N, Aij ≠ i) separated by spaces. The list represents identifiers of persons that ith person knows. The list is terminated by 0.

Результат

If the solution to the problem does not exist, then write a single message “No solution” (without quotes). Otherwise write a solution on two lines. On the first line write the number of persons in the first team, followed by the identifiers of persons in the first team, placing one space before each identifier. On the second line describe the second team in the same way. You may write teams and identifiers of persons in a team in any order.

Пример

исходные данныерезультат
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
3 1 3 5
2 2 4
Автор задачи: Vladimir Kotov, Roman Elizarov
Источник задачи: 2001-2002 ACM Northeastern European Regional Programming Contest