26308번 - Distance and Tree 스페셜 저지다국어

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 ∈ 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 ∈ V$, the distance $δ(u, v)$ from $u$ to $v$ is $0$ if $u = v$. If there exists a path from $u$ to $v$, then $δ(u, v)$ is the minimum number of edges required to form a path from $u$ to $v$. Otherwise, $δ(u, v) = ∞$. 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 ≤ k ≤ n$, the coordinate of $p_k$ is $(\cos{kθ}, \sin{kθ})$ where $θ = 2π n$.
• For any two distinct edges $\{p_a, p_b\}$ and $\{q_a, q_b\}$ in $E_T$, the line segments $p_ap_b$ and $q_aq_b$ do not intersect unless those two edges share a common vertex (that is, $\{p_a, p_b\}∩\{q_a, q_b\} ≠ ∅$).
• There exists a vertex $r$ such that $δ(r, p_k) = d_k$ for $1 ≤ k ≤ 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$.

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.

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.

• $2 ≤ n ≤ 100000$
• For $1 ≤ k ≤ n$, $0 ≤ d_k ≤ n - 1$.