心落河水平穿过命运之地,将其分为南北两侧。
工程师 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$$$ 之前。
由于鲁特被命运与他分离的前任分心,他要求你计算沿河排列房屋的方式的数量,以 $$$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$$$ 行,第 $$$i$$$ 行包含两个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 沿河排列 $$$n$$$ 房屋的方式数量,以 $$$10^9+7$$$ 为模。
示例
输入复制
42 11 23 31 21 32 35 41 21 33 43 54 31 21 31 4
输出复制
2 0 8 12
注意
在第一个测试用例中,房屋 $$$1$$$ 应建在北侧,房屋 $$$2$$$ 应建在南侧,反之亦然。
在第二个测试用例中,必须在河的同一侧至少建造两栋房屋。但每对房子都有一座桥相连。所以在每一种安排中,至少有一座桥不会过河。因此,答案是$$$0$$$。
在第三个测试用例中,问题陈述中提供了房屋的可能布置之一。