/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
N 個のコップと 1 個の玉があります。
N 個のコップは左右に 1 列に並べられています。
コップを全てひっくり返して、 左から 1 番目のコップの中に玉を入れました。
以下のような操作を Q 回行います。
- i 回目の操作：左から A_i 番目のコップと左から B_i 番目のコップの場所を入れ替える。このときコップの中に玉が入っていれば、玉もコップとともに場所が移る。
あなたはマジシャンなので、以下の超能力を使うことが出来ます。
- 超能力：左から i 番目のコップに玉が入っているとき、その玉を隣のコップ(左からi-1 番目もしくは i+1 番目のコップ)の中に瞬間移動させる。ただし、左から0 番目や N+1 番目のコップは存在しないので、そこに瞬間移動させることはできない。
超能力は、すべての操作を始める前か、操作と操作の間か、すべての操作を終えた後に使うことが出来ます。
ただし、超能力を使って良いのは全体を通してたかだか 1 回までです。
全ての操作とたかだか 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
Score : 100 points
Problem Statement
You have N cups and 1 ball.
The cups are arranged in a row, from left to right.
You turned down all the cups, then inserted the ball into the leftmost cup.
Then, you will perform the following Q operations:
- The i-th operation: swap the positions of the A_i-th and B_i-th cups from the left. If one of these cups contains the ball, the ball will also move.
Since you are a magician, you can cast a magic described below:
- Magic: When the ball is contained in the i-th cup from the left, teleport the ball into the adjacent cup (that is, the (i-1)-th or (i+1)-th cup, if they exist).
The magic can be cast before the first operation, between two operations, or after the last operation, but you are allowed to cast it at most once during the whole process.
Find the number of cups with a possibility of containing the ball after all the operations and possibly casting the magic.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i < B_i \leq N
Input
The input is given from Standard Input in the following format:
N Q A_1 B_1 A_2 B_2 : A_Q B_Q
Output
Print the number of cups with a possibility of eventually containing the ball.
Sample Input 1
10 3 1 3 2 4 4 5
Sample Output 1
4
Sample Input 2
20 3 1 7 8 20 1 19
Sample Output 2
5