В мире деревьев есть популярная игра для двух игроков, которая проводится на дереве с \(n\) вершинами, пронумерованными от \(1\) до \(n\). В этой игре ведущие турнира сначала выбирают вершину, которая будет корнем дерева, и выбирают другую вершину (возможно, ту же самую, что и корень), на которую кладут монету. Затем каждый игрок по очереди перемещает монету в любую дочернюю\(^\dagger\) вершину вершины, на которой в данный момент находится монета. Первый игрок, который не может сделать ход, проигрывает.
Алиса хочет стать легендарным древесным гроссмейстером, поэтому она тратит много времени на изучение игры. Она записала матрицу \(s\) размером \(n\) на \(n\), где \(s_{i,j} = \mathtt{1}\), если первый игрок может выиграть, если корнем дерева выбрана вершина \(i\), а монета изначально была помещена на вершину \(j\). В противном случае \(s_{i, j} = \mathtt{0}\). Алиса — перфекционистка, поэтому она предполагает, что оба игрока играют идеально.
Однако по дороге на турнир она случайно ударилась головой и забыла, как выглядит дерево. Определите, существует ли дерево, которое удовлетворяет выигрышным и проигрышным состояниям, представленным матрицей \(s\), и если существует, постройте подходящее дерево.
\(^\dagger\) Вершина \(c\) является дочерней по отношению к вершине \(u\), если между \(c\) и \(u\) есть ребро, и \(c\) не лежит на единственном простом пути из корня в вершину \(u\).
Выходные данные
Если не существует дерева, удовлетворяющего выигрышным и проигрышным состояниям, представленным матрицей \(s\), выведите единственную строку, содержащую «NO».
В противном случае, если существует дерево, удовлетворяющее матрице \(s\), выведите «YES» в первой строке, а затем \(n - 1\) строку, каждая из которых содержит два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\)), означающих, что дерево имеет ребро между вершинами \(u\) и \(v\).
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Если существует несколько деревьев, удовлетворяющих матрице \(s\), выведите любое из них.
Примечание
В первом наборе входных данных граф \(1\!-\!4\!-\!2\!-\!3\) удовлетворяет выигрышным и проигрышным состояниям, представленным матрицей \(s\). Например, \(s_{3,3} = 1\), так как первый игрок может переместить монету из \(3\rightarrow 2\), затем второй игрок перемещает монету из \(2\rightarrow 4\), и, наконец, первый игрок перемещает монету из \(4\rightarrow 1\). В этот момент у вершины \(1\) нет детей, поэтому второй игрок не может сделать ход и проигрывает. С другой стороны, \(s_{1,3} = 0\), так как если \(1\) является корнем, то у \(3\) нет детей, поэтому первый игрок не может сделать первый ход и проигрывает.
Во втором наборе входных данных можно показать, что ни одно дерево не удовлетворяет матрице \(s\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1100
0101
0011
0101
|
YES
4 1
3 2
2 4
|
|
2
|
3
001
010
100
|
NO
|