Informatica Online Judge

  빛종한 [2308 / 0904]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 27   Total Tried : 27


The Champion of this Problem (C++) : gs17050 - ms / 850byte
My Best Submission (C++) : N/A

[35th 김세빈]

Background

종한이는 오늘도 단백질 합성 실험에 빠져 있다.

종한이는 $N$가지 단백질들이 적힌 목록을 가지고 있는데, 그의 목표는 이 $N$가지 종류의 단백질들을 모두 수집하는 것이다.


종한이가 단백질을 얻을 수 있는 방법은 두 가지가 있다.

먼저, 인터넷을 통해 원하는 종류의 단백질을 원하는 만큼 구입할 수 있다.

또한, 뛰어난 생물 실력을 가진 종한이는 $M$가지의 실험을 통해 특정한 종류의 단백질을 다른 종류로 바꿀 수 있다. i번째 실험은 단백질 $A_i$를 $B_i$로 바꾸는 실험이다.


물론 모든 단백질들을 인터넷에서 구입해도 된다.

하지만 구입하는 단백질의 종류가 많아질수록 배송이 늦어지게 된다.

뿐만 아니라, 종한이는 실험을 "사랑"하므로, 실험을 통해 달성할 수 있는 일을 굳이 인터넷을 통해 하고 싶지 않다.

따라서 최대한 적은 종류의 단백질들을 인터넷에서 구입하고, 나머지는 실험을 통해 얻으려고 한다.

종한이가 N가지 종류의 단백질들을 모두 수집하기 위해 인터넷에서 구입해야 할 단백질의 종류의 수의 최솟값을 구하여라.

Input

첫째 줄에 단백질의 수 $N$과 종한이가 할 수 있는 실험의 수 $M$이 주어진다.

둘째 줄부터 $M+1$번째 줄까지, $i+1$번째 줄에는 두 개의 정수 $A_i$와 $B_i$가 주어진다. 이는 종한이가 $i$번째 실험을 통해 단백질 $A_i$를 $B_i$로 바꿀 수 있음을 의미한다.

물론, 몇만 개가 넘는 단백질을 다루는 것쯤이야 종한이에게는 일도 아니다. 하지만 이산구조 시간에 이 문제를 풀어야 하는 여러분을 위해 아래와 같은 조건을 두겠다.

$1 <= N <= 20,000$
$1 <= M <= 50,000$
$1 <= A_i, B_i <= N$
$A_i != B_i$

Output

종한이가 인터넷에서 구입해야 할 단백질의 종류의 수의 최솟값을 구하여라.

IO Example

Input 1
3 2
1 3
2 3

Output 1
2

Input 2
5 6
1 2
2 4
2 5
3 5
4 5
4 1

Output 2
2

Input 3
5 0

Output 3
5

Note

첫 번째 예제에서, 단백질 1과 2를 구입하면 이를 통해 3을 얻을 수 있다.
두 번째 예제에서, 단백질 1과 3만 구입하면 된다.
세 번째 예제에서, 종한이는 모든 단백질을 구입해야 한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]