CF1909E Multiple Lamps

[Kid2Will - Fire Aura](https://soundcloud.com/xgp/kid2will-fire-aura) ⠀ 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.

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 $ .

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.

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.