分数: 100 点
问题陈述
你有 N 杯子和 1 球。
杯子从左到右排成一排。
你拒绝了所有杯子,然后将球插入最左边的杯子。
然后,您将执行以下操作 Q 操作:
- 的 i-th 操作:交换位置 A_i-th 和 B_i左起第 3 个杯子。如果这些杯子之一装有球,则球也会移动。
由于你是魔法师,你可以施展如下魔法:
- 魔法:当球包含在 i从左边数第一个杯子,将球传送到相邻的杯子(即 (i-1)-th 或 (i+1)第一个杯子,如果存在)。
该魔法可以在第一次操作之前、两次操作之间或最后一次操作之后施展,但整个过程中最多只能施展一次。
找出在所有操作和可能施展魔法后可能容纳球的杯子的数量。
约束
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i < B_i \leq N
输入
输入由标准输入按以下格式给出:
N Q A_1 B_1 A_2 B_2 : A_Q B_Q
输出
打印最终可能容纳球的杯子的数量。
样本输入 1
10 3 1 3 2 4 4 5
示例输出 1
4
示例输入 2
20 3 1 7 8 20 1 19
示例输出 2
5