CODE FESTIVAL 2016 Relay (Parallel)

G - 超能力 / Magician


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する