#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T> inline istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> inline ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

template<typename T> inline T min(vector<T>& v) {return *min_element(v.begin(), v.end());}

template<typename T> inline T max(vector<T>& v) {return *max_element(v.begin(), v.end());}

template<typename T> inline int min_element(vector<T>& v) {return min_element(v.begin(), v.end()) - v.begin();}

template<typename T> inline int max_element(vector<T>& v) {return max_element(v.begin(), v.end()) - v.begin();}

template<typename T> inline void sort(vector<T>& v) {sort(v.begin(), v.end());}

template<typename T, typename Function> inline void sort(vector<T>& v, Function func) {sort(v.begin(), v.end(), func);}

template<typename T> inline void rsort(vector<T>& v) {sort(v.rbegin(), v.rend());}

template<typename T> inline void reverse(vector<T>& v) {reverse(v.begin(), v.end());}

template<typename T> inline void unique(vector<T>& v) {v.erase(unique(v.begin(), v.end()), v.end());}

template<typename T> inline void nth_element(vector<T>& v, int n) {nth_element(v.begin(), v.begin() + n, v.end());}

template<typename T> inline bool next_permutation(vector<T>& v) {return next_permutation(v.begin(), v.end());}

template<typename T> inline int find(vector<T>& v, T t) {return find(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int in(vector<T> v, T t) {return find(v, t) != (int)v.size();}

template<typename T> inline int lower_bound(vector<T>& v, T t) {return lower_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int upper_bound(vector<T>& v, T t) {return upper_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline T accumulate(const vector<T>& v, function<T(T, T)> func = plus<T>()) {return accumulate(v.begin(), v.end(), T(), func);}

template<typename T> inline void adjacent_difference(vector<T>& v) {adjacent_difference(v.begin(), v.end(), v.begin());}

template<typename T> inline void adjacent_difference(vector<T>& v, vector<T>& u) {adjacent_difference(v.begin(), v.end(), u.begin());}

template<typename T> inline void partial_sum(vector<T>& v, vector<T>& u) {partial_sum(v.begin(), v.end(), u.begin());}

template<typename T> inline T inner_product(vector<T>& v, vector<T>& u) {return inner_product(v.begin(), v.end(), u.begin(), T(0));}

template<typename T> inline int count(const vector<T>& v, T t) {return count(v.begin(), v.end(), t);}

template<typename T, typename Function> inline int count_if(const vector<T>& v, Function func) {return count_if(v.begin(), v.end(), func);}

template<typename T, typename Function> inline void remove_if(vector<T>& v, Function func) {v.erase(remove_if(v.begin(), v.end(), func), v.end());}

template<typename T, typename Function> inline bool any_of(vector<T> v, Function func) {return any_of(v.begin(), v.end(), func);}

template<typename T> inline vector<T> subvector(vector<T>& v, int a, int b) {return vector<T>(v.begin() + a, v.begin() + b);}

template<typename T> inline int kinds(const vector<T>& v) {return set<T>(v.begin(), v.end()).size();}

template<typename T> inline void iota(vector<T>& v) {iota(v.begin(), v.end(), T());}

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n + 2), u(n + 2);
  v[1] = u[2] = 1;
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    swap(v[a], v[b]);
    swap(u[a], u[b]);
    if (v[a]) u[a - 1] = u[a + 1] = 1;
    if (v[a - 1] || v[a + 1]) u[a] = 1;
    if (v[b]) u[b - 1] = u[b + 1] = 1;
    if (v[b - 1] || v[b + 1]) u[b] = 1;
  }
  u[0] = u.back() = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[i]) u[i] = 1;
  }
  cout << accumulate(u) << endl;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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.

Examples

Input

10 3
1 3
2 4
4 5


Output

4


Input

20 3
1 7
8 20
1 19


Output

5

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T> inline istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> inline ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

template<typename T> inline T min(vector<T>& v) {return *min_element(v.begin(), v.end());}

template<typename T> inline T max(vector<T>& v) {return *max_element(v.begin(), v.end());}

template<typename T> inline int min_element(vector<T>& v) {return min_element(v.begin(), v.end()) - v.begin();}

template<typename T> inline int max_element(vector<T>& v) {return max_element(v.begin(), v.end()) - v.begin();}

template<typename T> inline void sort(vector<T>& v) {sort(v.begin(), v.end());}

template<typename T, typename Function> inline void sort(vector<T>& v, Function func) {sort(v.begin(), v.end(), func);}

template<typename T> inline void rsort(vector<T>& v) {sort(v.rbegin(), v.rend());}

template<typename T> inline void reverse(vector<T>& v) {reverse(v.begin(), v.end());}

template<typename T> inline void unique(vector<T>& v) {v.erase(unique(v.begin(), v.end()), v.end());}

template<typename T> inline void nth_element(vector<T>& v, int n) {nth_element(v.begin(), v.begin() + n, v.end());}

template<typename T> inline bool next_permutation(vector<T>& v) {return next_permutation(v.begin(), v.end());}

template<typename T> inline int find(vector<T>& v, T t) {return find(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int in(vector<T> v, T t) {return find(v, t) != (int)v.size();}

template<typename T> inline int lower_bound(vector<T>& v, T t) {return lower_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int upper_bound(vector<T>& v, T t) {return upper_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline T accumulate(const vector<T>& v, function<T(T, T)> func = plus<T>()) {return accumulate(v.begin(), v.end(), T(), func);}

template<typename T> inline void adjacent_difference(vector<T>& v) {adjacent_difference(v.begin(), v.end(), v.begin());}

template<typename T> inline void adjacent_difference(vector<T>& v, vector<T>& u) {adjacent_difference(v.begin(), v.end(), u.begin());}

template<typename T> inline void partial_sum(vector<T>& v, vector<T>& u) {partial_sum(v.begin(), v.end(), u.begin());}

template<typename T> inline T inner_product(vector<T>& v, vector<T>& u) {return inner_product(v.begin(), v.end(), u.begin(), T(0));}

template<typename T> inline int count(const vector<T>& v, T t) {return count(v.begin(), v.end(), t);}

template<typename T, typename Function> inline int count_if(const vector<T>& v, Function func) {return count_if(v.begin(), v.end(), func);}

template<typename T, typename Function> inline void remove_if(vector<T>& v, Function func) {v.erase(remove_if(v.begin(), v.end(), func), v.end());}

template<typename T, typename Function> inline bool any_of(vector<T> v, Function func) {return any_of(v.begin(), v.end(), func);}

template<typename T> inline vector<T> subvector(vector<T>& v, int a, int b) {return vector<T>(v.begin() + a, v.begin() + b);}

template<typename T> inline int kinds(const vector<T>& v) {return set<T>(v.begin(), v.end()).size();}

template<typename T> inline void iota(vector<T>& v) {iota(v.begin(), v.end(), T());}

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n + 2), u(n + 2);
  v[1] = u[2] = 1;
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    swap(v[a], v[b]);
    swap(u[a], u[b]);
    if (v[a]) u[a - 1] = u[a + 1] = 1;
    if (v[a - 1] || v[a + 1]) u[a] = 1;
    if (v[b]) u[b - 1] = u[b + 1] = 1;
    if (v[b - 1] || v[b + 1]) u[b] = 1;
  }
  u[0] = u.back() = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[i]) u[i] = 1;
  }
  cout << accumulate(u) << endl;
}

```