F. Восстановление дерева
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Fishingprince любит деревья. Дерево — это связный неориентированный граф без циклов.

У Fishingprince'а есть дерево на $$$n$$$ вершинах. Его вершины пронумерованы числами от $$$1$$$ до $$$n$$$. Пусть $$$d(x,y)$$$ равно длине кратчайшего расстояния между вершинами $$$x$$$ и $$$y$$$, если считать длину каждого ребра равной $$$1$$$.

К сожалению, Fishingprince потерял своё дерево. Тем не менее какая-то информация о нём сохранилась. А именно, для каждой тройки чисел $$$x,y,z$$$ ($$$1\le x<y\le n$$$, $$$1\le z\le n$$$) известно, выполнено ли равенство $$$d(x,z)=d(y,z)$$$.

Помогите ему восстановить структуру дерева или сообщите, что дерева, удовлетворяющего всем ограничениям, не существует.

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

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

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$2\le n\le 100$$$) — количество вершин в дереве.

Далее следует $$$n-1$$$ строк. Из этих $$$n-1$$$ строк $$$i$$$-я строка содержит $$$n-i$$$ последовательностей символов длины $$$n$$$, состоящих из 0 и 1. Если $$$k$$$-й символ в $$$j$$$-й последовательности $$$i$$$-й строки равен 0, то $$$d(i,k)\ne d(i+j,k)$$$; если же $$$k$$$-й символ в $$$j$$$-й последовательности $$$i$$$-й строки равен 1, то $$$d(i,k)=d(i+j,k)$$$.

Гарантируется, что в каждом тесте:

  • есть не более $$$2$$$ наборов входных данных с $$$n>50$$$;
  • есть не более $$$5$$$ наборов входных данных с $$$n>20$$$.
Выходные данные

Для каждого набора входных данных:

  • выведите No, если искомого дерева не существует;
  • иначе в первой строке выведите Yes. Затем выведите $$$n-1$$$ строк. Каждая из них должна содержать два целых числа $$$x,y$$$ ($$$1\le x,y\le n$$$), означающих ребро между вершинами $$$x$$$ и $$$y$$$ в дереве. Если существуют несколько решений, выведите любое из них.

При выводе Yes и No вы можете выводить каждый символ в любом регистре (верхнем или нижнем).

Пример
Входные данные
5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000
Выходные данные
Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5