小青鱼有一个包含 $n$ 个顶点和 $m$ 条边的连通简单无向图。顶点从 $1$ 到 $n$ 进行编号。

小青鱼想要选择该图的一棵生成树，并以顶点 $1$ 为根。在树确定根之后，每个顶点与其他一些顶点之间就存在祖先-后代关系。

以下伪代码描述了如何从选定的生成树中获得有根树：

Algorithm 1 Rooting the chosen spanning tree
1: procedure DFS(vertex x, vertex p)
2: Mark x as visited
3: Set the parent of x to p
4: for each vertex y adjacent to x in the chosen spanning tree do
5: if y != p then
6: DFS(y, x)
7: end if
8: end for
9: Finish vertex x
10: end procedure
11: procedure ROOT-TREE
12: Mark all vertices as unvisited
13: DFS(1, 0)
14: end procedure

对于两个顶点 $u$ 和 $v$，如果 $u$ 在选定的生成树中处于从根节点 $1$ 到 $v$ 的路径上，则称顶点 $u$ 是顶点 $v$ 的祖先。一个顶点也被认为是它自己的祖先。

原图中未被包含在生成树中的边，如果其一个端点在有根生成树中是另一个端点的祖先，则被称为返祖边（back edge）。

小青鱼希望返祖边的数量恰好为 $c$。请构造这样一棵生成树。

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n, m, c$ ($1 \le n \le 10^6$, $n - 1 \le m \le \frac{n(n-1)}{2}$, $0 \le c \le m - n + 1$)。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示顶点 $u$ 和 $v$ 之间的一条无向边。输入中的第 $i$ 条边编号为 $i$。每个测试用例中的图都是简单且连通的，且保证至少存在一棵满足条件的生成树。

保证所有测试用例中 $n$ 的总和不超过 $10^6$，且 $m$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，在一行中输出 $n - 1$ 个互不相同的整数：被选入生成树的边的编号。

所选的边必须构成一棵以顶点 $1$ 为根的生成树，且其返祖边的数量恰好为 $c$。

如果存在多个可行解，输出其中任意一个即可。

样例

样例输入 1

2
5 10 0
4 1
3 4
2 1
5 3
3 2
1 5
4 2
3 1
2 5
4 5
5 10 3
1 4
3 4
2 4
5 1
2 3
3 5
1 2
2 5
1 3
4 5

样例输出 1

1 3 6 8
1 2 3 10