#include <stdio.h>

#include <memory.h>

#include <stdlib.h>


#define N 1000


struct node {

node *next;

int p;

};


int size;

int r[N*N][2];

int rc;

int ans;


node *g[N*N];

int na,nb;


int tabler[N][N];

int tablel[N][N];


int edge[N*N][2];

int ec;


int sel[N*N];

int check[N*N];


int path[N*N];

int pc;


void init(int a[][N]) {

int i,j;

for(i=0;i<size;i++) {

for(j=0;j<size;j++) {

a[i][j]=-2;

}

}

}


void set_obstacle(int a[][N]) {

int i;

for(i=0;i<rc;i++) {

a[r[i][0]][r[i][1]]=-1;

}

}


void input() {

int i;

int a,b;

scanf("%d",&size);

scanf("%d",&rc);

for(i=0;i<rc;i++) {

scanf("%d %d",&a,&b);

a--;

b--;

r[i][0]=a;

r[i][1]=b;

}

}


int mark_grid(int a[][N],int dir) {

int i,j,k;

int ki,kj;

int cnt;

cnt=0;

for(i=0;i<size;i++) {

for(j=0;j<size;j++) {

if (a[i][j]==-2) {

for(k=0;k<size;k++) {

ki=i+k;

kj=j+k*dir;

if (ki>=size || kj>=size || kj<0) break;

if (a[ki][kj]!=-2) break;

a[ki][kj]=cnt;

}

cnt++;

}

}

}

return cnt;

}


int sf(const void *a,const void *b) {

int aa,bb;

aa=((int *)a)[0];

bb=((int *)b)[0];

if (aa<bb) return -1;

if (aa>bb) return 1;

aa=((int *)a)[1];

bb=((int *)b)[1];

if (aa<bb) return -1;

if (aa>bb) return 1;

return 0;

}


void set_edge(int a,int b) {

node *tmp;

tmp=(node *)malloc(sizeof(node));

tmp->p=b;

tmp->next=g[a];

g[a]=tmp;

}


void graph(int a[][N],int b[][N]) {

int i,j;

ec=0;

for(i=0;i<size;i++) {

for(j=0;j<size;j++) {

edge[ec][0]=a[i][j];

edge[ec][1]=b[i][j];

ec++;

}

}

qsort(edge,ec,sizeof(edge[0]),sf);


for(i=0;i<ec;i++) {

for(j=i+1;j<ec;j++) {

if (edge[i][0]==edge[j][0] && edge[i][1]==edge[j][1]) {

edge[j][0]=-1;

}

else break;

}

i=j-1;

}



for(i=0;i<na;i++) {

g[i]=NULL;

}

for(i=0;i<ec;i++) {

if (edge[i][0]==-1) continue;

set_edge(edge[i][0],edge[i][1]);

}

}


void make_graph() {

init(tabler);

init(tablel);

set_obstacle(tabler);

set_obstacle(tablel);

na=mark_grid(tabler,1);

nb=mark_grid(tablel,-1);

graph(tabler,tablel);

}


int dfs(int p) {

int b,c;

node *tmp;

if (check[p]==1) return 0;


check[p]=1;

tmp=g[p];

for(;;) {

if (tmp==NULL) break;

b=tmp->p;

c=sel[b];

path[pc]=p;

path[pc+1]=b;

pc+=2;

if (c==-1) return 1;

if (dfs(c)==1) return 1;

pc-=2;


tmp=tmp->next;

}

return 0;

}


void match() {

int i,j;

int a,b;

int found;

for(i=0;i<nb;i++) {

sel[i]=-1;

}

ans=0;

for(i=0;i<na;i++) {

if (i==5) {

a=1;

}

memset(check,0,na*4);

pc=0;

found=dfs(i);

if (found) {

ans++;

for(j=0;j<pc;j+=2) {

a=path[j];

b=path[j+1];

sel[b]=a;

}

}

}

}


void proc() {

make_graph();

match();

}


void output() {

printf("%d\n",ans);

}


int main() {

input();

proc();

output();

return 0;

}




초등학교 문제 풀이 그켬ㅋㅋㅋ

이런거 푸는거 보면 머리 진짜 좋은거같다..