|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.
Long ago the Byteland kingdom had a wide system of
roads. Unfortunately, that was a long time ago,
and now this system does not exist. Citizens can't
even remember, what towns were connected with their
own town by roads. The only thing they do remember
is the number of roads, that this town once had.
The new king wants to restore the road system and
asked you to design the road scheme. You have to
find out, what towns should be connected by roads,
so that the following requirements are met:
1. From each town where should be a path to any
other town, and there cannot be more than one
path between two towns.
2. Each town should have the same number of roads
it had long time ago. Citizens of each town
remember this number.
Get to work, the king does not like to wait!
Input
In the first line an integer number N is
written - number of towns in Byteland
(2 ≤ N ≤ 10000). In the next N
lines follow numbers Ci - number of roads,
that i-th town once had
(1 ≤ Ci ≤ 10000).
All towns are numbered from 1 to N.
Output
If the required road system does not exist, output -1.
Otherwise write in first line the number of roads
required to be built. In next lines write the road
descriptions one per line in arbitrary order. Each road
is described by numbers of towns it connects, in
increasing order. All roads are two-way. No road can
connect a town to itself. Two towns cannot be connected
by more than one road. If there are several
solutions, output any of them.
|
Input 1
|
Output 1
|
Input 2
|
Output 2
|
Input 3
|
Output 3
|
2
1
1
|
1
1 2
|
3
1
1
1
|
-1
|
4
1
1
3
1
|
3
1 3
2 3
3 4
|
Для отправки решений необходимо выполнить вход.
|