406812: GYM102565 A Artifact

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Artifacttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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.

ExampleInput
5 5
2 5
1 2
2 4
2 3
4 1
Output
2
Note

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

加入题单

上一题 下一题 算法标签: