#include <bits/stdc++.h>
#define int long long
#define maxn 40
using namespace std;
int n,m;
int v[maxn];
map <int,int> ma;
int ans = INT_MAX;
void read(int x,int y){
	v[x] |= (1ll << (y - 1));
}
void out(int x,int l){
	int tot = 0;
	while(x){
		tot++;
		cout << (x & 1);
		x >>= 1;
	}
	while(tot < l){
		tot++;
		cout<<0;
	}
}
int cnt(int x){
	int sum = 0;
	while(x){
		if(x & 1){
			sum++;
		}
	}
	return sum;
}
void worka(int l,int r){
	for(int i = 0;i < (1ll << (n >> 1));i++){
		int s = i,tot = 0,ansx = 0,sum = 0;
		while(s){
			tot++;
			if(s & 1){
				ansx ^= v[tot];
				sum++;
			}
			s >>= 1;
		}
		if(ma.count(ansx)){
			ma[ansx] = min(ma[ansx],sum);
		}
		if(!ma.count(ansx)){
			ma[ansx] = sum;
		}
	}
}
void workb(int l,int r){
	for(int i = 0;i < (1ll << (n - (n >> 1)));i++){
		int s = i,tot = 0,ansx = 0,sum = 0;
		while(s){
			tot++;
			if(s & 1){
				ansx ^= v[tot + (n >> 1)];
				sum++;
			}
			s >>= 1;
		}
		ansx ^= ((1ll << n) - 1);
		if(ma.count(ansx)){
			int x = ma[ansx],sumx = 0;
			ans = min(ans,x + sum);
			
		}
	}
}
signed main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		read(i,i);
	}
	for(int i = 1,x,y;i <= m;i++){
		cin >> x >> y;
		read(x,y);
	}
	worka(1,n / 2);
	workb(n / 2 + 1,n);
	
	cout << ans;
}