Приглашаем всех школьников принять участие в Заочной олимпиаде ФУПМ по программированию

<PREV Problem:
NEXT>
Solved by 54 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 210ms

SW soft NIX
ID = 54.80.63.78