高效地计算给定无向简单图 $G$ 中指定子图 $H$ 的副本数量 $k(H, G)$ 可能具有挑战性。例如，对于一个 $n$ 个节点的图 $G$，计算 $k(C_3, G)$ 时，如果你的算法是“组合式”的，那么对于任何常数 $\delta > 0$，可能需要 $\Omega(n^{3-\delta})$ 的时间。我们用 $C_k$ 表示长度为 $k$ 的简单环。当指定的子图 $H$ 变得更加复杂时，计算 $k(H, G)$ 所需的运行时间通常会迅速增长。

图 1：金字塔 $P$ 是一个由 5 个节点和 8 条边组成的无向简单图，如上图所示。不难验证 $k(C_3, P) = 4$，$k(C_4, P) = 5$ 且 $k(C_5, P) = 4$。

Bob 是一位研究人员，他需要检测给定图网络中的罕见事件。例如，在一个 $n$ 个节点的随机图 $R$ 中，每条边以 $1/2$ 的概率存在，其 $k(C_3, R)$ 的期望值为 $\binom{n}{3}/8$。如果他发现 $k(C_3, R)$ 与期望值有显著偏差，他可能会得出结论：$R$ 不太可能是通过上述过程生成的随机图。Bob 正在研究 $n$ 个节点图中 $k(C_3, G)$ 与 $k(C_5, G)$ 之间的相关性。有一个猜想认为，对于任何 $n$ 个节点的无向简单图 $G$，如果 $$k(C_3, G) \geq \frac{5}{4} \left( n^{1.5} + \frac{n}{2} \right),$$ 则 $k(C_5, G) > 0$。你的任务是实现一个高效的算法来验证该猜想是否错误。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。接下来是各个测试用例。对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，中间用空格隔开。$n$ 表示给定无向简单图 $G$ 的节点数，$m$ 表示后续行中给出的 $C_3$ 的数量。$G$ 中的边集恰好是所给出的所有 $C_3$ 中边的并集。接下来的 $m$ 行，每行包含三个不同的整数 $x$、$y$ 和 $z$，中间用空格隔开，表示 $G$ 中的一个 $C_3$，其端点为 $x$、$y$ 和 $z$。$G$ 中的节点编号从 1 到 $n$。

输出格式

对于每个测试用例，如果 $k(C_5, G) > 0$，则在一行中按顺序输出 $G$ 中任意一个五边形的 5 个节点标识符（即输出一组节点 $x_1 x_2 x_3 x_4 x_5$，使得对于每个 $1 \leq i \leq 4$，$(x_i, x_{i+1})$ 是一条边，且 $(x_1, x_5)$ 也是一条边；如果存在多个解，输出其中任意一个）；否则，在一行中输出“-1”。

数据范围

• $1 \leq t \leq 10$
• $1 \leq n \leq 10^4$
• $m = \lceil 5/4(n^{1.5} + (n/2)) \rceil$

样例

输入 1

1
7 28
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 4
1 3 5
1 3 6
1 3 7
1 4 5
1 4 6
1 4 7
1 5 6
1 5 7
1 6 7
2 3 4
2 3 5
2 3 6
2 3 7
2 4 5
2 4 6
2 4 7
2 5 6
2 5 7
2 6 7
3 4 5
3 4 6
3 4 7

输出 1

1 2 3 4 7