MOBILE - Mobile

Manfred loves to build mobiles out of old CDs. For each one, he has an exact plan how it should look like: The CDs are all hanging exactly on the same height. For each pair of CDs, he writes down the height of the lowest bar such that both CDs are hanging somewhere under this bar. For example, the following mobile and distance matrix fit together:



After a while, Manfred realizes that he does not succeed to build every mobile he planned to. For example, there is no solution for the following distance matrix:
0 1 2
1 0 3
2 3 0
So, he decides to write a computer program that checks the distance matrices and tells him if there is a solution.

Input

Several matrices to check. The first row contains the size of the matrix N (N <= 2048), the next N rows contain the distances in the matrix. Then, the data of the next matrix comes, and so on. All distances are positive integers smaller than 2048. The input is terminated by a zero as matrix size.

Output

For each matrix, write true if Manfred can build a mobile, false otherwise.

Example

Input:
5
0 1 1 1 3
1 0 1 1 3
1 1 0 1 3
1 1 1 0 3
3 3 3 3 0
3
0 1 2
1 0 3
2 3 0
3
1 1 1
1 0 2
1 1 0
0

Output:
true
false
false

Added by:Martin Bader
Date:2006-10-17
Time limit:3.545s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Ulm Bioinformatics Course WS 06/07

hide comments
2019-07-30 14:52:23
How is the distance between CD-1 and CD-4 3 in the example? The first bar covers 1,2 & 3 and the second bar covers 2,3 & 4. They do not have a common bar under which they're both hanging.

If CD-1 is considered to be hanging under the bar at height-3 then CD-4 can be considered to be hanging under bar at height-1 too, so why is it 3 instead of 1?

Last edit: 2019-07-30 14:53:06
2010-04-07 22:01:54 :D
Yes, N<=2048 and also values for a matrix are smaller than 2048
2010-04-03 05:11:59 tld
I think n<=2000

Last edit: 2010-04-03 05:12:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.