CF1909E Multiple Lamps

[Kid2Will - Fire Aura](https://soundcloud.com/xgp/kid2will-fire-aura) ⠀ 你有 $n$ 盏灯，编号从 $1$ 到 $n$。最开始，所有的灯都是关闭的。 你还有 $n$ 个按钮。第 $i$ 个按钮会切换所有编号为 $i$ 的倍数的灯的状态。当一盏灯被切换时，如果它原来是关的就会被打开，如果原来是开的就会被关闭。 你需要按照以下规则按下若干按钮： - 至少要按下一个按钮。 - 不能多次按同一个按钮。 - 给定 $m$ 对 $(u_i, v_i)$。如果你按下按钮 $u_i$，你也必须按下按钮 $v_i$（可以在任意时刻按下，不一定要在 $u_i$ 之后）。注意，如果你按下按钮 $v_i$，则不需要按下按钮 $u_i$。 你不想浪费太多电。请找出一种按按钮的方法，使得最后最多只有 $\lfloor n/5 \rfloor$ 盏灯是亮着的；如果无法做到，输出 $-1$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq m \leq 2 \cdot 10^5$），分别表示灯的数量和约束对的数量。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$）。如果你按下按钮 $u_i$，你也必须按下按钮 $v_i$。保证所有的 $(u_i, v_i)$ 对都是不同的。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例： - 如果不存在一种按钮选择方式，使得最后亮着的灯不超过 $\lfloor n/5 \rfloor$ 盏，输出一行 $-1$。 - 否则，输出两行。第一行包含一个整数 $k$（$1 \le k \le n$），表示按下的按钮数量。第二行包含 $k$ 个整数 $b_1, b_2, \dots, b_k$（$1 \le b_i \le n$），表示按下的按钮编号（顺序任意）。$b_i$ 必须互不相同，并且最后亮着的灯数量不超过 $\lfloor n/5 \rfloor$。

在第一个测试用例中，你需要让最多 $\lfloor 4/5 \rfloor$ 盏灯亮着，也就是不能有任何灯亮着。可以证明，至少按下一个按钮时无法让 $0$ 盏灯亮着。 在第二个测试用例中，你可以按下按钮 $3$、$5$、$1$、$2$。 - 最初，所有灯都是关的； - 按下按钮 $3$ 后，编号为 $3$ 的倍数的灯（即 $3$ 号灯）被切换，$3$ 号灯亮； - 按下按钮 $5$ 后，编号为 $5$ 的倍数的灯（即 $5$ 号灯）被切换，此时 $3$、$5$ 号灯亮； - 按下按钮 $1$ 后，编号为 $1$ 的倍数的灯（即 $1$、$2$、$3$、$4$、$5$ 号灯）被切换，此时 $1$、$2$、$4$ 号灯亮； - 按下按钮 $2$ 后，编号为 $2$ 的倍数的灯（即 $2$、$4$ 号灯）被切换，此时 $1$ 号灯亮。 这是合法的，因为： - 你至少按下了一个按钮； - 每个按钮最多按下一次； - 你按下了按钮 $u_2=5$，因此也必须按下按钮 $v_2=1$，实际上 $1$ 号按钮已经被按下； - 最后只有 $1$ 号灯是亮着的。 在第三个测试用例中，按下按钮 $8$、$9$、$10$，只有 $8$、$9$、$10$ 号灯亮着。 由 ChatGPT 4.1 翻译