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

出力

最終的に玉が入っている可能性があるコップの個数を出力せよ。

10 3
1 3
2 4
4 5

4

20 3
1 7
8 20
1 19

5