В городе организовали радиосеть. Необходимо эту сеть присоединить к внешним сетям. Для этого надо выбрать узел, через который будет осуществляться подключение. Критерий для выбора узла следующий: расстояние от этого узла до максимально удалённого от него узла должно быть минимальным.
Расстояние между двумя непосредственно соединёнными узлами считается равным 1, а в случае, если надо использовать промежуточные узлы, каждый узел увеличивает расстояние на 1.
Входные данные
В первой строке входного файла INPUT.TXT содержится число N (N Ј 255) - количество узлов в сети.
В последующих N строках - матрица смежности радиосети. То есть в строке с номером i+1 на месте j стоит 1, если узлы с номерами i и j непосредственно соединены и 0 в противном случае. В каждой строке матрицы N чисел (нули и единицы) разделенные пробелами.
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести натуральное число - номер выбранного узла сети.
| Пример INPUT.TXT: | OUTPUT.TXT для примера: |
| 3 | 2 |
| 0 1 0 | |
| 1 0 1 | |
| 0 1 0 | |
Ограничение времени: 1 сек на тест