bzoj#P4835. [Lydsy2017年4月月赛]遗忘之树

[Lydsy2017年4月月赛]遗忘之树

题目描述

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

  1. 删去 uu,对每个连通块递归调用过程 P\operatorname{P}
  2. 对每个连通块,如果它的标号最小的重心为 vv,那么在图 GG 中连一条 uuvv 的有向边。

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

输入格式

第一行是一个整数 TT,表示测试数据的组数。

对于每组测试数据:

第一行是两个整数 nnmm ,表示 GG 的点数的边数。

接下来 mm 行,每行是两个整数 uuvv,表示有一条从 uuvv 的有向边。

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

并且所有测试数据的 nn 之和、 mm 之和均不超过 10610^6

输出格式

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

样例输入

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

样例输出

1
1

数据范围与约定

对于 100%100\% 的数据,1\le T\le 1000,2n,m1000002\le n , m \le 1000001u,vn1\le u,v\le nn,m106\sum n,\sum m\le 10^6

题目来源

鸣谢Tangjz提供试题