如果一个图可以用 $k$ 种颜色对每个节点进行染色，使得任意两个由边相连的节点 $u$ 和 $v$ 的颜色不同，则称该图是 $k$-可着色的。

给定一个连通的二分图，其中一部分有 $n$ 个节点，编号为 $1$ 到 $n$，另一部分有 $n$ 个节点，编号为 $n+1$ 到 $2n$。第一部分的任意两个节点之间没有边，第二部分的任意两个节点之间也没有边。

（如果一个图的节点可以被划分为两个非空集合，使得每条边都连接来自不同集合的节点，则称该图为二分图。）

这个图显然是 2-可着色的：你可以将第一部分的所有节点染成颜色 1，将第二部分的所有节点染成颜色 2。但你不喜欢这样。你不希望这个图是 2-可着色的。你甚至不希望它是 3-可着色的！

你希望向该图中添加一些边，使得它不再是 3-可着色的（特别地，你可以在同一部分的两个节点之间添加边）。请问你最少需要添加多少条边？

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 10^4, 2n - 1 \le m \le \min(n^2, 2 \cdot 10^5)$)，分别表示每一部分的大小和边的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i \le n, n+1 \le v_i \le 2n$)，表示一条边 $(u_i, v_i)$。

保证没有重边。保证给定的图是连通的。

输出格式

输出一个整数，表示为了使该图不再是 3-可着色的，你最少需要添加的边数。

样例

样例输入 1

2 4
1 3
1 4
2 3
2 4

样例输出 1

2

样例输入 2

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

样例输出 2

3

说明

在第一个样例中，你可以向图中添加边 $(1, 2)$ 和 $(3, 4)$。你将得到一个 4 个节点的完全图，它不是 3-可着色的。

在第二个样例中，你至少需要添加 3 条边才能使图不再是 3-可着色的。