#P17883. Cyclic Topsort
Cyclic Topsort
给定一张包含 个顶点、 条边的有向图,顶点编号为 。
你需要选择一个由互不相同的顶点组成的序列 ,满足以下条件:
对于每个 ,以及图中每一条指向 的边 ,都必须存在某个 ,使得 。
也就是说,除了序列的第一个顶点以外,序列中每个顶点的所有入边起点,都必须已经出现在它之前。
求满足条件的序列的最大长度。
图中允许自环和重边。第一个顶点不受上述入边条件限制。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示一条从 指向 的边。
输出格式
输出一个整数,表示合法序列的最大长度。
数据范围
,,。
样例 1
5 0
5
样例 2
3 3
1 1
2 2
3 3
1
样例说明
样例 1 中所有顶点都没有入边,可以选择全部顶点。
样例 2 中每个顶点都有自环,因此只有第一个顶点能够被选入序列。