P14564 圆环

Yuki 是一个喜欢玩游戏的机器人！ Yuki 最喜欢玩的游戏的规则如下： - 游戏在一个长度为 $n$ 的圆环上进行，其中位置 $i$ 与位置 $(i \bmod n)+1$ 相邻；初始时，Yuki 的两只手分别位于位置 $1$ 和位置 $n$；在游戏过程中，Yuki 可以花费一点体力，将其中一只手移动到**相邻**的一个位置上。 - 这个圆环上一共会出现 $m$ 个音符；在第 $x_i$ 秒时，位置 $y_i$ 会出现一个音符，此时需要满足 Yuki 有**至少一只手**位于位置 $y_i$，否则 Yuki 将输掉游戏；若 Yuki 完成了所有的要求，那么称她完成了游戏。 - 保证没有音符重叠；即对于每对满足 $1 \le i \lt j \le m$ 的正整数 $i,j$，保证 $x_i\ne x_j$ 或 $y_i \ne y_j$。 - 保证每个时刻最多有两个音符；即对于每个正整数 $t$，保证满足 $x_i=t$ 的正整数 $i$ 不超过两个。 由于 Yuki 是一个机器人，所以她玩这个游戏很有优势——不论怎么移动，她的手都不会打结，并且她的两只手也可以移动到相同的位置上。 现在，Yuki 想让你帮助她求出，她完成游戏至少要花费多少点体力。容易证明 Yuki 一定可以完成游戏。

第一行包含三个整数 $c,n,m$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。 接下来 $m$ 行，第 $i$ 行包含两个整数 $x_i,y_i$。

输出一行，包含一个整数，表示她完成游戏所至少要花费的体力的点数。

### 样例 2 见下发文件中的 $\textbf{\textit{circle/circle2.in}}$ 与 $\textbf{\textit{circle/circle2.ans}}$。 该组样例满足测试点 $3$ 的限制。 ### 样例 3 见下发文件中的 $\textbf{\textit{circle/circle3.in}}$ 与 $\textbf{\textit{circle/circle3.ans}}$。 该组样例满足测试点 $7$ 的限制。 ### 样例 4 见下发文件中的 $\textbf{\textit{circle/circle4.in}}$ 与 $\textbf{\textit{circle/circle4.ans}}$。 该组样例满足测试点 $13$ 的限制。 ### 样例 5 见下发文件中的 $\textbf{\textit{circle/circle5.in}}$ 与 $\textbf{\textit{circle/circle5.ans}}$。 该组样例满足测试点 $16$ 的限制。 ### 样例 6 见下发文件中的 $\textbf{\textit{circle/circle6.in}}$ 与 $\textbf{\textit{circle/circle6.ans}}$。 该组样例满足测试点 $18$ 的限制。 ### 样例 7 见下发文件中的 $\textbf{\textit{circle/circle7.in}}$ 与 $\textbf{\textit{circle/circle7.ans}}$。 该组样例满足测试点 $25$ 的限制。 ### 数据范围 对于所有测试数据，保证： - $2 \le n \le 3\times10^5$，$1 \le m \le 3\times10^5$； - $1 \le x_i \le m$，$1 \le y_i \le n$； - 对于每对满足 $1 \le i \lt j \le m$ 的正整数 $i,j$，$x_i\ne x_j$ 或 $y_i \ne y_j$； - 对于每个正整数 $t$，满足 $x_i=t$ 的正整数 $i$ 不超过两个。 ::cute-table{tuack} | 测试点编号 | $n,m \le$ | 特殊性质 | | :--------: | :-----------: | :------: | | $1\sim2$ | $20$ | 无 | | $3\sim4$ | $80$ | 无 | | $5$ | $400$ | A | | $6$ | $400$ | B | | $7\sim8$ | $400$ | 无 | | $9\sim10$ | $5\times10^3$ | A | | $11\sim12$ | $5\times10^3$ | B | | $13\sim15$ | $5\times10^3$ | 无 | | $16\sim17$ | $3\times10^5$ | A | | $18\sim21$ | $3\times10^5$ | B | | $22\sim25$ | $3\times10^5$ | 无 | - 特殊性质 A：对于每个正整数 $t$，保证满足 $x_i=t$ 的正整数 $i$ 的数量为偶数。 - 特殊性质 B：对于每个正整数 $t$，保证满足 $x_i=t$ 的正整数 $i$ 不超过一个。