#104835. [BZOJ 4835] [Lydsy1704月赛]遗忘之树

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

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

现在小 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提供试题