Pinely Round 3 (Div. 1 + Div. 2) |
---|
Finished |
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 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:
44 05 24 15 115 97 88 99 1010 911 112 213 314 415 55 41 22 33 44 5
-1 4 3 5 1 2 3 8 9 10 1 5
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$$$.
This is valid because
In the third test case, pressing the buttons $$$8$$$, $$$9$$$, $$$10$$$ turns only the lamps $$$8$$$, $$$9$$$, $$$10$$$ on.
Name |
---|