题目描述

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$。

输出格式

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

0 3 4
1 2
2 3
2 2
3 1

2

提示

样例 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}

• 特殊性质 A：对于每个正整数 $t$，保证满足 $x_i=t$ 的正整数 $i$ 的数量为偶数。
• 特殊性质 B：对于每个正整数 $t$，保证满足 $x_i=t$ 的正整数 $i$ 不超过一个。