406812: GYM102565 A Artifact

You and your friend are playing a game called Dota 2 and you want to do a one versus one match. You are given $$$N$$$ artifacts at the beginning of the game and you need to give some of them to your friend. These artifacts can be combined to create spells. A spell can be constructed with k artifacts $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ if $$$k \geq 2$$$ and artifact $$$a_1$$$ can be combined with artifact $$$a_2$$$, artifact $$$a_2$$$ can be combined with artifact $$$a_3$$$, ..., artifact $$$a_{k-1}$$$ can be combined with artifact $$$a_k$$$. Your friend is a professional player, so if he has at least $$$2$$$ distinct artifacts belonging to a spell construction, he will be able to build the whole spell. Because you are not so good at this game, if your friend can build at least one spell, he will beat you.

You need to give to your friend the maximum number of artifacts, such that he will not be able to create any spell with these artifacts, having in mind that he needs only two distinct artifacts from a spell construction in order to create the whole spell.

The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 3000$$$), representing the number of artifacts, and the number $$$M$$$ ($$$1 \leq M \leq20000$$$), representing the number of pairs of artifacts that can be combined.

The following $$$M$$$ lines will contain two numbers $$$x_i$$$ ($$$1 \leq x_i \leq N$$$) and $$$y_i$$$ ($$$1 \leq y_i \leq N$$$) each, $$$x_i \neq y_i$$$, representing that artifact $$$x_i$$$ can be combined with artifact $$$y_i$$$ (this does not mean that artifact $$$y_i$$$ can be combined with artifact $$$x_i$$$).

You should output one line containing one non-negative integer: the maximum number of artifacts that you can give to your friend, such that he will not be able to create any spell.

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

2

$$$2$$$ is the maximum number of artifacts that you can give to your friend.

For example, you can give to your friend artifact $$$3$$$ and $$$5$$$. Note that we cannot give him artifact $$$4$$$ as well, because that would mean he would be able to create the spell $$$4, 1, 2, 3$$$.