시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 79 | 50 | 47 | 65.278% |
JOI 社はついに新製品「途方もなく奇妙な道具 (Incredibly Odd Instrument)」の開発を終え た.社長は,この新製品についての案内を,購入が予想される全ての人に送信するつもりで,そ れらの人の連絡先を入手したが,あまり多くの人に案内を送っていると,悪質な業者であると 思われてしまう可能性があることに気づいた.
そこで,できるだけ少ない人数の人を選んで案内を送信し,人づてに全ての人に新製品につ いて知ってもらうことにした.新製品はとても革新的なので,製品について知った人は,すぐ に自分が連絡先を知っている全ての人に新製品についての情報を連絡すると考えられる.
購入が予想される全ての人に新製品についての情報が行き渡るようにするために,何人の人 間に案内を送信しなければならないかを求めるプログラムを作成せよ.
入力の 1 行目には,2 つの整数 n, m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) が空白を区切りとして書かれている.n は新製品の購入が予想される人の人 数を表す.
続く m 行 (2 行目から m + 1 行目) はどの人がどの人の連絡先を知っているかを表す.j + 1 行目 (1 ≤ j ≤ m) には,2 つの整数 aj, bj (1 ≤ aj, bj ≤ n,aj ≠ bj) が空白を区切りとして書か れている.これは,人 aj が人 bj の連絡先を知っていることを表す.人は 1 から n までの整数で 表される.j ≠ k ならば aj = ak かつ bj = bk となることはない.
出力は,標準出力に行うこと.案内を送信する相手の人数の最小値を表す 1 つの整 数を出力せよ.
5 5 1 2 2 3 3 1 3 4 5 4
2