您有 $$$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$$$ 灯。
示例
输入 #1
4 4 0 5 2 4 1 5 1 15 9 7 8 8 9 9 10 10 9 11 1 12 2 13 3 14 4 15 5 5 4 1 2 2 3 3 4 4 5
输出 #1
-1 4 3 5 1 2 3 8 9 10 1 5
注意
在第一个测试用例中,最多需要打开 $$$\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$$$。