#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

#define rep(i, l, r) for(int i = l; i <= r; i++)
#define down(i, l, r) for(int i = l; i >= r; i--)
#define MS 12345
#define MAX 1037471823
#define Q 103

using namespace std;

int n, m, k[MS], r[MS], l[MS], next[MS], last[MS], h[MS], s[MS], a, now;
bool b[MS];
struct node
{
	int x, y;
	bool operator < (const node &k) const { return x < k.x || (x == k.x && y < k.y); }
} c[2345678];

int main()
{
	scanf("%d%d", &n, &m);
	rep(i, 1, m) scanf("%d%d", &c[i].x, &c[i].y);
	rep(i, 1, m) c[i+m].x = c[i].y, c[i+m].y = c[i].x; m *= 2;
	sort(c+1, c+1+m); c[m+1].x = MAX;
	rep(i, 2, m) if (c[i].x == c[i-1].x && c[i].y == c[i-1].y) c[i] = c[m+1];
	sort(c+1, c+1+m); while (c[m].x == MAX) m--;
	k[1] = 1; rep(i, 2, n+1) { k[i] = k[i-1]; while (c[k[i]].x < i) k[i]++; }
	
	h[0] = n; rep(i, 2, n) next[i] = i-1; rep(i, 1, n-1) last[i] = i+1; now = 0;
	down(i, n, 1)
	{
		l[i] = h[now]; b[l[i]] = true; h[now] = next[h[now]]; if (h[now] != 0) last[h[now]] = 0;
		while (h[now] == 0 && now > 0) now--;
		rep(j, k[l[i]], k[l[i]+1]-1) if (b[c[j].y] == false) 
		{
			a = c[j].y;
			if (a != h[r[a]]) next[last[a]] = next[a], last[next[a]] = last[a]; else h[r[a]] = next[a], last[next[a]] = 0;
			r[a]++; 
			if (r[a] > now) now = r[a];
			next[a] = h[r[a]]; last[h[r[a]]] = a; h[r[a]] = a; last[a] = 0;
		}
	}
	
	now = 0;
	down(i, n, 1) 
	{
		rep(j, 1, now) b[j] = false;
		rep(j, k[l[i]], k[l[i]+1]-1) b[s[c[j].y]] = true; 
		a = 0;
		down(j, now, 1) if (b[j] == false) a = j;
		if (a == 0) now++, s[l[i]] = now; else s[l[i]] = a;
	}
	printf("%d\n", now);
	return 0;
}