G. Легендарный древесный гроссмейстер
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В мире деревьев есть популярная игра для двух игроков, которая проводится на дереве с $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$)  — количество вершин в дереве.

Каждая из следующих $$$n$$$ строк содержит строку из $$$n$$$ символов, где $$$j$$$-й символ $$$i$$$-й строки равняется $$$s_{i, j}$$$ ($$$s_{i, j} \in \{\mathtt{0}, \mathtt{1}\}$$$) — выигрышные и проигрышные состояния дерева.

Выходные данные

Если не существует дерева, удовлетворяющего выигрышным и проигрышным состояниям, представленным матрицей $$$s$$$, выведите единственную строку, содержащую «NO».

В противном случае, если существует дерево, удовлетворяющее матрице $$$s$$$, выведите «YES» в первой строке, а затем $$$n - 1$$$ строку, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), означающих, что дерево имеет ребро между вершинами $$$u$$$ и $$$v$$$.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Если существует несколько деревьев, удовлетворяющих матрице $$$s$$$, выведите любое из них.

Примеры
Входные данные
4
1100
0101
0011
0101
Выходные данные
YES
4 1
3 2
2 4
Входные данные
3
001
010
100
Выходные данные
NO
Примечание

В первом наборе входных данных граф $$$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$$$.