给定一个包含 $6 \cdot N$ 个顶点和 $M$ 条边的无向图。该图的一个额外性质是它可以被划分为 $2 \cdot N$ 个不相交的三角形。

请在图中找出 $N$ 个不相交的三角形。

输入格式

第一行包含一个自然数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 接下来是 $T$ 组数据。 每组数据的第一行包含自然数 $N$ 和 $M$ ($1 \le N \le 300, 0 \le M \le 10^6$)。 接下来的 $M$ 行，每行包含两个自然数 $x$ 和 $y$ ($1 \le x, y \le 6 \cdot N$)，表示顶点 $x$ 和 $y$ 之间有一条边。 所有测试用例中 $N$ 的总和不超过 $300$。

输出格式

对于每个测试用例，输出 $N$ 行，每行包含三个自然数 $a, b, c$ ($1 \le a, b, c \le 6 \cdot N$)，表示顶点 $a, b, c$ 构成一个三角形。

子任务

样例

样例输入 1

1
1 6
1 2
2 3
1 3
4 5
4 6
5 6

样例输出 1

1 2 3

样例输入 2

1
3 26
4 7
4 9
7 9
4 5
4 8
5 8
4 12
4 18
12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 17

样例输出 2

1 6 13
3 7 9
4 5 8