给定一个包含 $N$ 个顶点的图 $G$，顶点编号为 $1, 2, \dots, N$。初始时，$G$ 没有边。 你将向 $G$ 中添加 $M$ 条无向边。图的最终形态是预先确定的，第 $i$ 条要添加的边（$1 \le i \le M$）连接顶点 $u_i$ 和 $v_i$。我们将此称为边 $i$。保证最终形成的图是简单图。

请确定是否存在一个 $(1, 2, \dots, M)$ 的排列 $(P_1, P_2, \dots, P_M)$ 满足以下条件，如果存在，请给出一个示例。

条件

你必须能够通过以下过程将所有 $M$ 条边添加到 $G$ 中：

• 对于 $i = 1, 2, \dots, M$，重复以下步骤：
  1. 如果 $G$ 中已经存在包含顶点 $u_{P_i}$ 或顶点 $v_{P_i}$ 的环，则条件不满足，过程结束。
  2. 将边 $P_i$（连接 $u_{P_i}$ 和 $v_{P_i}$ 的无向边）添加到 $G$ 中。

给定 $T$ 组测试数据；请解决每一组数据。

输入格式

输入格式如下：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

其中 $case_i$ ($1 \le i \le T$) 表示第 $i$ 组测试数据。每组测试数据的格式如下：

$N \ M$ $u_1 \ v_1$ $u_2 \ v_2$ $\vdots$ $u_M \ v_M$

• 所有输入值均为整数。
• $1 \le T \le 2000$
• 对于每组测试数据：
  • $2 \le N \le 4000$
  • $1 \le M \le 4000$
  • $1 \le u_i, v_i \le N$ ($1 \le i \le M$)
  • 添加所有给定边后形成的图是简单图。
• 所有测试数据的 $N$ 之和不超过 $4000$。
• 所有测试数据的 $M$ 之和不超过 $4000$。

输出格式

对于每组测试数据，如果存在满足条件的排列 $(P_1, P_2, \dots, P_M)$，则输出该排列 $P$，数字间用空格分隔。如果不存在这样的排列，则输出 -1。

样例

样例输入 1

1
4 4
1 2
2 3
3 4
4 2

样例输出 1

1 4 3 2

样例输入 2

4
4 5
1 2
2 3
3 4
3 1
1 4
5 3
1 2
2 3
3 4
9 10
3 5
1 8
5 8
4 9
6 7
7 9
1 2
1 4
2 4
4 6
8 10
1 4
3 8
2 5
3 4
1 5
5 8
2 8
5 7
4 5
3 7

样例输出 2

-1
1 2 3
1 2 3 4 8 9 10 7 6 5
-1

说明

在第一个样例中，给定图的形状如下：

如果我们按顺序 $P = (1, 2, 3, 4)$ 添加边，条件满足，过程如下：

因此，“1 2 3 4”是一个有效的输出。

然而，如果我们按顺序 $P = (2, 3, 4, 1)$ 添加边，在添加边 1 之前，已经创建了一个包含顶点 2 的环，因此条件不满足：

其他有效的输出包括 $P = (1, 4, 3, 2)$ 或 $P = (2, 4, 1, 3)$。 注意，图不一定是连通的。