foreveralone

Problem Description

There are N cats with M friendships between them. As a friendship is mutual, when cat A is friends with cat B, cat B is also friends with cat A.

A cat is called Forever Alone if it does not have any friends. Rar the Cat wants to know how many cats are forever alone.

However, Rar the Cat noticed that some cat claims that they are friends with themselves. These friendships are not legitimate and are termed as Alternative Friendships. Rar the Cat wants you to ignore such alternative friendships and still consider them as Forever Alone if they do not have any other friends.

Limits

For all testcases, 0 ≤ M ≤ N*(N+1)/2 in addition to the limits below.

Subtask 1 (19%): 1 ≤ N ≤ 100, 0 ≤ M ≤ N*(N+1)/2.

Subtask 2 (31%): 1 ≤ N ≤ 10000, 0 ≤ M ≤ 1000000.

Subtask 3 (39%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000.

Subtask 4 (11%): 1 ≤ N ≤ 109, 0 ≤ M ≤ 1000000.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain two integers, N and M.

M lines will follow with 2 integers each, A and B, each ranging from 0 to N-1. This means that there is a friendship between cat A and cat B. This friendship can either be a legitimate friendship or an alternative friendship.

For every pair of cat (A, B), there will not be more than one friendship.

Output

The output should contain a single integer, the number of cats that are forever alone.

Sample Testcase 1

Input

10 5
0 1
2 3
4 5
6 7
8 9

Output

0

Explanation

Every cat from 0 to 9 has a friendship. Thus, no cats are forever alone.

Sample Testcase 2

Input

10 5
0 1
1 2
3 4
5 6
7 8

Output

1

Explanation

Cat 9 is not in any friendships. Hence, it is forever alone.

Sample Testcase 3

Input

10 5
0 0
1 1
2 2
3 2
3 3

Output

8

Explanation

Cat 4, 5, 6, 7, 8 and 9 do not have any friendships. They are forever alone.

Cat 0 and 1 are only in a friendship with itself. Hence, they are considered forever alone.

Although Cats 2 and 3 are in a friendship with itself, they also have a friendship between them. As such, they are not considered forever alone.


Submitting to 'foreveralone'


You're not logged in! Click here to login


Submitting to 'foreveralone'


You're not logged in! Click here to login


Submitting .cpp to 'foreveralone'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 4 Seconds
Memory Limit: 256MB
No. of ACs: 120
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 19
2 31
3 39
4 11
5 0