У Пети было дерево, состоящее из n вершин, пронумерованных целыми числами от 1 до n. Но по стечению обстоятельств он своё дерево потерял.
Петя помнит о k вершинах из своего дерева информацию о расстоянии от каждой из них до всех n вершин дерева.
Перед вами стоит задача восстановить любое дерево, удовлетворяющее информации, которую помнит Петя, либо сообщить, что это невозможно.
Выходные данные
Если не существует подходящего дерева, выведите -1.
В противном случае, выведите в n - 1-й строке по два целых числа — концы очередного ребра. Вы можете выводить ребра и концы ребер в любом порядке. Вершины дерева пронумерованы от 1 до n.
Если ответов несколько, разрешается вывести любой из них.
Примечание
Иллюстрация к первому примеру:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
0 1 2 3 2
2 1 0 1 2
|
2 1
3 2
4 3
5 2
|
|
2
|
3 1
1 2 1
|
-1
|