Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

D. Distance and Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Graph problems are popular in competitive programming, and problems related to distanceis and trees appear frequently. Let us start with some definitions.

A set is a collection of distinct elements. An undirected simple graph $$$G$$$ is a pair $$$(V,E)$$$, where $$$V$$$ is a set and $$$E$$$ is a set of unordered pairs of $$$V$$$'s elements. For a graph $$$G=(V,E)$$$, we call $$$V$$$ as $$$G$$$'s vertex set and $$$E$$$ as $$$G$$$'s edge set. Elements in $$$V$$$ are vertices, and elements in $$$E$$$ are edges.

Let $$$u$$$ and $$$v$$$ be vertices in $$$V$$$. A path from $$$u$$$ to $$$v$$$ of length $$$k$$$ is a sequence of edges $$$e_1,e_2,\dots,e_k\in E$$$ such that there exists a sequence of distinct vertices, $$$v_1,\dots,v_{k+1}$$$, satisfying the following conditions.

  • $$$u=v_1$$$.
  • $$$v=v_{k+1}$$$.
  • $$$e_i=\{v_i,v_{i+1}\}$$$.
If $$$p$$$ is a path from $$$u$$$ to $$$v$$$, then $$$u$$$ and $$$v$$$ are connected by $$$p$$$.

We can define distances and trees now. Given two vertices $$$u,v\in V$$$, the distance $$$\delta(u,v)$$$ from $$$u$$$ to $$$v$$$ is $$$0$$$ if $$$u=v$$$. If there exists a path from $$$u$$$ to $$$v$$$, then $$$\delta(u,v)$$$ is the minimum number of edges required to form a path from $$$u$$$ to $$$v$$$. Otherwise, $$$\delta(u,v)=\infty$$$. A tree is an undirected graph in which any distinct two vertices $$$u$$$ and $$$v$$$ are connected by exactly one path.

Danny gives you a sequence of non-negative integers $$$d_1,d_2,\dots,d_n$$$ and asks you to construct a tree $$$G_T=(V_T,E_T)$$$ satisfying the following conditions.

  • The vertex set $$$V_T=\{p_1,\dots,p_n\}$$$ is a set of points on a two dimensional Euclidean plane. For $$$1\le k\le n$$$, the coordinate of $$$p_k$$$ is $$$(\cos k\theta, \sin k\theta)$$$ where $$$\theta=\frac{2\pi}{n}$$$.
  • For any two distinct edges $$$\{p_a,p_b\}$$$ and $$$\{q_a,q_b\}$$$ in $$$E_T$$$, the line segments $$$\overline{p_ap_b}$$$ and $$$\overline{q_aq_b}$$$ do not intersect unless those two edges share a common vertex (that is, $$$\{p_a,p_b\}\cap\{q_a,q_b\}\neq\emptyset$$$).
  • There exists a vertex $$$r$$$ such that $$$\delta(r, p_k)=d_k$$$ for $$$1\le k \le n$$$. We call $$$r$$$ as the root of $$$G_T$$$.
If there exists such tree graph, please output the edge set $$$E_T$$$. Otherwise, output -1.
Input

The first line contains a positive integer $$$n$$$ indicating the number of vertices of the tree to be constructed. The second line contains $$$n$$$ non-negative integers $$$d_1,\dots,d_n$$$, the sequence given by Danny.

  • $$$2\le n\le 100000$$$
  • For $$$1\le k\le n$$$, $$$0\le d_k\le n-1$$$.
Output

If there does not exist such a tree $$$G_T$$$, output -1. Otherwise, output $$$n-1$$$ lines to represent the edge set $$$E_T$$$. The $$$i$$$-th line should contain two space-separated integers $$$u_i$$$ and $$$v_i$$$. The $$$i$$$-th edge in $$$E_T$$$ should be $$$\{p_{u_i},p_{v_i}\}$$$. If there are multiple solutions, you may output any of them.

Examples
Input
5
0 1 2 1 3
Output
-1
Input
5
1 1 0 1 1
Output
3 1
3 2
3 4
3 5