ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1176. Гиперканалы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В состав Галактической империи входит N планет. Между большинством из них существуют гиперканалы. Новый император повелел, чтобы с любой планеты можно было попасть на любую другую, пройдя только через один гиперканал. Каналы устроены так, что позволяют путешествовать только в одну сторону.
Единственный оставшийся прокладчик гиперканалов расположен на базе около планеты с номером A. К сожалению, он не может путешествовать по уже существующим каналам, он всегда прокладывает новый. А наличие двух каналов в одном направлении между двумя планетами существенно осложняет навигацию. Ваша задача — найти такой маршрут для прокладчика, чтобы все необходимые каналы были построены, и не было бы построено лишних. В конце своего маршрута прокладчик должен оказаться на своей родной базе, с которой он начал движение.

Исходные данные

В первой строке находится число N ≤ 1000 и число AN. N следующих строк содержит по N чисел — в i-й строке j-е число равно 1, если есть канал от планеты i к планете j, иначе 0. Известно, что Галактическая империя может удовлетворить свою потребность в гиперканалах прокладкой не более чем 32000 новых каналов.

Результат

Выведите последовательность, в которой следует прокладывать каналы. Каждая строка должна содержать два целых числа: номера планет, с какой и на какую следует проложить очередной гиперканал. Гиперканалы следует перечислить в порядке их прокладки. Гарантируется, что решение существует.

Пример

исходные данныерезультат
4 2
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0
2 4
4 1
1 2
2 1
1 4
4 2
Автор задачи: Павел Атнашев
Источник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002