Advertisement(宣伝) - joi2009-day2

時間制限: 1秒

メモリ制限: 64MB

JOI社はついに新製品「途方もなく奇妙な道具(Incredibly Odd Instrument)」の開発を終えた. 社長は, この新製品についての案内を, 購入が予想される全ての人に送信するつもりで, それらの人の連絡先を入手したが, あまり多くの人に案内を送っていると, 悪質な業者であると思われてしまう可能性があることに気づいた.

そこで, できるだけ少ない人数の人を選んで案内を送信し, 人づてに全ての人に新製品について知ってもらうことにした. 新製品はとても革新的なので, 製品について知った人は, すぐに自分が連絡先を知っている全ての人に新製品についての情報を連絡すると考えられる.

購入が予想される全ての人に新製品についての情報が行き渡るようにするために, 何人の人間に案内を送信しなければならないかを求めるプログラムを作成せよ.

Input.

入力ファイルadvertisement.inの1行目には, 2つの整数n,m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) が空白を区切りとして書かれている. nは新製品の購入が予想される人の人数を表す.

続くm行(2行目からm+1行目) はどの人がどの人の連絡先を知っているかを表す. j+1行目(1 ≤ j ≤ m) には, 2つの整数a[j],b[j] (1 ≤ a[j],b[j] ≤ n, a[j] ≠ b[j]) が空白を区切りとして書かれている. これは, 人a[j]が人b[j]の連絡先を知っていることを表す. 人は1からnまでの整数で表される. j ≠ k ならばa[j] = a[k] かつb[j] = b[k] となることはない.

Output.

出力は, 標準出力に行うこと. 案内を送信する相手の人数の最小値を表す1つの整数を出力せよ.

採点基準

採点用データのうち, 配点の70% 分については, n ≤ 1000, m ≤ 1000 を満たす.

例1

advertisement.in	標準出力
`5 5 1 2 2 3 3 1 3 4 5 4`	`2`