#P17883. Cyclic Topsort

Cyclic Topsort

给定一张包含 nn 个顶点、mm 条边的有向图,顶点编号为 1,2,…,n1,2,\ldots,n。

你需要选择一个由互不相同的顶点组成的序列 a1,a2,…,ala_1,a_2,\ldots,a_l,满足以下条件:

对于每个 i∈[2,l]i\in[2,l],以及图中每一条指向 aia_i 的边 (v,ai)(v,a_i),都必须存在某个 j<ij<i,使得 aj=va_j=v。

也就是说,除了序列的第一个顶点以外,序列中每个顶点的所有入边起点,都必须已经出现在它之前。

求满足条件的序列的最大长度。

图中允许自环和重边。第一个顶点不受上述入边条件限制。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行两个整数 ui,viu_i,v_i,表示一条从 uiu_i 指向 viv_i 的边。

输出格式

输出一个整数,表示合法序列的最大长度。

数据范围

2≤n≤3×1052\le n\le3\times10^5,0≤m≤3×1050\le m\le3\times10^5,1≤ui,vi≤n1\le u_i,v_i\le n。

样例 1

5 0
5

样例 2

3 3
1 1
2 2
3 3
1

样例说明

样例 1 中所有顶点都没有入边,可以选择全部顶点。

样例 2 中每个顶点都有自环,因此只有第一个顶点能够被选入序列。