Using his experiences with time travel, as well as some knowledge of general relativity and black holes, the mad scientist Kyouma has created a doomsday device. He plans to cause a localized event horizon: given a series of events and connections, sever the events so that no event can be affected by another.
Kyouma has spotted a network of events which he will use his device on. This network can be treated as an undirected graph with ~N~ vertices (numbered from ~1~ to ~N~) and ~M~ edges, with each vertex representing an event to disconnect and each edge representing a connection between two events. When Kyouma triggers his device, a large distortion in spacetime is created, allowing him to remove any group of edges from the graph which forms a pseudoforest. He considers the network destroyed and his task complete once he has removed all edges through uses of his doomsday device.
However, some of the connections between events are abnormally strong: that is, it is possible for multiple edges to exist between the same pair of vertices, all of which must be removed. It is guaranteed that each edge connects two distinct vertices.
Kyouma, while an evil genius, is neither very rich nor very patient. Therefore, he would like to know the fewest number of times he must activate his device to destroy the network.
A pseudoforest is a series of edges where, for each connected component, there is at most one simple cycle. Since there may be repeated edges in this graph, a simple cycle contained in a valid pseudoforest may consist of two vertices connected by two edges.
Subtask 1 [10%]
~1 \le M \le 9~
~2 \le N \le 9~
Subtask 2 [90%]
~1 \le M \le 2000~
~2 \le N \le 2000~
For all tasks, the constraints ~1 \le a,b \le N~, and ~a \ne b~ will hold.
On the first line will be two space separated integers: ~N~, the number of vertices, and ~M~, the number of edges.
On each of the next ~M~ lines there will be two integers ~a~ and ~b~, indicating a two-way connection between ~a~ and ~b~.
Print a single integer, the fewest number of pseudoforests that must be removed in order to disconnect all vertices.
Sample Input 1
3 2 1 2 3 2
Sample Output 1
Sample Input 2
4 5 1 2 2 3 3 4 4 1 1 3
Sample Output 2
Explanation for Sample 2
There is no way to remove all the edges with one pseudoforest. To remove it with two, Kyouma could for example remove the edges ~(1,2)~ and ~(2,3)~ at first, and then remove the remaining edges afterwards.
Sample Output 3
2 2 1 2 1 2
Sample Output 3
Explanation for Sample 3
As can be seen, a cycle between two nodes (~1~ and ~2~ in this case) is considered a valid cycle, and can therefore be removed in one activation.
Sample Input 4
3 4 1 2 2 1 2 3 3 2
Sample Output 4