Migrated from Lutece 1578 Kait0u Kid

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Have you known Kaitou Kid, the main character in the manga and anime franchise Magic Kaito, and a recurring character in the manga and anime franchise Detective Conan?

Kid is a talent thief and it seems that he has never been caught by the stupid cops.

But you, as a famous detective, decide to catch him tonight.

You know Kid will appear in Osaka tonight, the structure of Osaka can be regarded as a connected simple undirected graph which composed by $N$ vertices and $M$ edges, the vertices are labeled from $1$ to $N$.

At the beginning, you place some cops at some vertices, and Kid will choose a vertex to start his escape. Matter-of-course, if all the vertices are occupied by cops, he will be caught directly.

The hunt process is played in rounds. Your cops are equipped with helicopters, at the beginning of each round, you can order some subset of cops take off in their helicopters and decide where they will land at the end of the round.

But Kid also knows the positions they will land, while the cops are in the air, he can run freely in the graph; however, he cannot pass through the vertices that are occupied by cops that did not lift.

After Kid runs to his new location, being always a vertex, the lifted cops land on pre-decided vertices.

Kid will be caught if you can always land a cop on his location after some rounds, now you need to determine the minimum number of the cops you need to use to catch him.

Input

The first line contains two integers $N$ and $M$.

For the next $M$ lines, each line contains two integers $u$ and $v$, denotes an edge between the $u_{th}$ vertex and the $v_{th}$ vertex.

$1 \leq N \leq 10^5$, $N - 1 \leq M \leq N + 2$, $1 \leq u, v \leq N$.

Output

Print the minimum number of cops you need to use to catch Kid.

Samples

3 2
1 2
2 3

2

Resources

The 15th UESTC Programming Contest Final