Sieć dróg
Limit pamięci: 32 MB
Do mapy drogowej dołączona została dyskietka z tabelą długości najkrótszych dróg (odległości) między każdymi dwoma miastami na mapie.
Wszystkie drogi są dwukierunkowe.
Położenie miast na mapie ma następującą ciekawą własność.
Jeżeli długość najkrótszej drogi z miasta do jest równa sumie długości najkrótszych dróg z do i z do ,
to miasto leży na (pewnej) najkrótszej drodze z do .
Powiemy, że dwa miasta i sąsiadują ze sobą, jeżeli nie istnieje miasto takie,
że długość najkrótszej drogi z miasta do jest równa długości najkrótszych dróg z do i z do .
Na podstawie danej tabeli odległości znajdź wszystkie pary miast sąsiadujących ze sobą.
Przykład
Jeżeli tabela odległości ma postać
A B C
A 0 1 2
B 1 0 3
C 2 3 0
wówczas sąsiednimi miastami są i oraz i .
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia tabele odległości;
- znajduje wszystkie pary sąsiednich miast;
- zapisuje wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita , .
Jest to liczba miast na mapie.
Miasta ponumerowane są jednoznacznie od do .
Tabela odległości jest zapisana w kolejnych wierszach.
W wierszu , , jest zapisanych nieujemnych liczb całkowitych nie większych od , oddzielonych pojedynczym odstępem.
Liczba -ta jest odległości między miastami oraz .
Wyjście
Twój program powinien wypisać na standardowe wyjście wszystkie pary (numerów) sąsiednich miast, po jednej parze w każdym wierszu.
Każda para powinna pojawia się tylko raz.
Liczby w parze powinny być uporządkowane rosnąco i oddzielone pojedynczym odstępem.
Kolejność wypisywania par powinna być taka, że dla pary poprzedzającej parę , lub ( i ).
Przykład
Dla danych wejściowych:
3
0 1 2
1 0 3
2 3 0
poprawną odpowiedzią jest:
1 2
1 3
Autor zadania: Piotr Chrząstowski-Wachtel.