C. Chain Reaction
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Our doubts are traitors, and make us lose the good we oft might win, by fearing to attempt.
— William Shakespeare, Measure for Measure

Feeling a little bored, WX decided to play a game called "Chain Reaction".

The game is based on a classic question "Toggle Lamps". There are $$$n$$$ lamps in total. Initially, all of them are turned off.

Also, there are $$$n$$$ buttons. If you push the $$$i$$$-th button, then all lamps $$$x$$$ such that $$$x$$$ is a multiple of $$$i$$$ will be toggled.

You have to push some button according to the following rules:

  1. You need to push at least one button;
  2. A button can be pushed only once;
  3. You are given $$$m$$$ pairs $$$(u_i, v_i)$$$, if you push the button $$$u_i$$$, then you have to push the button $$$v_i$$$ (at any moment, not necessarily after pushing the button $$$u_i$$$). Note that if you push the button $$$v_i$$$, then you don't have to push the button $$$u_i$$$ for the given pair $$$(u_i, v_i)$$$.

Find a way to push buttons such that at most $$$\lfloor \sqrt{n} \rfloor$$$ lamps$$$^{\dagger}$$$ are on, or print $$$-1$$$ if it is impossible.

$$$^{\dagger}$$$ $$$\lfloor x \rfloor$$$ denotes the round down operation.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$, denoting the number of test cases.

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

The $$$i$$$-th 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 push the button $$$u_i$$$, then you have to push the button $$$v_i$$$. It's guaranteed that the pairs $$$(u_i, v_i)$$$ are distinct.

It's guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, output a single line:

  • If it is impossible, then output $$$-1$$$;
  • Otherwise, first output an integer $$$k$$$, denoting the number of buttons you push. Then output $$$k$$$ integers $$$b_i$$$, denoting the buttons you push. You can output in any order. Note that all $$$b_i$$$ must be distinct, and at last there will be at most $$$\lfloor \sqrt n \rfloor$$$ lamps that are on.
Example
Input
1
4 2
1 2
4 3
Output
2 4 3
Note

In the first test case, there are $$$4$$$ lamps and $$$2$$$ pairs in total. $$$\lfloor \sqrt{4} \rfloor = 2$$$.

One possible way is:

  1. Push the button $$$4$$$. After that, the lamp $$$4$$$ will be toggled on;
  2. Push the button $$$3$$$. After that, the lamp $$$3$$$ will be toggled on (satisfy the $$$2$$$-th pair).

Another possible way is just to push the button $$$2$$$. After that, the lamp $$$2, 4$$$ will be toggled on ($$$4$$$ is a multiple of $$$2$$$). Note that you don't need to push the button $$$1$$$.

These are not the only possible ways.