A graph is called $k$\-colorable if it's possible to color each its node in one of $k$ colors so that for any two nodes $u$ and $v$, which are connected by an edge, their colors will be different.

You are given a connected bipartite graph, where one part has $n$ nodes, numbered from $1$ to $n$, and the second part has $n$ nodes, numbered from $n+1$ to $2n$. There is no edge between any two nodes from the first part, and there is no edge between any two nodes from the second part.

(A graph is called bipartite if its nodes can be split into two nonempty parts, such that each edge connects nodes from different parts).

This graph, of course, is $2$\-colorable: you can color all nodes from the first part in color $1$ and from the second in color $2$. But you don't like that. You don't want this graph to be $2$\-colorable. You don't even want it to be $3$\-colorable!

You want to add some edges to this graph so that it stops being $3$\-colorable (in particular, you can add edges between two nodes from the same part). What's the smallest number of edges you have to add?

The first line contains two integers $n, m$ ($2 \le n \le 10^4, 2n-1 \le m \le min(n^2, 2\cdot 10^5)$)  — the size of each part and the number of edges correspondingly.

The $i$\-th of the next $m$ lines contains two integers $u_i, v_i$ ($1 \le u_i \le n$, $n+1 \le v_i \le 2n$), denoting the edge $(u_i, v_i)$.

It's guaranteed that no edge will appear more than once. It's guaranteed that the graph on these edges is connected.

Output a single integer  — the smallest number of edges that you have to add to this graph so that it becomes not $3$\-colorable.

2

In the first sample, you can add edges $(1, 2)$ and $(3, 4)$ to the graph. You will get a complete graph on $4$ nodes, which is not $3$\-colorable.

3

In the second sample, you can't add less than $3$ edges to make graph not $3$\-colorable.