刚交了个假做法, 就是把每个节点按度数降序排序之后输出前$n\over3$个点编号(升序排序后输出)

我们可以构造这样的图

9 24
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
2 1
2 3
6 3
4 1
2 4
4 5
4 6
7 9
8 9
9 3
9 2
9 5
9 4
9 6
1 7
1 8

画成图就是

我们发现$1$和$9$的度是$7$, $7$和$8$的度是$2$, 其余点的度是$6$

按这样的做法就会输出1 x 9, 其中$x\in\{2,3,4,5,6\}$

而$1$和$9$没有边, 所以这是错误答案

虽然改成随机化取点多交几发也能过