#488 Graph Construction

Loading problem...

Preparing the statement, recent submissions, and submit form.

DOJ/DOJ Contest/DOJ Contest 6

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

You are given a positive integer $N$ and nonnegative integers $D_1,D_2,\cdots,D_N$ , $X_1,X_2,\cdots,X_N$ .

Determine whether there exists a simple undirected graph $G$ with vertices $1,2,\cdots,N$ satisfying all of the following conditions. If one exists, construct any such graph. Note that $G$ does not have to be connected.

For every $i$ ( $1 \leq i \leq N$ ), the degree of vertex $i$ is $D_i$ .

Definition of a simple graph

A simple graph has no self-loops and has at most one edge between any two distinct vertices.

Input

The input is given from Standard Input in the following format:

$N$ $D_1\ D_2\ \cdots\ D_N$

Output

If no simple undirected graph satisfies the conditions, print $-1$ on the first line.

If such a graph exists, print it in the following format:

$M$ $u_1\ v_1$

Constraints

$1\le N\le 1\,000$ .
$0\le D_i\le N-1$ ().

Subtasks

#	Score	Constraints
1	17	$X_i = D_i$ ( $1 \leq i \leq N$ ).

Samples

Sample 1

Input

4
1 2 2 1
1 2 2 1

Output

Sample 2

Input

4
2 0 2 0
2 2 2 0

Output

-1

Editorial

View editorial