#include <iostream>
#include <vector>
using namespace std;
 
int n,m;
vector<int> vis;
 
bool dfs(int w0,int w,vector<vector<int>> &G) {
	vis[w0]=1;
	for (int q=1; q<=n; q++) {
		if (G[w0][q]>0 && vis[q]==0) {
			if (q==w || dfs(q,w,G)==0) {
				G[w0][q]--; 
				G[q][w0]++;
				return 0;
			}
		}
	}
	return 1;
}
 
int main() {
	int u,v,i,k,res=10000000;
	scanf("%d %d\n",&n,&m);
	vector<vector<int>> G0(n+1,vector<int>(n+1,0));
	for (i=0; i<m; i++) {
		scanf("%d %d\n",&u,&v);
		G0[u][v]=1;
		G0[v][u]=1;
	}
	for (i=2; i<=n; i++) {
		k=0;
		vector<vector<int>> G=G0;
		vis=vector<int>(n+1,0);
		while (!dfs(1,i,G)) {
			k++;
			vis=vector<int>(n+1,0);
		}
		if (k<res) res=k;
	}
	printf("%d",res);
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG4sbTsKdmVjdG9yPGludD4gdmlzOwoKYm9vbCBkZnMoaW50IHcwLGludCB3LHZlY3Rvcjx2ZWN0b3I8aW50Pj4gJkcpIHsKCXZpc1t3MF09MTsKCWZvciAoaW50IHE9MTsgcTw9bjsgcSsrKSB7CgkJaWYgKEdbdzBdW3FdPjAgJiYgdmlzW3FdPT0wKSB7CgkJCWlmIChxPT13IHx8IGRmcyhxLHcsRyk9PTApIHsKCQkJCUdbdzBdW3FdLS07IAoJCQkJR1txXVt3MF0rKzsKCQkJCXJldHVybiAwOwoJCQl9CgkJfQoJfQoJcmV0dXJuIDE7Cn0KCmludCBtYWluKCkgewoJaW50IHUsdixpLGsscmVzPTEwMDAwMDAwOwoJc2NhbmYoIiVkICVkXG4iLCZuLCZtKTsKCXZlY3Rvcjx2ZWN0b3I8aW50Pj4gRzAobisxLHZlY3RvcjxpbnQ+KG4rMSwwKSk7Cglmb3IgKGk9MDsgaTxtOyBpKyspIHsKCQlzY2FuZigiJWQgJWRcbiIsJnUsJnYpOwoJCUcwW3VdW3ZdPTE7CgkJRzBbdl1bdV09MTsKCX0KCWZvciAoaT0yOyBpPD1uOyBpKyspIHsKCQlrPTA7CgkJdmVjdG9yPHZlY3RvcjxpbnQ+PiBHPUcwOwoJCXZpcz12ZWN0b3I8aW50PihuKzEsMCk7CgkJd2hpbGUgKCFkZnMoMSxpLEcpKSB7CgkJCWsrKzsKCQkJdmlzPXZlY3RvcjxpbnQ+KG4rMSwwKTsKCQl9CgkJaWYgKGs8cmVzKSByZXM9azsKCX0KCXByaW50ZigiJWQiLHJlcyk7CglyZXR1cm4gMDsKfQ==

NSA1IAoxIDIgCjIgMyAKMyA1IAo1IDIgCjIgNA==

5 5 
1 2 
2 3 
3 5 
5 2 
2 4