题目描述

定义任意两点之间存在唯一路径的无向图是树。对于一棵 $n$ 个点的树，如果删掉某个点 $u$ 之后每个连通块的大小均不超过 $\dfrac n 2$，那么称 $u$ 为这棵树的重心。现在有一棵 $$n$$ 个点的树 $T$，利用过程 $\operatorname{P}$ 来构造一个 $$n$$ 个点的有向图 $G$ ，初始 $G$ 没有边。现在对T调用过程 $\operatorname{P}$ ， $\operatorname{P}$ 的内容如下：

1. 删去 $u$，对每个连通块递归调用过程 $\operatorname{P}$ ；
2. 对每个连通块，如果它的标号最小的重心为 $v$，那么在图 $G$ 中连一条 $u$ 到 $v$ 的有向边。

现在小 Q 同学手里有一个图 $G$ ，但是不记得原来 $T$ 的样子了，希望你能通过 $G$ 来恢复 $T$，但是可能得到的 $T$ 会有很多种，你只需要告诉小 Q 同学可能的 $T$ 的个数。两棵树被认为是不同的，当且仅当存在一对点 $(u,v)$，使得 $u$ 和 $v$ 在一棵树中有边，在另一棵树中没有边。

输入格式

第一行是一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行是两个整数 $n$ 和 $m$ ，表示 $G$ 的点数的边数。

接下来 $m$ 行，每行是两个整数 $u$ 和 $v$，表示有一条从 $u$ 到 $v$ 的有向边。

保证对于每组测试数据，至少存在一棵树 $T$ ，使得对 $T$ 调用过程 $\operatorname{P}$ 之后可以得到 $G$ 。

并且所有测试数据的 $n$ 之和、 $m$ 之和均不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个非负整数，表示这组数据的答案对 $10^9+7$ 取模的值。

样例输入

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

样例输出

1
1

数据范围与约定

对于 $100\%$ 的数据，1\le T\le 1000，$2\le n , m \le 100000$，$1\le u,v\le n$ ，$\sum n,\sum m\le 10^6$。

题目来源

鸣谢Tangjz提供试题