SP10440 FRNDS - Friends

朋友 有一群 $N$ 人打算一起去电影院看电影，其中有些人是彼此认识的朋友。根据一句俗话——“我朋友的朋友也是我的朋友”，可以推导出：如果 $A$ 和 $B$ 是朋友，$B$ 和 $C$ 也是朋友，那么 $A$ 和 $C$ 也彼此是朋友。而且，任何一个朋友关系都是相互的，也就是说如果 $A$ 是 $B$ 的朋友，那么 $B$ 也是 $A$ 的朋友。 这一群人将坐在电影院的第一排，这一排有 $N$ 个座位。一次排座是成功的，如果至少有一对朋友坐在相邻的座位上。你的任务是计算有多少种这样的成功排座的方式。

输入以一个整数 $T$ 开始，表示测试用例的数量（$1 \le T \le 600$）。每个测试用例从两个整数 $N$ 和 $M$ 开始，分别代表总人数和朋友关系的数目（$2 \le N \le 40$，$0 \le M \le 800$）。接下来的 $M$ 行，每行包含两个整数 $A$ 和 $B$（$1 \le A, B \le N$，$A \neq B$），表示 $A$ 和 $B$ 是朋友。

对于每个测试用例，输出结果为一行格式为「Case #X: P」，其中 $X$ 代表测试用例编号（从 1 开始），$P$ 是能成功安排的方式数量，并对 $1000000007$ 取模后的结果。你可以参考样例输出来更好地理解格式。 **本翻译由 AI 自动生成**