시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

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.

입력

First line of the input contains T the number of test cases. Each test case starts with a line containing two integers V(1≤V≤30) and E(0≤E≤1000). Each of the next E line contains two integers a, b (0≤a≤V‐1, 0≤b≤V‐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.

출력

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.

예제 입력 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

예제 출력 1

2
-1
2
4