В одном магическом королевстве есть 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. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
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
3
1 5 2
|