//Tudose Vlad Andrei
//O((N + M) * log(N)) - 100 de puncte
#include <cstdio>
#include <vector>
#define INPUT "dag.in"
#define OUTPUT "dag.out"
#define MAXN 100001
using namespace std;
int Deg[MAXN], Q[MAXN], n;
vector<int> G[MAXN];

int max(int a, int b)
{
	return a > b ? a : b;
}

int ok(int m)
{
	int i, l = 0, r = -1, x;
	
	for(i = 1; i <= n; ++i)
	{
		Deg[i] = G[i].size();
		if(Deg[i] <= m)
			Q[++r] = i;
	}
	while(l <= r)
	{
		x = Q[l++];
		for(i = 0; i < G[x].size(); ++i)
			if(--Deg[G[x][i]] == m)
				Q[++r] = G[x][i];
	}

	return r + 1 == n;
}

int main()
{
	int m, x, y, l, r;

	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);

	scanf("%d%d", &n, &m);
	while(m--)
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	l = 1; r = 0;
	for(int i = 1; i <= n; ++i)
		r = max(r, G[i].size());

	while(l < r)
	{
		m = (l + r) >> 1;
		if(ok(m))
			r = m;
		else
			l = m + 1;
	}

	printf("%d\n", l);
	return 0;
}
