Bobo 有一个包含 $n$ 个顶点的无向图 $G$，顶点编号为 $1, \dots, n$，共有 $n$ 条边。对于每个 $1 \le i \le n$，顶点 $i$ 与顶点 $(i \pmod n) + 1$ 之间有一条边。此外，他还有一个包含 $m$ 个数对的列表 $(a_1, b_1), \dots, (a_m, b_m)$。

现在，Bobo 将选择一个 $i$，并移除顶点 $i$ 与顶点 $(i \pmod n) + 1$ 之间的边。令 $\delta_i(u, v)$ 表示移除该边后，顶点 $u$ 和顶点 $v$ 之间最短路径的边数。

请选择一个 $i$，使得 $\delta_i(a_1, b_1), \dots, \delta_i(a_m, b_m)$ 中的最大值最小。

形式化地，求以下表达式的值： $$\min_{1 \le i \le n} \left\{ \max_{1 \le j \le m} \delta_i(a_j, b_j) \right\}$$

输入格式

输入包含多个测试用例，以文件结束符（EOF）终止。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$。 接下来的 $m$ 行中，第 $j$ 行包含两个整数 $a_j$ 和 $b_j$。

• $2 \le n \le 2 \times 10^5$
• $1 \le m \le 2 \times 10^5$
• 对于每个 $1 \le j \le m$，$1 \le a_j, b_j \le n$
• 在每个输入中，所有测试用例的 $n$ 之和不超过 $2 \times 10^5$，所有测试用例的 $m$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示该最小值。

样例

输入格式 1

3 2
1 2
2 3
3 2
1 1
2 2
3 3
1 2
2 3
3 1

输出格式 1

1
0
2

说明

对于第一个样例，当 $i=1$ 时，$\delta_1(1, 2)=2, \delta_1(2, 3)=1$；当 $i=2$ 时，$\delta_2(1, 2)=1, \delta_2(2, 3)=2$；当 $i=3$ 时，$\delta_3(1, 2)=1, \delta_3(2, 3)=1$。选择 $i = 3$ 可得到最小值 1。