# include <stdio.h>

int a[100][100],vizitat[100],st[100],vf,k,n,nr,nr1;

void zero(){
	int i;
	for(i=1;i<=n;i++){
		vizitat[i]=0;
		st[i]=0;
	}
}

void citire(){
	int i,j,k,m;
	scanf("%d%d",&n,&m);
	for(k=1;k<=m;k++){
		scanf("%d%d",&i,&j);
		a[i][j]=a[j][i]=1;
	}
}

void init(int k){
	vf=1;
	st[vf]=k;
	vizitat[k]=1;
}

int este_vida(){
	return vf==0;
}

void adaug(int i){
	vf++;
	st[vf]=i;
	vizitat[i]=1;
}

void elimin(){
	vf--;
}

void prelucrare(){
	int i=1,k=st[vf];
	while(i<=n && (a[k][i]==0 || (a[k][i]==1 && vizitat[i]==1))) i++;
	if(i==n+1)
		elimin();
	 else {nr1++;
		   adaug(i);
	 }
}

int main(){
	int i;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	scanf("%d",&k);
	printf("Nodurile vizitate prin metoda DF sunt:\n");
	for(i=1;i<=n;i++){
		k=i;
		init(k);
		nr1=0;
		while(!este_vida()) prelucrare();
		if(nr1>nr)
			nr=nr1;
		zero();
	}
	printf("%d",nr+1);
	return 0;
}