C.朋友

题目描述

题目描述

有 $n$ 个人和 $m$ 对朋友关系。每对朋友可以选择成为线上朋友（通过网络联系）或线下朋友（主要通过面对面交流）。

要求：每个人拥有的线上朋友数量和线下朋友数量必须相同。

• 即，如果某人 $i$ 有 $x_i$ 个线上朋友，那么他也必须有 $x_i$ 个线下朋友。
• 不同的人可以有不同的总朋友数。

请计算满足所有人要求的方法总数。

输入格式

第一行是一个整数 $T(T \leq 100)$，表示测试用例的数量。

对于每个测试用例：

1. 第一行包含两个整数 $n (1 \leq n \leq 8)$和 $m (0 \leq m \leq (n)*(n-1)/2)$，分别表示人数和朋友对数。
2. 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ ，表示 $x$ 和 $y$是朋友关系。保证 $x != y$ ，且任何一对朋友关系最多出现一次。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的方法总数。

样例

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

0
2