Score : $600$ points
Given is a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \dots, N$, and the $i$-th edge connects Vertices $A_i$ and $B_i$.
Find the minimum possible number of connected components in the graph after removing zero or more edges so that the following condition will be satisfied:
Condition:
For every pair of vertices $(a, b)$ such that $1 \le a < b \le N$, if Vertices $a$ and $b$ belong to the same connected component, there is an edge that directly connects Vertices $a$ and $b$.
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$
Print the answer.
3 2 1 2 1 3
2
Without removing edges, the pair $(2, 3)$ violates the condition. Removing one of the edges disconnects Vertices $2$ and $3$, satisfying the condition.
4 6 1 2 1 3 1 4 2 3 2 4 3 4
1
10 11 9 10 2 10 8 9 3 4 5 8 1 8 5 6 2 5 3 6 6 9 1 9
5
18 0
18