На секретную базу пробрался секретный шпион. База состоит из $$$N$$$ помещений, соединенных переходами. На секретный пульт охраны поступил сигнал тревоги. Для обнаружения шпиона было решено выслать $$$k$$$ секретных охранников. В начальный момент времени все охранники находятся в зале №1 базы. За одну минуту один (и только один) из охранников может перейти по проходу в соседнюю комнату. Аналогично шпион за одну минуту может перейти в соседнюю комнату или остаться на месте.
Если какой-то из охранников и шпион в один момент времени оказываются в одной комнате или пытаются пройти по одному и тому же коридору навстречу друг другу, то шпион оказывается схваченным.
Напишите программу, которая определит наименьшее количество охранников, которое необходимо для того, чтобы проверить всю базу и поймать шпиона или убедиться, что тревога была ложной.
Во входном файле записано сначала число $$$N$$$ ($$$1 \leq N \leq 15$$$), а затем идет таблица $$$N \times N$$$ 0 и 1, описывающая военную базу. В позиции ($$$i,j$$$) этой таблицы стоит 0, если прохода из $$$i$$$-ой комнаты в $$$j$$$-ую не существует, и 1 — если существует. На диагонали этой таблицы стоят 0. Элемент ($$$i, j$$$) всегда равен элементу ($$$j, i$$$).
В выходной файл выведите сначала число охранников, а затем алгоритм их действий в следующем формате: номер охранника, и в какую комнату он перемещается. Алгоритм должен заканчиваться парой (0,0) и содержать не более 1000000 шагов.
3 1 1 1 1 0 0 1 0 0
1 1 2 1 3 0 0