Bi-coloring

Input

The first line of the input contains $T$, the number of test cases. Each test case starts with a line containing two integers $V$ (1 \leq V \leq 30) and $E$ (0 \leq E \leq 1000). Each of the next $E$ lines contains two integers $a$, $b$ (0 \leq a \leq V-1, 0 \leq b \leq V-1) denoting that there is a bidirectional edge between $a$ and $b$. There will not be any self-loops or duplicate edges. The last line of the input will be blank.

Output

For each test case, output the number of ways you can color the graph with only two colors. If you cannot color the graph with at most two colors, output $-1$.

Examples