CF404C Restore Graph

Valera 曾经有一张无自环、无重边的无向连通图，包括 $n$ 个顶点。该图有一个有趣的性质：每个顶点至多有 $k$ 条相邻的边。为方便起见，我们假定这些顶点编号为 $1$ 到 $n$。 有一天，Valera 从某个顶点出发，计算了它到所有其他顶点的最短距离，并将这些距离写在了数组 $d$ 中。因此，数组元素 $d[i]$ 表示 Valera 选择的顶点到编号为 $i$ 的顶点的最短距离。 然后，发生了一件不可挽回的糟糕事情。Valera 丢失了原始的图。不过他还保留着数组 $d$。请你帮助 Valera 还原丢失的图。

第一行包含两个用空格分隔的整数 $n$ 和 $k$，$(1 \leq k < n \leq 10^{5})$。$n$ 表示原图的顶点数，$k$ 表示每个顶点至多有 $k$ 条相邻的边。 第二行包含 $d[1], d[2], \ldots, d[n]$，彼此用空格分隔，$(0 \leq d[i] < n)$。$d[i]$ 表示 Valera 选择的顶点到编号为 $i$ 的顶点的最短距离。

如果 Valera 记错了，没有符合条件的图存在，则第一行输出 $-1$。否则，第一行输出一个整数 $m$ $(0 \leq m \leq 10^{6})$——所还原出的图的边数。 接下来 $m$ 行，每行两个用空格分隔的整数 $a_{i}$ 和 $b_{i}$，$(1 \leq a_{i}, b_{i} \leq n; a_{i} \neq b_{i})$，表示存在一条连接 $a_{i}$ 和 $b_{i}$ 的边。图中不能出现自环和重边。如果有多种合法答案，你可以输出其中任意一种。

由 ChatGPT 5 翻译