#8336. 「信息素养2023小学组决赛」有向无环图的拓扑排序方案数 普及+/提高

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

给定一个有向无环图 (DAG),求其拓扑排序结果的方案数。一个拓扑排序是将所有节点排成一个线性序列,使得对于每条有向边 ,节点 在序列中出现在

节点 的前面。

输入格式

第一行两个整数 ,表示 DAG 的节点数和边数。

接下来 行,每行两个整数 ,表示有一条从节点 到节点 的有向边。

输出格式

输出一个整数,表示拓扑排序结果的方案数。

样例

样例输入

3 2
1 2
2 3

样例输出

1

样例解释

有且仅有一种拓扑排序: 1 -> 2 -> 3。

数据范围与提示