CodeSprintLA 2020 — Individual Competition


2020-05-23 13:00 AKDT

CodeSprintLA 2020 — Individual Competition


2020-05-23 15:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -393 days 22:21:39

Time elapsed


Time remaining


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).


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.


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
Sample Input 2 Sample Output 2
2 0
Sample Input 3 Sample Output 3
2 1
1 2
Sample Input 4 Sample Output 4
5 3
5 3
4 1
2 4