### Friends

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

There are n people and m pairs of friends. For every pair of friends, they can choose to become online friends (communicating using online applications) or offline friends (mostly using face-to-face communication). However, everyone in these n people wants to have the same number of online and offline friends (i.e. If one person has x onine friends, he or she must have x offline friends too, but different people can have different number of online or offline friends). Please determine how many ways there are to satisfy their requirements.

#### Input

The first line of the input is a single integer T (T=100) , indicating the number of testcases.

For each testcase, the first line contains two integersn (1≤n≤8) and m (0≤m≤n(n−1)2) , indicating the number of people and the number of pairs of friends, respectively. Each of the next m lines contains two numbers x and y , which mean x and y are friends. It is guaranteed that x≠y and every friend relationship will appear at most once.

For each testcase, the first line contains two integers

#### Output

For each testcase, print one number indicating the answer.

#### Sample Input

2 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 4 1

#### Sample Output

0 2

#### Hint

#### Source

2015 Multi-University Training Contest 2