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}\{\max_{1 \leq j \leq m} \delta_i(a_j, b_j)\}

Note from SCNUOJ admin: we don't have the official test data sets, and all tests used here are randomly generated, so expect weak tests and/or even wrong input format. Contact one of the admins if you wish to improve the tests.

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.

• 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.

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

For the first case,

Choosing i = 3 yields the minimum value 1.