CF746G New Roads

在Berland有 n 个城市，每一座城市都有一个单独的编号——在 1 到 n 范围内的一个整数，首都的编号是 1。现在，在Berland有一个极其严峻的问题：城市之间没有道路相连。 为了使得每个城市之间都有路相连，要在城市之间建造 n-1 条路。 在建造计划中一共有 t 个整数 a1，a2，...，at，t 等于首都与离首都最远的城市之间的距离。ai 表示一共有 ai 座城市与首都之间的距离是 i。两个城市之间的距离等于从一座城市到另一座城市所经过的道路的数量。 而且，除了首都以外一共会有 k 座城市仅与一条道路相连。这些城市是“死胡同”，它们没有经济吸引力。首都不算在内(即：即使只有一条道路与首都相连，首都也不算在“死胡同”里)。 你的任务是做出符合所有条件的计划，或是说明符合所有条件的计划是不存在的。

输入数据的第一行包括三个整数 n，t，k(2

如果不存在符合全部条件的方案，输出 -1。 否则，在第一行输出一个整数 n，表示城市个数。在接下来的 n-1 行中每一行包括两个整数，表示在这两个城市之间有道路相连。你可以以任意顺序输出。(注：此处任意顺序指道路顺序及每条道路所连接的的城市顺序均可以任意顺序输出) 如果有多组解，输出任意一组。记住首都的编号是 1。 Translated by @radish布団