Multiple Lamps
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, constructive algorithms, math, number theory

You have $$$n$$$ lamps, numbered from $$$1$$$ to $$$n$$$. Initially, all the lamps are turned off.

You also have $$$n$$$ buttons. The $$$i$$$-th button toggles all the lamps whose index is a multiple of $$$i$$$. When a lamp is toggled, if it was off it turns on, and if it was on it turns off.

You have to press some buttons according to the following rules.

- You have to press at least one button.
- You cannot press the same button multiple times.
- You are given $$$m$$$ pairs $$$(u_i, v_i)$$$. If you press the button $$$u_i$$$, you also have to press the button $$$v_i$$$ (at any moment, not necessarily after pressing the button $$$u_i$$$). Note that, if you press the button $$$v_i$$$, you don't need to press the button $$$u_i$$$.

You don't want to waste too much electricity. Find a way to press buttons such that at the end at most $$$\lfloor n/5 \rfloor$$$ lamps are on, or print $$$-1$$$ if it is impossible.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — the number of lamps and the number of pairs, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$). If you press the button $$$u_i$$$, you also have to press the button $$$v_i$$$. It is guaranteed that the pairs $$$(u_i, v_i)$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case:

- If there is no choice of buttons that makes at most $$$\lfloor n/5 \rfloor$$$ lamps on at the end, output a single line containing $$$-1$$$.
- Otherwise, output two lines. The first line should contain an integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of pressed buttons. The second line should contain $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n$$$) — the indices of the pressed buttons (in any order). The $$$b_i$$$ must be distinct, and at the end at most $$$\lfloor n/5 \rfloor$$$ lamps must be turned on.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you need to turn at most $$$\lfloor 4/5 \rfloor$$$ lamps on, which means that no lamp can be turned on. You can show that no choice of at least one button turns $$$0$$$ lamps on.

In the second test case, you can press buttons $$$3$$$, $$$5$$$, $$$1$$$, $$$2$$$.

- Initially, all the lamps are off;
- after pressing button $$$3$$$, the lamps whose index is a multiple of $$$3$$$ (i.e., $$$3$$$) are toggled, so lamp $$$3$$$ is turned on;
- after pressing button $$$5$$$, the lamps whose index is a multiple of $$$5$$$ (i.e., $$$5$$$) are toggled, so lamps $$$3$$$, $$$5$$$ are turned on;
- after pressing button $$$1$$$, the lamps whose index is a multiple of $$$1$$$ (i.e., $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$) are toggled, so lamps $$$1$$$, $$$2$$$, $$$4$$$ are turned on;
- after pressing button $$$2$$$, the lamps whose index is a multiple of $$$2$$$ (i.e., $$$2$$$, $$$4$$$) are toggled, so lamp $$$1$$$ is turned on.

This is valid because

- you pressed at least one button;
- you pressed all the buttons at most once;
- you pressed button $$$u_2 = 5$$$, which means that you had to also press button $$$v_2 = 1$$$: in fact, button $$$1$$$ has been pressed;
- at the end, only lamp $$$1$$$ is on.

In the third test case, pressing the buttons $$$8$$$, $$$9$$$, $$$10$$$ turns only the lamps $$$8$$$, $$$9$$$, $$$10$$$ on.

Example input:
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

Example output:
-1
4
3 5 1 2
3
8 9 10
1
5

Editorial: