Задача №518. Захват королевства
В одном магическом королевстве есть \(N\) городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами. Дороги, которые были построены Светлыми силами, вымощены белыми камнями, а те, что построены Темными – черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое – по белой дороге.
Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные с ними города под свой контроль.
Точнее, если светлый маг будет направлен в некоторый город, то он возьмет под свой контроль этот город и все города, которые напрямую соединены с ним белыми дорогами. Аналогично, черный маг помимо города, в который он направлен, будет контролировать все города, напрямую соединенные с ним черными дорогами. Для захвата королевства требуется установить контроль над всеми городами.
Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, \(2^K\) >= \(N\).
Выясните, светлых или темных магов следует использовать для захвата королевства, а также в какие города их следует направить.
В первой строке вводятся целые числа \(N\) и \(K\) ( \(2 \le N \le 256\), \(2^K\) \(\ge\) \(N\), \(K \le N\)).
Следующие \(N\) строк содержат по \(N\) целых чисел каждая. На \(i\)-ой позиции \(i\)-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех \(j \neq i\) число на \(j\)-ой позиции \(i\)-ой из этих строк равно 1, если \(i\)-ый город соединен с \(j\)-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.
Гарантируется, что входные данные корректны, то есть если \(i\)-ый город соединен с \(j\)-ым белой дорогой, то и \(j\)-ый соединен с \(i\)-ым белой дорогой, аналогично в случае черных дорог.
Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L\( \le\)K – количество использованных магов. Третья строка должна содержать \(L\) целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать \(L\). Если решений несколько, выведите любое.
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