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

int main() {
	int N, M; cin >> N >> M;
	vector<int>T(N+1);
	for(int i = 0; i < M; i++)
	{
		int s, e; cin >> s >> e;
		T[s]++;
		T[e]--;
	}
	for(int i = 1; i <= N; i++)T[i] += T[i-1];
	T[0]++;
	int mx = -1, bg = -1, c = 0, c_bg;
	for(int i = 1; i <= N; i++)
	{
		if(T[i] == 0)
		{
			c++;
			if(T[i-1] != 0)
			{
				c_bg = i;
			}
		}
		else
		{
			if(c > mx)
			{
				mx = c;
				bg = c_bg;
			}
			c = 0;
		}
	}
	if(mx == -1)
	{
		cout << mx;
		return 0;
	}
	mx--;
	bg++;
	for(int i : T)cout << i << " ";
	cout << "\n"; 
	cout << mx << " " << bg;
}