配点 : $500$ 点

問題文

$N$ 頂点 $M$ 辺からなる単純な有向グラフ $G$ があり、頂点には頂点 $1$, 頂点 $2$, $\ldots$, 頂点 $N$ と番号がついています。 また、$i$ $(1\leq i\leq M)$ 本目の辺は頂点 $U_i$ から頂点 $V_i$ へ張られています。

高橋君がある頂点から始めて、$G$ の上を有向辺に沿って頂点から頂点へ移動することを繰り返します。 $G$ の頂点のうち、高橋君がうまく経路を選ぶことで、その頂点から始めていくらでも移動を繰り返すことができるようなものの個数を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $0 \leq M \leq \min(N(N-1), 2\times 10^5)$
• $1 \leq U_i,V_i\leq N$
• $U_i\neq V_i$
• $i\neq j$ ならば $(U_i,V_i)\neq (U_j,V_j)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

出力

答えを出力せよ。

5 5
1 2
2 3
3 4
4 2
4 5

4

頂点 $2$ を始点とした場合、頂点 $2$ $\to$ 頂点 $3$ $\to$ 頂点 $4$ $\to$ 頂点 $2$ $\to$ 頂点 $3$ $\to$ $\cdots$ と高橋君はいくらでも移動を繰り返す事ができます。 頂点 $3$, 頂点 $4$ を始点とした場合も同様です。 頂点 $1$ からは最初に頂点 $2$ に移動して、以下同様にいくらでも行動を繰り返すことができます。 一方、頂点 $5$ からは一度も移動することができません。

よって、条件を満たすのは頂点 $1$, $2$, $3$, $4$ の $4$ つであるので、 $4$ を出力します。

3 2
1 2
2 1

2

単純な有向グラフにおいて、$2$ つの頂点の間を互いに逆向きに結ぶ辺が、ともに存在する事はあり得ることに注意してください。 また、$G$ は連結であるとは限りません。