RT

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
int s, n, m, cnt, d[N], ans[N];
vector < int > v[N];

long long read()
{
	long long sum = 0, w = 1;
	char ch = getchar();
	while (!isdigit(ch) && ch != '-')  ch = getchar();
	if (ch == '-')  w = -1, ch = getchar();
	while (isdigit(ch))  sum = (sum << 3) + (sum << 1) + ch - '0', ch = getchar();
	return sum * w;
}

int main()
{
	s = n = read(), m = read();
	for (int i = 1; i <= m; i++)
	{
		int a = read(), b = read();
		if (a == 1)  a++;
		if (a == n)  a--;
		if (a == b)  continue;
		if (a < b)
			for (int j = a + 1; j <= b; j++)
				v[j].push_back(j - 2), d[j - 2]++;
		else
			for	(int j = b; j <= a + 1; j++)
				v[j].push_back(j + 2), d[j + 2]++;
	}
//	for (int i = 1; i <= n; i++)
//		printf("%d ", d[i]);
//	printf("\n");
	while (s > 0)
	{
		int i; 
		bool f = 0;
		for (i = 1; i <= n; i++)
			if (d[i] == 0)
			{
				f = 1;
				break;
			}
		d[i]--;
		if (!f)
		{
			printf("QED\n");
			return 0;
		} 
		ans[i] = ++cnt;
		s--;
		int l = v[i].size();
		for (int j = 0; j < l; j++)
			d[v[i][j]]--;
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}