bzoj#P4835. [Lydsy2017年4月月赛]遗忘之树
[Lydsy2017年4月月赛]遗忘之树
题目描述
定义任意两点之间存在唯一路径的无向图是树。对于一棵 个点的树,如果删掉某个点 之后每个连通块的大小均不超过 ,那么称 为这棵树的重心。现在有一棵 n 个点的树 ,利用过程 来构造一个 n 个点的有向图 ,初始 没有边。现在对T调用过程 , 的内容如下:
- 删去 ,对每个连通块递归调用过程 ;
- 对每个连通块,如果它的标号最小的重心为 ,那么在图 中连一条 到 的有向边。
现在小 Q 同学手里有一个图 ,但是不记得原来 的样子了,希望你能通过 来恢复 ,但是可能得到的 会有很多种,你只需要告诉小 Q 同学可能的 的个数。两棵树被认为是不同的,当且仅当存在一对点 ,使得 和 在一棵树中有边,在另一棵树中没有边。
输入格式
第一行是一个整数 ,表示测试数据的组数。
对于每组测试数据:
第一行是两个整数 和 ,表示 的点数的边数。
接下来 行,每行是两个整数 和 ,表示有一条从 到 的有向边。
保证对于每组测试数据,至少存在一棵树 ,使得对 调用过程 之后可以得到 。
并且所有测试数据的 之和、 之和均不超过 。
输出格式
对于每组测试数据,输出一行一个非负整数,表示这组数据的答案对 取模的值。
样例输入
2
3 2
1 2
1 3
4 3
1 3
2 1
2 4
样例输出
1
1
数据范围与约定
对于 的数据,1\le T\le 1000,, ,。
题目来源
鸣谢Tangjz提供试题