P10779 BZOJ4316 Xiao C's Independent Set

Given a simple undirected graph $G = (V, E)$, it is guaranteed that each edge belongs to one and only one simple cycle. Find the size of the maximum independent set of $G$.

The first line contains two positive integers $n, m$, representing the number of vertices and the number of edges in the graph. The next $m$ lines each contain two positive integers $u, v$, describing an undirected edge.

Output the size of the maximum independent set of $G$.

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^4$, and $1 \leq m \leq 6 \times 10^4$. Translated by ChatGPT 5