Группа людей состоит из N членов. У каждого члена группы есть друзья в этой группе, один или более. Напишите программу, которая разделит группу на две команды. Каждый член каждой команды должен иметь друзей в другой команде.
Исходные данные
Первая строка ввода содержит одно число N (N ≤ 100). Члены группы занумерованы от 1 до N. Вторая, третья, …, (N+1)-я строки содержат список друзей первого, второго, …, N-го членов группы соответственно. Списки друзей заканчиваются нулями. Помните, что отношение дружбы в группе всегда взаимное.
Результат
Первая строка вывода должна содержать количество людей в первой группе или ноль, если невозможно разделить людей на две группы. Если решение существует, выведите список первой группы во второй строке вывода. Числа должны быть разделены одиночными пробелами. Если существует более одного решения, можете вывести любое из них.
Пример
исходные данные | результат |
---|
7
2 3 0
3 1 0
1 2 4 5 0
3 0
3 0
7 0
6 0
| 4
2 4 5 6
|
Автор задачи: Дмитрий Филимоненков
Источник задачи: Tetrahedron Team Contest May 2001