D1. Ориентация дерева (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Разница между версиями заключается в том, что в этой версии ограничение на $$$n$$$ ниже. Вы можете совершать взломы только в том случае, если вы решили все версии этой задачи.

Однажды у вас было неориентированное дерево с $$$n$$$ вершинами. Чтобы сделать дерево более интересным, вы решили назначить произвольное направление каждому из $$$n-1$$$ рёбер.

Со временем вы забыли структуру вашего дерева. Однако вы нашли записку, в которой зафиксировано после того, как направления рёбер были назначены, может ли $$$u$$$ достичь $$$v$$$$$$^{\text{∗}}$$$ для всех упорядоченных пар $$$(u,v)$$$, которые удовлетворяют $$$1\le u,v\le n$$$.

Вы хотите выяснить структуру дерева и направление рёбер на основе информации, представленной в записке. Определите, существует ли возможное решение, и постройте одно из них. Если существует несколько решений, вам нужно найти только одно из них.

$$$^{\text{∗}}$$$Для ориентированного графа мы говорим, что $$$x$$$ может достичь $$$y$$$, если и только если существует последовательность вершин $$$u_1,u_2,\ldots,u_k$$$, такая что $$$u_1=x,u_k=y$$$ и для всех $$$i$$$ от $$$2$$$ до $$$k$$$ существует направленное ребро $$$u_{i-1}\rightarrow u_i$$$. В частности, вершина всегда может достичь саму себя.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2\le n\le 500$$$), обозначающее количество вершин в вашем дереве.

Следующие $$$n$$$ строк содержат строку $$$s_i$$$. $$$s_i$$$ имеет длину $$$n$$$ и состоит только из $$$0$$$ и $$$1$$$. $$$j$$$-й символ $$$s_i$$$ равен $$$1$$$, если и только если $$$i$$$ может достичь $$$j$$$ после направления рёбер.

Гарантируется, что сумма $$$n^3$$$ по всем наборам входных данных не превосходит $$$500^3$$$.

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

Для каждого набора входных данных выведите $$$\texttt{Yes}$$$, если решение существует, в противном случае выведите $$$\texttt{No}$$$. Если ответ $$$\texttt{Yes}$$$, на следующих строках выведите описание построенных рёбер.

Выведите $$$n-1$$$ строк, обозначающих направленные рёбра. Каждая строка должна содержать два целых числа $$$x$$$ и $$$y$$$, обозначающих, что после направления рёбер существует направленное ребро $$$x\rightarrow y$$$. Если существует несколько решений, выведите любое из них.

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

Пример
Входные данные
11
4
1000
1111
1010
0001
4
1111
0111
0010
0111
4
0011
0111
0011
0001
4
1000
0110
0010
1111
4
1000
0110
1010
1111
5
10000
01011
00111
00010
00001
5
10000
11000
10101
10111
00001
5
10000
01101
00100
01110
10001
4
1100
0100
0011
0001
4
1110
0100
0010
0101
3
100
111
101
Выходные данные
Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1
Примечание

В первом наборе входных данных вершины $$$1$$$ и $$$4$$$ могут достигать только самих себя, вершина $$$2$$$ может достигать каждую вершину, вершина $$$3$$$ может достигать только вершины $$$1$$$ и $$$3$$$. Построенные рёбра удовлетворяют этому ограничению.

Для второго набора входных данных можно доказать, что подходящего решения не существует.