HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Roads

Section problems

• Lawyers Council
• Math and Soldiers
• Many-coloured roads
• What about judges?
• Liars and Knights
• Interesting permutations
• Kovrov
• Points
• Roads
• Brackets
• Triangles
• String Multiplication
• Nice Floor
• Strange Numbers
• Factorial
• Boundary Troops
• ATM

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Павел Кузнецов, ПГУ.

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

Для отправки решений необходимо выполнить вход.

www.contester.ru