考虑一个无向图。如果满足以下条件，则称顶点对 $(U, V)$ 是分离的：

• 存在两条从 $U$ 到 $V$ 的简单路径，它们的长度之差至少为 $2$。注意，简单路径是指路径上的所有顶点都互不相同的路径。

如果存在至少一个其他顶点 $V$，使得顶点对 $(U, V)$ 是分离的，则称顶点 $U$ 是可分离的。

给定三个整数 $N, M$ 和 $K$。请构造任意一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图，使得该图恰好有 $K$ 个可分离的顶点。如果不存在这样的图，输出 $-1$。

输入格式

输入格式如下：

T
N M K
...

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $2 \le N \le 2 \times 10^5$
• $N - 1 \le M \le \min \left(2 \times 10^5, \frac{N \cdot (N - 1)}{2}\right)$
• $0 \le K \le N$
• 保证所有测试用例中 $N$ 的总和与 $M$ 的总和均不超过 $2 \times 10^5$。

输出格式

对于每个测试用例：

• 如果无法构造出满足条件的图，输出单个整数 $-1$。
• 否则，输出 $M$ 行。其中第 $i$ 行应包含两个整数 $U_i$ 和 $V_i$（$1 \le U_i, V_i \le N, U_i \neq V_i$），表示第 $i$ 条边的两个端点。该图必须是简单图（即无自环、无重边）、连通图，且恰好有 $K$ 个可分离的顶点。

如果存在多个满足条件的图，输出其中任意一个即可。

样例

输入样例 1

3
2 1 1
3 2 0
4 5 4

输出样例 1

-1
1 2
2 3
1 2
2 3
3 4
1 4
1 3

说明

测试用例 1：对于 $N = 2$ 且 $M = 1$，唯一可能的图是单条边，它有 $0$ 个可分离的顶点。

测试用例 2：我们需要 $0$ 个可分离的顶点，给出的图满足这一条件。

测试用例 3：所有顶点都是可分离的。例如，顶点 $1$ 是可分离的，因为对于顶点对 $(1, 2)$，存在两条路径 $1 \to 2$ 和 $1 \to 4 \to 3 \to 2$，它们的长度相差 $2$。