SP296 TWORK - Teamwork is Crucial

在中世纪晚期，比特兰大学就像当时其他的大学一样，是一个阴郁之地。哲学家在这里苦思生命的真谛，神学家同样深思且与哲学家争论不休，而炼金术士则在寻找黄金的过程中研制出各种新型的腐蚀性绿色洗发水。校长最担心的是，员工中没人能找到一条赚钱的途径。他向人力资源总监抱怨这一困境，总监便提出了一个简单明了的理论。他认为，科研效率低下是由于科学家各自为战，而大力提倡团队合作能带来奇迹。 总监计划将每位科学家分配到一个三人小组中，然后让组员们选出一个作为组长。然而，这正是难题所在。每位科学家只愿意接受他自己或是自己的老熟人担任组长，绝不允许陌生人担任这个职务。因此，在组建小组时，必须确保每个小组中至少有一个被所有成员认可的合适组长人选。 虽然大学中的每个人通过不同层级的熟人间接地认识其他人，但每位科学家的直接熟人数却很少——要么有 2 个，要么有 3 个。即便如此，也应该能为绝大多数科学家分配到合适的小组。现在，这项繁重的任务落到了你这位临时大学算法专家的肩上。

输入首先包含一个整数 $t$，表示测试用例的数量（$t \leq 100$）。接下来是 $t$ 个测试用例。 每个测试用例的第一行为两个整数 $n$ 和 $m$（$4 \leq n \leq m \leq 20000$，且 $n$ 能被 4 整除），表示科学家的总人数和熟人关系的总数。接下来的 $m$ 行中，每行包含两个整数 $a_i$ 和 $b_i$，表示科学家 $a_i$ 和 $b_i$ 是彼此的直接熟人（$1 \leq a_i, b_i \leq n$，每个科学家只有 2 或 3 个熟人）。熟人关系是互相的。

针对每个测试用例，首先输出一个整数 $k$，表示你形成的小组数量。接下来的 $k$ 行中，每行输出 3 个整数，代表相应小组中科学家的编号。 如果在某个测试用例中，超过 25% 的科学家不能被有效地分配到小组中，则你的解决方案将被视为不正确。 **本翻译由 AI 自动生成**