Поликарп учится в университете в группе, состоящей из n студентов (включая его самого). Все они зарегистрированы в социальной сети «ЕстьКонтакт!».
Не все из студентов одинаково общительны. Про каждого студента известна величина ai — максимальное количество сообщений, которые i-й студент согласен послать за сутки. Студент не может посылать сообщения сам себе.
Рано утром Поликарп узнал важную новость о том, что завтра состоится зачёт по программированию. По этой причине эту новость необходимо срочно сообщить всем одногруппникам с помощью личных сообщений.
Перед вами стоит задача составить такой план использования личных сообщений, чтобы:
- студент i послал не более ai сообщений (для всех i от 1 до n);
- все студенты узнали новость о зачёте (изначально она известна только Поликарпу);
- студент может сообщать новость другому только в том случае, если сам её знает.
Считайте, что все студенты пронумерованы различными целыми числами от 1 до n, а Поликарп всегда имеет номер 1.
В этой задаче вам не следует минимизировать количество сообщений, момент времени, когда все узнают о зачете или еще какой-либо другой параметр. Найдите любой способ использования личных сообщений, который удовлетворяет требованиям выше.
Выходные данные
Если сообщить всем студентам новость о зачёте невозможно, в первую строку выведите -1.
В противном случае, в первую строку выведите целое число k — количество сообщений, которые будут посланы. В каждой из следующих k строк выведите по два различных целых числа f и t, означающие, что студент номер f отправил сообщение с новостью студенту номер t. Все сообщения должны быть выведены в хронологическом порядке, то есть студент, отправляющий сообщение, уже должен знать новость. Допускается, что студенты могут получать повторные сообщения с новостью о зачёте.
Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере Поликарп (студент с номером 1) может отправить сообщение студенту с номером 2, который может после этого отправить сообщение студентам номер 3 и 4. Таким образом, все студенты узнают о зачёте.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 1 0
|
3
1 2
2 4
2 3
|
|
2
|
6
2 0 1 3 2 0
|
6
1 3
3 4
1 2
4 5
5 6
4 6
|
|
3
|
3
0 2 2
|
-1
|