eolymp
bolt
Try our new interface for solving problems
Problems

Bi-coloring

Bi-coloring

Time limit 1 second
Memory limit 64 MiB

Given a graph determine how many ways you can color the graph with at most two colors. There cannot be an edge containing two vertices of the same color.

Input data

First line of the input contains T the number of test cases. Each test case starts with a line containing two integers V (1 V30) and E (0E1000). Each of the next E line contains two integers a, b (0aV-1, 0bV-1) denoting that there is a bidirectional edge between a and b. There will not be any self loop or duplicate edges. The last line of the input will be a blank.

Output data

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

Input example #1
4
5 5
0 1
0 4
1 2
2 3
3 0

3 3
0 1
1 2
2 0

6 7
0 1
1 2
2 3
3 0
4 0
4 5
5 1

2 0
Output example #1
2
-1
2
4
Source ACM-ICPC Malaysia al-Khawārizmī Programming Contest 2011