P11433 [COCI 2024/2025 #2] 三角 / Trokuti
题目背景
译自 [COCI 2024/2025 #2](https://hsin.hr/coci/) 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$ 的三个顶点。
说明/提示
对于 $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$。
| 子任务编号 | $n,\sum n$ | 特殊性质 | 得分 |
| :--: | :--: | :--: |:--: |
| $ 1 $ | $\le 300$ | A | $ 13 $ |
| $ 2 $ | $=3$ | B | $ 18 $ |
| $ 3 $ | $=6$ | B | $ 18 $ |
| $ 4 $ | $\le 300$ | | $ 71 $ |
- 特殊性质 A：$m=6n$。
- 特殊性质 B：$T=1$。