← 返回题目列表

AtCoder · relay_g

G. 魔术师

中文机器翻译题面 查看原题

分数: 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