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

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

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

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

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

4
0 
1 0
1 1 0
1 1 1 0

NO

5
0 
1 0
2 1 0
3 2 1 0
-1 -1 -1 -1 0

YES
0 1
1 2
2 3

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

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