食物链

题目描述:

给定一个生态系统，其中包括n个物种和m条捕食关系，求生态系统中的食物链条数。

如下图中共有9条食物链（你也许曾经生物课上手算过）。

补充说明：捕食食物链的起点是生产者，终点是不被其他动物所食的的动物，不出现非生物物质和能量及分解者，即只有生产者和消费者。

输入格式:

第一行为数据组数T。

接下来T组，开头两个整数n和m，接下来m行，每行两个整数u,v表示存在从u被v捕食。

其中T<=30, n<=100000, m<=200000, 1<=u,v<=n。

输出格式:

对于每一组数据，输出一个整数，表示食物链的条数，答案 mod 1e9+7。

样例输入:

1
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

样例输出:

9

提示:

样例即为上图，编号为草是1，其余从左到右依次编号。

如果实在没有思路的话，可以参考算法导论练习题22.4-2。

时间限制: 2000ms
空间限制: 128MB

---

来源: HAOI 2016 d1t1