CF1239F Swiper, no swiping!

我是地图，我是地图！我是地图！！！ 地图 为了迎接新的冒险，Boots 想要做一件好事。经过与地图和背包的讨论，他们决定送给 Dora 一个连通图。经过长时间的挑选，Boots 选出了 $t$ 个 Dora 可能会喜欢的图的方案。然而狐狸 Swiper 想要破坏他的计划。 Swiper 知道，Dora 现在只能数到 $3$，于是他想出了如下主意。他想要偷走一些非空的顶点集合，使得 Dora 不会注意到损失。他决定偷走一些非空的顶点集合，使得在删除被偷走的顶点及其相邻的边后，所有剩余顶点的度数对 $3$ 取模后都不发生变化。顶点的度数是指与其相连的边的数量。如果把所有顶点都偷走会太可疑，所以 Swiper 需要另想办法。 Boots 认为，绝不能让这场犯罪得逞。然而他们担心自己无法独自应对。因此 Boots 决定向你寻求帮助。请你判断，对于每个图的方案，Swiper 是否能够完成盗窃。

第一行包含一个整数 $t$（$1 \le t \le 100\,000$），表示图的方案数。 每个方案的第一行包含两个整数 $n$、$m$（$1 \le n \le 500\,000$，$0 \le m \le 500\,000$），分别表示图的顶点数和边数。 接下来 $m$ 行，每行包含两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$），表示一条连接顶点 $a_i$ 和 $b_i$ 的边。 保证每个图都是连通的，且没有重边和自环。 保证所有方案中 $n$ 的总和不超过 $500\,000$，$m$ 的总和也不超过 $500\,000$。 每个图的描述之间用一个空行隔开。

对于每个方案： - 如果存在满足条件的答案，输出 "Yes"，然后输出答案。第一行输出一个整数 $c$（$1 < c < n$），表示 Crook 可以偷走的顶点数。下一行输出 $c$ 个不同的整数，表示这些顶点的编号，顺序任意。 - 否则输出 "No"。 如果有多种合法的偷顶点方式，输出任意一种即可。 注意，不要求偷走的顶点数最大。

下图展示了样例测试中的第三个方案。Crook 可以偷走的顶点集合用粗体表示。  由 ChatGPT 4.1 翻译