ROADNET  Road net
A diskette was enclosed to a road map. The diskette contains the table of the shortest ways (distances) between each pair of towns on the map. All the roads are twoway. The location of towns on the map has the following interesting property: if the length of the shortest way from town A to town B equals the sum of the lengths of the shortest ways from A to C and C to B then town C lies on (certain) shortest way from A to B. We say that towns A and B are neighbouring towns if there is no town C such that the length of the shortest way from A to B equals the sum of the lengths of the shortest ways from A to C and C to B. Find all the pairs of neighbouring towns.
Example
For the table of distances:
A  B  C  

A  0  1  2 
B  1  0  3 
C  2  3  0 
the neighbouring towns are A, B and A, C.
Task
Write a program that for each test case:
 reads the table of distances from standard input;
 finds all the pairs of neighbouring towns;
 writes the result to standard output.
Input
The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
In the first line of each test case there is an integer n, 1 <= n <= 200, which equals the number of towns on the map. Towns are numbered from 1 to n.
The table of distances is written in the following n lines. In the (i+1)th line, 1 <= i <= n, there are n nonnegative integers not greater than 200, separated by single spaces. The jth integer is the distance between towns i and j.
Output
For each test case your program should write all the pairs of the neighbouring towns (i.e. their numbers). There should be one pair in each line. Each pair can appear only once. The numbers in each pair should be given in increasing order. Pairs should be ordered so that if the pair (a, b) precedes the pair (c, d) then a < c or (a = c and b < d).
Consequent test cases should by separated by an empty line.
Example
Sample input: 1 3 0 1 2 1 0 3 2 3 0 Sample output: 1 2 1 3
hide comments
csd_123:
20201022 18:36:47
did it in O(n3) time any O(n2) solution


nadstratosfer:
20190407 12:23:22
The annoying gibberish of a statement costed me an hour of solving wrong problems. How hard would it be to write "Find pairs of towns such that the shortest way between them doesn't lead through another town" ?


anubhav1772:
20170717 19:19:55
O(n^3) works...AC in 1 GO :) 

nky_007:
20170317 15:20:43
AC using dijkstra algo.. 

vengatesh15:
20170110 13:44:29
AC in 1 go 

amit_taps1997:
20161225 13:59:55
Those who are getting SIGSXSZ, check the loops sequence 

Divyansh Shukla:
20151226 22:46:39
Simple FloydWarshall :) 

geoffreymace7:
20151218 17:35:27
How does one avoid SIGSXSZ? 

swordfish12:
20150310 04:53:47
n^3 solution works... easy one


Rajat (1307086):
20141217 12:25:53
Got SIGSXSZ first.

Added by:  Michał Czuczman 
Date:  20040810 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  5th Polish Olympiad in Informatics, stage 2 (Piotr ChrząstowskiWachtel) 