Maximum Dance Party Invitations

A school is planning a dance party. There are n students in the school, and some pairs of students have danced together before. Note that every dancing pair always consists of one boy and one girl. In the party, it is required that for any chosen boy and any chosen girl, they should not have danced together before. Determine the maximum number of students that can be invited to the party.

Hint: This problem can be modeled as finding a maximum independent set in a bipartite graph. By Kőnig's theorem, the size of a maximum independent set is equal to n minus the size of a maximum matching.

The input consists of a bipartite graph where one part represents boys and the other represents girls. Each edge represents a pair of students who have danced together before.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵), denoting the total number of students and the number of pairs who have danced together before respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) where u is the index of a boy and v is the index of a girl who have danced together before. It is guaranteed that each pair consists of one boy and one girl. Note that some students may not appear in any pair; they are free of any restrictions.

outputFormat

Output a single integer — the maximum number of students that can be invited to the party such that no invited boy and girl have danced with each other before.

sample

4 2
1 1
2 2

2