CF300B Coach

一位编程教练有 $n$ 名学生要教。我们知道 $n$ 可以被 $3$ 整除。假设所有学生的编号为 $1$ 到 $n$。 在大学编程锦标赛之前，教练希望将所有学生分成每组三人的小组。已知有一些学生对，希望和某些同学分在同一组。此外，如果第 $i$ 个学生希望和第 $j$ 个同组，则第 $j$ 个学生也希望和第 $i$ 个同组。为了让小组取得好成绩，教练要求：若第 $i$ 个学生希望与第 $j$ 个同组，则他们必须在同一组。同时，显然每个学生必须恰好在一支小组中。 请帮助教练按照他的期望将学生分组。

输入的第一行为两个整数 $n$ 和 $m$，其中 $3 \leq n \leq 48$，$n$ 可以被 $3$ 整除。接下来 $m$ 行，每行包含一对整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq n)$，表示编号为 $a_i$ 和 $b_i$ 的学生希望分在同一组。 保证 $n$ 可以被 $3$ 整除。保证每对 $a_i, b_i$ 在输入中最多出现一次。

如果无法完成分组，输出 $-1$。否则，输出 $n/3$ 行，每行输出三个整数 $x_i, y_i, z_i$ $(1 \leq x_i, y_i, z_i \leq n)$，表示第 $i$ 组的成员编号。 如果有多种分组方案，可以输出任意一种。

由 ChatGPT 5 翻译