<PREV Problem:
NEXT>
Solved by 56 users: ...
UserDateAttemptTimeCMSC
ignat16 dec 2008C++200.09448 
Ravent22 dec 2006FPC300.38452 
imAnik13 mar 2017C++100.82471 
vjudge113 mar 2017C++100.83471 
Philip_PV22 feb 2009C++300.11481 
Stranger03 dec 2006FPC200.57482 
tourist08 jan 2008Kylix100.03503 
Philip_PV22 feb 2009C++200.11510 
tomek17 dec 2006C++800.05552 
Ra16bit13 dec 2008C++100.20561 
TTLovePP25 dec 2010C++1400.07583 
Languages
C++
49
FPC
5
Java
2
Kylix
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Graph existance

Time limit = 2 second(s)

You are given a matrix of distances in a graph. You should check whether this graph could be a tree or set of trees (forest). Edge length is 0 or positive integer.

Input The first line contains number of vertices N. Next N lines contains matrix (only left bottom triangle of matrix). Distance -1 corresponds to infinite distance.

Output Output YES or NO. If YES, then next lines should contains list of edges of the tree (any tree (forest) with given distance matrix). Each edge is coded by two identifiers of it's ends. Vertex identifiers are numbers 0, 1, ..., N-1.

Input#1
4
0 
1 0
1 1 0
1 1 1 0
Output#1
NO
Input#2
5
0 
1 0
2 1 0
3 2 1 0
-1 -1 -1 -1 0
Output#2
YES
0 1
1 2
2 3

Author:
Artem Voroztsov
25 November 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.210.24.208