Problem Description

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

Input Format

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 Format

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

5 6
1 2
2 3
3 1
3 4
4 5
3 5

2

Hint

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