#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==