Задача №111526. Большая прогулка
Во время летних каникул Вася и Петя путешествовали со своими родителями по Одной Очень Гостеприимной Стране. В этой стране всего N городов, пронумерованных числами от 1 до N. Маршрут Васи начинался в городе A и заканчивался в городе B, а маршрут Пети – начинался в городе C и заканчивался в городе D. Поскольку времени у них было немного, то и Васины и Петины родители выбрали самый короткий путь, соединяющий начальный и конечный города их маршрута.
После каникул Вася с Петей встретились и захотели обсудить свои путешествия. Особенно интересно было обсуждать те города, в которых побывали они оба.
Определите, в каких городах побывали и Вася и Петя и выведите их номера в порядке возрастания. Если же маршруты ребят не пересекались, выведите -1.
Обратите внимание на то, что поскольку на некоторых дорогах шел ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X.
В первой строке вводится число N (1 ≤ N ≤ 100). В следующих N строках вводится по N чисел, не превосходящих 100, j-ое число в i-ой строке равно длине пути между i-м и j-м городом. Известно, что между любыми двумя городами есть дорога и поскольку на некоторых дорогах идет ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X. В следующих двух строках вводятся пары целых числа от 1 до 100 – номера городов, являющихся началом и концом маршрута Васи (A и B), и аналогичные числа для Пети (C и D).
Выведите их номера в порядке возрастания. Если маршруты ребят не пересекались, выведите одно число - 1. Гарантируется, что кратчайший путь – единственный.
4
0 100 100 1
100 0 3 100
100 4 0 1
100 3 10 0
1 3
2 3
2 3