#include<cstdio>
#include<cstring>
const int N=500;
const int MAX=999999999;
int n,m;
struct qq
{
	int x,y;
	int other;
	int z,last;
};
qq s[N*N];
qq k[N*N];
int num,last[N];
int st1,ed1;
int h[N];
int q[N];//循环队列
int min;
int init1 (int x,int y,int z)
{
	num++;
	s[num].x=x;
	s[num].y=y;
	s[num].z=z;
	s[num].last=last[x];
	last[x]=num;
	return num;
}
void init(int x,int y,int z)
{
	int num1=init1(x,y,z),num2=init1(y,x,0);
	s[num1].other=num2;
	s[num2].other=num1;
}
void ready ()
{
	num=0;
	memset(last,-1,sizeof(last));
	for (int u=0;u<n;u++)
		init(u+n,u,1);
	return ;
}
bool bt ()
{
	memset(h,0,sizeof(h));
	int st=1,ed=2;
	q[st]=st1;h[st1]=1;
	while (st!=ed)
	{
		int x=q[st];
		for (int u=last[x];u!=-1;u=s[u].last)
		{
			int y=s[u].y;
			if (s[u].z>0&&h[y]==0)
			{
				h[y]=h[x]+1;
				q[ed]=y;
				ed++;
				if (ed>=N) ed=1;
			}
		}
		st++;
		if (st>=N) st=1;
	}
	if (h[ed1]==0) return false;
	return true;
}
int min1 (int x,int y)
{
	return x<y?x:y;
}
int find (int x,int f)
{
	if (x==ed1) return f;
	int s1=0,t;
	for (int u=last[x];u!=-1;u=s[u].last)
	{
		int y=s[u].y;
		if (s[u].z>0&&h[y]==(h[x]+1)&&s1<f)
		{
			t=find(y,min1(s[u].z,f-s1));
			//if (t!=MAX) printf("%d %d %d %d\n",x,s[u].x,s[u].y,s[u].z);
			s1+=t;
			s[u].z-=t;
			s[s[u].other].z+=t;
		}
	}
	if (s1==0) h[x]=0;
	return s1;
}
void check (int x,int y)
{
	int ans=0;
	st1=x;
	ed1=y+n;
	while (bt()==true)
	{
		ans=ans+find(st1,MAX);
		if (ans>=min) return ;
	}
	min=ans;
	return ;
}
int main()
{
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		if (n == 0) { printf("0\n"); continue; }  
        if (n == 1) { printf("1\n"); continue; }  
        if (m == 0) { printf("0\n"); continue; }  
	ready();
	for (int u=1;u<=m;u++)
	{
		while (getchar()!='(');
		int x,y;
		scanf("%d,%d)",&x,&y);
		init(y,x+n,MAX);
		init(x,y+n,MAX);
	}
	for (int u=1;u<=num;u++) k[u]=s[u];
	min=MAX;
	for (int u=0;u<n;u++)//枚举起点 
	{
		for (int i=0;i<n;i++)//枚举终点
		{
			if (u==i) continue;
			for (int j=1;j<=num;j++) s[j]=k[j];
			check(u,i);
		}
	}
	if (min==MAX) min=n;
	printf("%d\n",min);
	}
	return 0;
}