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

Захват королевства

Захват королевства

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

В одном магическом королевстве есть N городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами, те дороги, которые были построены Светлыми силами вымощены белыми камнями, а те, которые построены Темными - черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое - по белой дороге.

Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились и решили вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные города под свой контроль.

Точнее, если светлый маг будет направлен в некоторый город, то он возьмет под свой контроль этот город и все города, которые напрямую соединены с ним белыми дорогами. Аналогично, черный маг помимо города, в который он направлен, будет контролировать все города, напрямую соединенные с ним черными дорогами. Для захвата королевства требуется установить контроль над всеми городами.

Однако при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K.

Единственная надежда верховных магов заключается в том, что K достаточно велико, 2^KN.

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

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

Первая строка входного файла содержит целые числа N и K (2N256, 2^KN, KN).

Следующие N строк содержат по N целых чисел каждая. На i-ой позиции i-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех j <> i число на j-ой позиции i-ой из этих строк равно 1, если i-ый город соединен с j-ым белой дорогой и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.

Гарантируется, что входные данные корректны, то есть если i-ый город соединен с j-ым белой дорогой, то и j-ый соединен с i-ым белой дорогой, аналогично в случае черных дорог.

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

Если захватить королевство при заданных условиях невозможно, выведите в выходной файл единственное число 0.

В противном случае на первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. На следующей строке выведите число LK - количество использованных магов. Третья строка должна содержать L целых чисел - номера городов, в которые следует направить магов.

Заметьте, что вам не требуется минимизировать L. Если решений несколько, выведите любое.

Пример

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