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.