给定一张包含 个生物、 条捕食关系的食物网,可形式化为一张有向无环图(DAG)。每条有向边由一对整数 表示:生物 捕食生物 。 在生物学意义上,一条食物链被定义为: 起点是生产者——不会捕食其它生物(即出度为 ); 终点是顶级消费者——不会被其它生物捕食(即入度为 ); 从生产者到顶级消费者,需要沿捕食方向(即有向边方向)依次连接。 请计算图中这样的食物链共有多少条。题目保证答案不超过 。
输入描述:
第一行输入两个整数 ——生物数量与捕食关系数量。接下来 行,每行输入两个整数 ,表示生物 捕食生物 (有向边 )。


输出描述:
输出一个整数,表示满足定义的食物链数量。
示例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

说明

所有出度为 0 的顶点为生产者 \{3,5,8\},所有入度为 0 的顶点为顶级消费者 \{1\}。沿有向边统计可得共 9 条满足要求的路径。
加载中...