У Валеры был неориентированный связный граф без петель и кратных ребер, состоящий из n вершин. Граф обладал интересным свойством: из каждой его вершины исходило не более k ребер. Для удобства будем считать, что вершины графа пронумерованы целыми числами от 1 до n.
Как-то раз Валера посчитал кратчайшие расстояния от одной из вершин графа до всех остальных и выписал их в массив d. Таким образом, элемент d[i] массива обозначает кратчайшее расстояние от выбранной Валерой вершины до вершины с номером i.
Вскоре произошло неисправимое. Валера потерял исходный граф. Однако, у него остался массив d. Помогите ему восстановить утерянный граф.
Выходные данные
Если Валера ошибся в записях и требуемого графа не существует, выведите в первой строке число -1. Иначе, в первой строке выведите целое число m (0 ≤ m ≤ 106) — количество ребер в найденном графе.
В каждой из следующих m строк выведите через пробел два целых числа ai и bi (1 ≤ ai, bi ≤ n; ai ≠ bi), обозначающих ребро, соединяющее вершины с номерами ai и bi. Граф не должен содержать петель и кратных ребер. Если возможных ответов несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 1 1
|
3
1 2
1 3
3 2
|
|
2
|
4 2
2 0 1 3
|
3
1 3
1 4
2 3
|
|
3
|
3 1
0 0 0
|
-1
|