Пересадки

Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, между какими парами городов можно лететь ровно с K пересадками. Напишите программу, которая выводит все пары таких городов.

Входные данные
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 50 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему авиационных сообщений. В последней строке вводится число K – желаемое количество пересадок.

Выходные данные
Программа должна найти все пары городов, между которыми можно лететь ровно с K пересадками. Каждая пара должна быть выведена в отдельной строке, номера городов в паре расположены по возрастанию. Нумерация начинается с единицы. Пары должны быть упорядочены: сначала все пары, которые начинаются в городе 1 по возрастанию второго номера города в паре, и т.д. Если ни одной такой пары не найдено, нужно вывести число 0.

Примеры
входные данные
4
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
2
выходные данные
1 4
2 4

0