题目描述

Heartfall River 横贯 Destinyland，将其分为北岸和南岸。

工程师 Root 想要在河边建造 $n$ 座房屋，编号从 $1$ 到 $n$。所有北岸的房屋和所有南岸的房屋都必须分别沿着与 Heartfall River 平行的直线排列。

将建造 $m$ 座桥，第 $i$ 座桥连接房屋 $u_i$ 和房屋 $v_i$（$u_i \ne v_i$）。保证所有 $n$ 座房屋通过这些桥是连通的，也就是说，可以通过若干桥从任意一座房屋到达另一座房屋。此外，不存在两座桥连接同一对房屋。

Root 想知道，有多少种方式可以沿河排列这 $n$ 座房屋（对 $10^9+7$ 取模），使得计划中的 $m$ 座桥满足以下条件：

• 对于每一座桥，它连接的两座房屋必须分别位于河的两岸；
• 当桥作为直线连接两座房屋时，所有桥都不会相交。

当 $n=5$ 时的一种可能的房屋排列方式。

如果存在以下任一情况，则两种排列被认为是不同的：

• 存在某座房屋在两种排列中位于不同的河岸；
• 存在两座房屋 $a$ 和 $b$，它们在两种排列中都位于同一岸，但在一种排列中 $a$ 在 $b$ 前面，而在另一种排列中 $b$ 在 $a$ 前面。

由于 Root 被命运分离的前任分心，他请求你计算有多少种方式可以沿河排列房屋，对 $10^9+7$ 取模。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$, $n-1 \leq m \leq \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$）——房屋数量和桥的数量。

接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i,v_i \leq n$, $u_i\ne v_i$）——第 $i$ 座桥连接的两座房屋编号。

保证所有 $n$ 座房屋通过这些桥是连通的，且不存在两座桥连接同一对房屋。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示沿河排列房屋的方案数，对 $10^9+7$ 取模。

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

2
0
8
12

说明/提示

在第一个测试用例中，房屋 $1$ 可以建在北岸，房屋 $2$ 建在南岸，或者反过来。

在第二个测试用例中，至少有两座房屋必须建在同一岸。但任意两座房屋之间都有桥相连，因此无论如何排列，至少有一座桥不会跨越河流。因此，答案为 $0$。

在第三个测试用例中，题目描述中给出了一种可能的房屋排列方式。

由 ChatGPT 4.1 翻译