【题目描述】

环形展馆闭馆后，两台巡检机器人需要依次赶往系统指定的检查点．有时一个阶段只有一处故障，有时两处故障必须同时处理．

环形展馆中有 $n$ 个检查点，沿顺时针方向依次编号为 $1,2,\ldots,n$．检查点 $n$ 与检查点 $1$ 相邻．

两台机器人初始分别位于检查点 $1$ 和检查点 $n$．它们之间没有区别，可以位于同一个检查点，也可以在移动过程中相遇或互相经过．

两点 $x,y$ 之间的移动距离定义为环上两条路径中较短一条的长度：

$$\operatorname{dis}(x,y)=\min(|x-y|,n-|x-y|).$$

接下来依次进行 $q$ 个巡检阶段．第 $i$ 个阶段给出一个包含 $c_i$ 个检查点的集合 $S_i$，其中 $c_i\in\{1,2\}$．在该阶段结束时，对于 $S_i$ 中的每个检查点，都必须至少有一台机器人位于该处．

两台机器人可以在相邻阶段之间任意移动．一次移动的代价等于机器人经过的边数，一个方案的总代价等于两台机器人全部移动距离之和．

请计算完成所有巡检阶段所需的最小总代价．

【输入描述】

第一行输入两个整数 $n,q$，分别表示检查点数量和巡检阶段数量．

接下来的 $q$ 行描述各个巡检阶段．每行首先输入一个整数 $c_i$：

• 如果 $c_i=1$，随后输入一个整数 $p_i$，表示 $S_i=\{p_i\}$；
• 如果 $c_i=2$，随后输入两个不同的整数 $p_i,r_i$，表示 $S_i=\{p_i,r_i\}$．

【输出描述】

输出一个整数，表示完成所有巡检阶段所需的最小总代价．

---

【样例 1】

【样例 1 输入】

8 4
1 3
1 7
2 2 6
1 4

【样例 1 输出】

7

【样例 1 解释】

一种最优方案如下：

• 第一阶段，将位于 $1$ 的机器人移动到 $3$，代价为 $2$；
• 第二阶段，将位于 $8$ 的机器人移动到 $7$，代价为 $1$；
• 第三阶段，将位于 $7$ 的机器人移动到 $6$，位于 $3$ 的机器人移动到 $2$，总代价增加 $2$；
• 第四阶段，将位于 $2$ 或 $6$ 的一台机器人移动到 $4$，总代价增加 $2$．

总代价为 $7$．

---

【样例 2】

【样例 2 输入】

1 3
1 1
1 1
1 1

【样例 2 输出】

0

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例满足 $n,q\le 30$．

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例满足 $n,q\le 2000$．

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例中所有阶段均满足 $c_i=2$．

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例中所有要求的检查点编号均属于 $\{1,n\}$．

---

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．

该样例中所有阶段均满足 $c_i=1$．

---

【样例 8】

见选手目录下的 Data/sample8.in 和 Data/sample8.ans．

该样例无特殊性质．

【数据规模与约定】

对于所有测试数据，保证：

• $1\le n,q\le3\times10^5$；
• $c_i\in\{1,2\}$ 且 $c_i\le n$；
• $1\le p_i,r_i\le n$；
• 当 $c_i=2$ 时，$p_i\ne r_i$．

子任务编号	分数	特殊性质
$1$	$10$	$n,q\le30$
$2$	$25$	$n,q\le2000$
$3$	$15$	对所有阶段均有 $c_i=2$
$4$	$10$	所有要求的检查点编号均属于 $\{1,n\}$
$5$	$15$	对所有阶段均有 $c_i=1$
$6$	$25$	无特殊性质

【大样例下载链接】

点击下载本题选手目录