Problem Description

There are $ N $ cups and $ 1 $ ball.

The $ N $ cups are arranged in a single row from left to right.

All the cups are initially flipped over, and the ball is placed inside the first cup from the left.

The following operation is performed $ Q $ times:

• $ i $-th operation: Swap the positions of the $ A_i $-th cup and the $ B_i $-th cup from the left. If the ball is inside one of these cups, it moves along with the cup.

As a magician, you can use the following telekinetic power:

• Telekinetic power: When the ball is in the $ i $-th cup from the left, instantly move the ball to an adjacent cup (the $ i-1 $-th or $ i+1 $-th cup). However, since the $ 0 $-th and $ N+1 $-th cups do not exist, the ball cannot be moved there.

The telekinetic power can be used either before starting all operations, between any operations, or after all operations.

However, you can use the telekinetic power at most once throughout the entire process.

Determine the number of cups that could potentially contain the ball after all operations and at most one use of the telekinetic power.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_Q $ $ B_Q $

Output Format

Output the number of cups that could potentially contain the ball at the end.

Sample Input and Output

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

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i < B_i \leq N$

见题面 Input 部分

见题面 Output 部分