← 返回题目列表

Codeforces · 300/B

B. 教练

中文机器翻译题面 查看原题

一位编程教练有 n 个学生要教。我们知道 n 可以被 3 整除。假设所有学生的编号都是从 1 到 n(包含 1 和 n)。

在大学编程锦标赛之前,教练希望将所有学生分成三人一组。对于一些学生,我们知道他们想加入同一个团队。此外,如果第 i 个学生希望与第 j 个学生在同一队,那么第 j 个学生也希望与第 i 个学生在同一队。教练希望各队能取得好的成绩,所以他希望满足以下条件:如果第 i 个学生想与第 j 个学生在同一队,则第 i 个学生和第 j 个学生必须在同一队。此外,很明显,每个学生都必须属于同一个团队。

帮助教练按照他想要的方式划分球队。

输入

输入的第一行包含整数 n 和 m (3 ≤ n ≤ 48, $$0 \leq m \leq \frac{n(n-1)}{2}$$。然后接下来的 m 行,每行包含一对整数 ai, bi (1 ≤ ai < bi ≤ n) — ai, bi 对表示编号为 ai 和 bi 的学生希望加入同一团队。

保证n能被3整除。保证每对ai,bi在输入中最多出现一次。

输出

如果所需的团队划分不存在,则打印数字-1。否则,打印 $$\frac{\pi}{3}$$ 行。每行打印三个整数 xi, yi, zi (1 ≤ xi, yi, zi ≤ n) — 第 i 队。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3 0

输出 #1

3 2 1

输入 #2

6 4
1 2
2 3
3 4
5 6

输出 #2

-1

输入 #3

3 3
1 2
2 3
1 3

输出 #3

3 2 1