eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Толстые хоббиты

Толстые хоббиты

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Ни один хоббит не в состоянии в одиночку противостоять полчищам Мордора… В последний поход против Мордора Гэндальф решил отправить N хоббитов из Шира. Но часть хоббитов наотрез отказалась, жалуясь на то, что другие хоббиты наверняка будут дразнить их толстыми. После опроса всех хоббитов оказалось, что любой хоббит отказывается принять участие в походе в том случае, если с ним в поход выступит хотя бы один хоббит с меньшим весом. К счастью для Средиземья, не все хоббиты знают свой точный вес. В Шире были всего одни весы чашечного типа, позволяющие для пары хоббитов определить, какой хоббит тяжелее. Некоторые пары хоббитов взвешивались на этих весах. Всем хоббитам известен результат всех взвешиваний. Гэндальф абсолютно уверен, что в Шире нет двух хоббитов одного веса. Он заинтересован в том, чтобы отряд состоял из наибольшего количества хоббитов. Однако найти наибольшее множество хоббитов, среди которых ни один не считает себя тяжелей другого, оказалось не так-то просто. Подскажите Гэндальфу, на сколько хоббитов он может рассчитывать. Помните при этом, что хоббиты умные существа и знают, что если Сэм тяжелее Пиппина, а Пиппин тяжелее Фродо, то Сэм и подавно будет тяжелее Фродо.

Входные данные

В первой строке дано целое число N — количество хоббитов (2N100). Все хоббиты пронумерованы целыми числами от 1 до N. В следующих N строках записана матрица размера N×N. Если i-й и j-й хоббит взвешивались на чашечных весах и оказалось, что i-й хоббит тяжелее, то в i-й строке матрицы на j-й позиции стоит единица. Во всех остальных случаях в матрице стоят нули.

Выходные данные

В первой строке выведите размер наибольшего множества хоббитов, готового выступить в поход, во второй строке перечислите номера хоббитов из этого множества через пробел.

Пример

Входные данные #1
2
0 1
0 0
Выходные данные #1
1
2