White Cloud has a square of n*n from (1,1) to (n,n).
White Rabbit wants to put in several cars. Each car will start moving at the same time and move from one side of one row or one line to the other. All cars have the same speed. If two cars arrive at the same time and the same position in a grid or meet in a straight line, both cars will be damaged.
White Cloud will destroy the square m times. In each step White Cloud will destroy one grid of the square(It will break all m grids before cars start).Any car will break when it enters a damaged grid.

The first line of input contains two integers n and m(n <= 100000,m <= 100000)
For the next m lines,each line contains two integers x,y(1 <= x,y <= n), denoting the grid which is damaged by White Cloud.

Print a number,denoting the maximum number of cars White Rabbit can put into.

2 0

4

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 1e6 + 10;

const int mod = 10000007;

typedef long long ll;

int vis1[maxn], vis2[maxn] ;

struct node{

     int x, y ;

}e[maxn];

int n , m ;

int main(){

    while( scanf("%d %d",&n,&m) != EOF) {

        memset(vis1,0,sizeof(vis1)) ;

        memset(vis2,0,sizeof(vis2)) ;

        long long int sum = n%2 == 0 ? 2*n : (n/2)*4 + 1 ;

        for( int i = 1 ; i <= m ; i ++ ){

            scanf("%d %d",&e[i].x,&e[i].y) ;

            vis1[e[i].x] = 1 ; vis2[e[i].y] = 1 ;

        }

        long long ans = 0 ;

        for(int i = 1 ; i <= n ; i ++) {

            if(vis1[i]) ans ++ ;

            if(vis2[i]) ans ++ ;

        }

        if( n%2 && ( vis1[(n + 1)/2] || vis2[(n + 1)/2] ) ) {

            ans -- ;

        }

        printf("%lld\n",sum - ans) ;

    }

    return 0 ;

}