U509937 [COCI2024/2025 #2] Trokuti

给出了一个具有 $6N$ 个顶点和 $M$ 条边的无向图。图性质是它可以被划分为最多 $2N$ 个不相交的三角形。在图中找到 $N$ 个不相交的三角形。

**本题有多组数据。** 第一行一个整数 $T$，表示数据组数。 对于每一组数据： 第一行输入两个正整数 $N$ 和 $M$。 接下来 $M$ 行，每行输入两个正整数 $x$ 和 $y$，表示结点 $x$ 和 $y$ 有边。 **保证 $N$ 不会超过 $300$。**

输出 $N$ 行，每行三个正整数 $a$、$b$、$c$ 代表这三个结点构成的三角形。

【数据范围】 对于 $100\%$ 的数据，$1\le T\le 100$，$1\le N\le 300$，$1\le M\le 10^6$，$1\le x,y\le 6N$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $13$ | $M=6N$ | | $2$ | $18$ | $N=3,T=1$ | | $3$ | $18$ | $N=6,T=1$ | | $4$ | $71$ | 无 |