Захват королевства
В одном магическом королевстве есть N городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами, те дороги, которые были построены Светлыми силами вымощены белыми камнями, а те, которые построены Темными - черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое - по белой дороге.
Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились и решили вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные города под свой контроль.
Точнее, если светлый маг будет направлен в некоторый город, то он возьмет под свой контроль этот город и все города, которые напрямую соединены с ним белыми дорогами. Аналогично, черный маг помимо города, в который он направлен, будет контролировать все города, напрямую соединенные с ним черными дорогами. Для захвата королевства требуется установить контроль над всеми городами.
Однако при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K.
Единственная надежда верховных магов заключается в том, что K достаточно велико, 2^K ≥ N.
Выясните, светлых или темных магов следует использовать для захвата королевства, а также в какие города их следует направить.
Входные данные
Первая строка входного файла содержит целые числа N и K (2 ≤ N ≤ 256, 2^K ≥ N, K ≤ N).
Следующие N строк содержат по N целых чисел каждая. На i-ой позиции i-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех j <> i число на j-ой позиции i-ой из этих строк равно 1, если i-ый город соединен с j-ым белой дорогой и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.
Гарантируется, что входные данные корректны, то есть если i-ый город соединен с j-ым белой дорогой, то и j-ый соединен с i-ым белой дорогой, аналогично в случае черных дорог.
Выходные данные
Если захватить королевство при заданных условиях невозможно, выведите в выходной файл единственное число 0.
В противном случае на первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. На следующей строке выведите число L ≤ K - количество использованных магов. Третья строка должна содержать L целых чисел - номера городов, в которые следует направить магов.
Заметьте, что вам не требуется минимизировать L. Если решений несколько, выведите любое.