Hide

Problem E
Faculty Forest

Right after finishing the CS $32$ lecture on trees, you notice that if you draw a graph whose nodes are UCLA Computer Science faculty members, and add an edge between every pair of faculty members who have coauthored a paper together, the Computer Science Department forms a tree! With a little more research, you find that if you draw the same graph for each UCLA department, you also get a tree! Given the forest of departmental faculty collaboration trees, find how many departments there are. Sadly, there is no collaboration between departments, and also it is possible that some departments may have only one faculty member (who cannot have coauthored a paper with anyone else).

Input

The first line of input consists of two space-separated integers $n$ and $m$, where $1 \leq n \leq 10^5$ is the number of faculty members at UCLA, and $0 \leq m < n$ is the number of distinct pairs of faculty members who have coauthored a paper. The faculty members are numbered $1,2,3 \dots n$. There follow $m$ lines each containing two space-separated integers $a$ and $b$ such that $1 \leq a,b \leq n$ and $a \not= b$, indicating that faculty member $a$ and faculty member $b$ have coauthored a paper. It is guaranteed that the input forms a forest.

Output

Print the number of departments at UCLA.

Sample Explanation

Figure  1 below shows how sample input $4$ corresponds to $2$ departments.

\includegraphics[width=0.5\textwidth ]{example_graph.png}
Figure 1: Sample input $4$ corresponds to $2$ departments, one containing faculty members $1$, $2$ and $4$, and the other containing faculty members $3$ and $5$.
Sample Input 1 Sample Output 1
1 0
1
Sample Input 2 Sample Output 2
2 0
2
Sample Input 3 Sample Output 3
2 1
1 2
1
Sample Input 4 Sample Output 4
5 3
5 3
4 1
2 4
2
CPU Time limit 1 second
Memory limit 1024 MB
Author
Jacob Zhang
Source CodeSprintLA 2020 (UCLA ACM-ICPC)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in