题目背景

译自 COCI 2024/2025 #2 T5。$\texttt{4s,0.5G}$。满分为 $120$。

题目描述

给定一张 $6n$ 个节点 $m$ 条边的无向图。保证这张图可以被划分成 $2n$ 个 $K_3$（大小为 $3$ 的完全图）。

求出这张图中的 $n$ 个 $K_3$，不能有重复顶点。

输入格式

本题单个测试点内有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。

接下来描述 $T$ 组数据：

第一行，两个整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示图中的一条无向边。

输出格式

每组数据输出 $n$ 行，每行三个整数，表示 $K_3$ 的三个顶点。

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

1 2 3

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

1 6 13
3 7 9
4 5 8

提示

对于 $100\%$ 的数据，保证：

• $1\le T\le 100$；
• $1\le n,\sum n\le 300$；
• $0\le m\le 10^6$；
• $1\le u,v\le 6n$。

• 特殊性质 A：$m=6n$。
• 特殊性质 B：$T=1$。