文理学院程序设计在线练习


The villagers' election

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

The village of Muye is going to be elected. There are some ninjas in the village, and some of them know each other. If two ninjas know each other, one of the ninjas can represent another ninja (ninja can also represent himself). It is necessary now to select some ninja to form a committees to satisfy that all ninjas in the village are represented by an odd number of committee members. Naruto wants to know the number of different ways to select committee members.

Input

The first line of data is the number of cases T.
For each case data :
The first line is two integers n and m, which represent the number of ninja and the number of relationship.
Next m lines, two integers u, v. This means that ninja u and ninja v know each other.
We ensure that the u and v is different and every relationship appears exactly once.
T <= 10
1<= n <= 20, 0<=m<=min(n*(n-1)/2,20)
1 <= u, v <= n

Output

Each set of data line, directly output the answer.

Sample Input
1
2 1
1 2
Sample Output
2
Source

2019绍兴市计算机技能竞赛