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)\).
Помогите ему восстановить структуру дерева или сообщите, что дерева, удовлетворяющего всем ограничениям, не существует.
Выходные данные
Для каждого набора входных данных:
- выведите No, если искомого дерева не существует;
- иначе в первой строке выведите Yes. Затем выведите \(n-1\) строк. Каждая из них должна содержать два целых числа \(x,y\) (\(1\le x,y\le n\)), означающих ребро между вершинами \(x\) и \(y\) в дереве. Если существуют несколько решений, выведите любое из них.
При выводе Yes и No вы можете выводить каждый символ в любом регистре (верхнем или нижнем).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|