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

<ПРЕД Задача:
СЛЕД>
Задачу решили 54 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Существование дерева

Time limit = 2 секунд(ы)

Дана матрица длин кратчайших путей в некотором графе. Проверить, может ли этот граф быть деревом или лесом деревьев. Если может, то вывести рёбра этого дерева.

Длины рёбер --- целые неотрицательные числа.

Вход. В первой строке указано число вершин графа N. 0 < N < 1000. Затем идёт N строк. В i-й строке дано i целых чисел, которые соответствуют расстоянию от i-й вершины до вершин с меньшими номерами. Последнее число равно 0, то есть расстояние от вершины до её самой равно 0. Все числа либо неотрицательны либо равны -1. Последнее означает, что соответствующие вершины не связаны (расстояние между ними равно бесконечности).

Выход. В первой строке следует написать либо слово YES, либо NO. В следующих строчках указаны пары идентификаторов вершин. Идентификаторы вершин меняются от 0 до (N-1).

Вход#1
4
0 
1 0
1 1 0
1 1 1 0
Выход#1
NO
Вход#2
5
0 
1 0
2 1 0
3 2 1 0
-1 -1 -1 -1 0
Выход#2
YES
0 1
1 2
2 3

Автор:
Ворожцов Артем.
25 ноября 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 50.16.165.62