#P18026. Vertex Separation

Vertex Separation

Vertex Separation

在一个无向图中,如果顶点 U,VU,V 之间存在两条简单路径,且这两条路径的长度之差至少为 22,则称点对 (U,V)(U,V) 可分离。

简单路径中不能重复经过顶点,路径长度指边数。两条路径不要求边不相交,也不要求内部顶点不相交。

如果对某个顶点 UU,存在另一个顶点 VV 使得 (U,V)(U,V) 可分离,则称 UU 是一个可分离顶点。

给定 N,M,KN,M,K,构造一个有 NN 个顶点、MM 条边的简单连通无向图,使其中恰好有 KK 个可分离顶点。顶点编号为 11 到 NN。简单图不能含自环和重边。

如果不存在这样的图,输出 -1。若存在多个合法图,输出任意一个即可。

输入格式

第一行一个整数 TT。接下来 TT 行,每行三个整数 N,M,KN,M,K,表示一组数据。

输出格式

对于每组数据:

  • 无解时,输出一行 -1。
  • 有解时,输出 MM 行,每行两个整数 Ui,ViU_i,V_i,描述一条边。不要额外输出 YES 或边数。

数据范围

1≤T≤1051\le T\le10^5,2≤N≤2×1052\le N\le2\times10^5,

$$N-1\le M\le\min\left(2\times10^5,\frac{N(N-1)}2\right),\qquad0\le K\le N.$$

所有测试用例的 NN 之和不超过 2×1052\times10^5,MM 之和也不超过 2×1052\times10^5。

样例 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