시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB116562.500%

문제

Bobo has an undirected graph $G$ with $n$ vertices labeled by $1, \dots, n$ and $n$ edges. For each $1 \leq i \leq n$, there is an edge between the vertex $i$ and the vertex $(i \bmod n) + 1$. He also has a list of $m$ pairs $(a_1, b_1), \dots, (a_m, b_m)$.

Now, Bobo is going to choose an $i$ and remove the edge between the vertex $i$ and the vertex $(i \bmod n) + 1$. Let $\delta_i(u, v)$ be the number of edges on the shortest path between the $u$-th and the $v$-th vertex after the removal. Choose an $i$ to minimize the maximum among $\delta_i(a_1, b_1), \dots, \delta_i(a_m, b_m)$.

Formally, find the value of $$\min_{1 \leq i \leq n}\left\{\max_{1 \leq j \leq m} \delta_i(a_j, b_j)\right\}\text{.}$$

입력

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains two integers $n$ and $m$.

For the following $m$ lines, the $i$-th line contains two integers $a_i$ and $b_i$.

출력

For each test case, output an integer which denotes the minimum value.

제한

  • $2 \leq n \leq 2 \times 10^5$
  • $1 \leq m \leq 2 \times 10^5$
  • $1 \leq a_i, b_i \leq n$ for each $1 \leq i \leq m$
  • In each input, the sum of $n$ does not exeed $2 \times 10^5$. The sum of $m$ does not exceed $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

노트

For the first case,

$i$ $\delta_i(1, 2)$ $\delta_i(2, 3)$
1 2 1
2 1 2
3 1 1

Choosing $i = 3$ yields the minimum value $1$.