#P18026. Vertex Separation
Vertex Separation
Vertex Separation
在一个无向图中,如果顶点 之间存在两条简单路径,且这两条路径的长度之差至少为 ,则称点对 可分离。
简单路径中不能重复经过顶点,路径长度指边数。两条路径不要求边不相交,也不要求内部顶点不相交。
如果对某个顶点 ,存在另一个顶点 使得 可分离,则称 是一个可分离顶点。
给定 ,构造一个有 个顶点、 条边的简单连通无向图,使其中恰好有 个可分离顶点。顶点编号为 到 。简单图不能含自环和重边。
如果不存在这样的图,输出 -1。若存在多个合法图,输出任意一个即可。
输入格式
第一行一个整数 。接下来 行,每行三个整数 ,表示一组数据。
输出格式
对于每组数据:
- 无解时,输出一行
-1。 - 有解时,输出 行,每行两个整数 ,描述一条边。不要额外输出
YES或边数。
数据范围
,,
$$N-1\le M\le\min\left(2\times10^5,\frac{N(N-1)}2\right),\qquad0\le K\le N.$$所有测试用例的 之和不超过 , 之和也不超过 。
样例 1
输入
3
2 1 1
3 2 0
4 5 4
输出
-1
1 2
2 3
1 2
2 3
3 4
1 4
1 3