問題
K君はオンラインゲーム"失われた王国"(chatgpt命名)を作成しています。
"失われた王国"には$N$個のエリアがあり、それぞれのエリアは一方通行のポータルでつながっています。
ポータルの情報が与えられます。各エリアからどのエリアへも到達できるようにするためには最小で何個ポータルを設置する必要があるかを出力してください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$
$A_i,B_i$は$i$個目のポータルがエリア$A_i$からエリア$B_i$へ移動できることを示している。
出力
アからどのエリアへも到達できるようにするためには最小で何個ポータルを設置する必要があるかを出力してください。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 10^{5}$
- $1 \leq M \leq 10^{5}$
- $1 \leq A_i,B_i \leq N$
- $A_i \ne B_i(1 \leq i \leq N)$
- 入力はすべて整数
入出力例
入力例1
3 3 1 2 2 3 3 1
出力例1
0
入力例2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
出力例2
1
作った後に気づきましたが、2017年のPCK予選10問目と同じ内容です。