1 人解决，5 人已尝试。
1 份提交通过，共有 10 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
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 two-way. 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 0 3
the neighbouring towns are A, B and A, C.
Task
Write a program that:
1.reads the table of distances;
2.finds all the pairs of neighbouring towns;
3.writes the result.
In the first line of the input 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 of the input. In the (i+1)-st line, 1<=i<=n, there are n non-negative integers not greater than 200, separated by single spaces. The j-th integer is the distance between towns i and j.
Your program should write all the pairs of the neighbouring towns (i.e. their numbers) to the toutput. 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 i b < d).
3 0 1 2 1 0 3 2 3 0
1 2 1 3
1 人解决，5 人已尝试。
1 份提交通过，共有 10 份提交。
9.9 EMB 奖励。