// UUID: a8f87c89-b052-405a-be20-709708e4489d
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;


	vector<int> diffs(n+1, 0);
	for (int i=0;i<m;i++){
		int start, end;
		cin >> start >> end;
		diffs[start]++;
		diffs[end]--;
	}

	for(int d:diffs){
		cout << d << " ";
	}
	cout << "\n";

	if(m==1){
		cout << (diffs[1] == 0 ? 1 : 0);
		return 0;
	}

	vector<int> totals(n+1, 0);
	
	totals[1] = diffs[1];
	
	for(int i=2;i<=n;i++){
		totals[i] = totals[i-1] + diffs[i];
	}
	for(int t:totals){
		cout << t << " ";
	}
	cout << "\n";

	int empty_section_count = 0;

	int previous;
	int current = totals[0];
	for(int i=1;i<=n;i++){
		previous = current;
		current = totals[i];

		if(previous == 0 && current ==0){
			continue;
		}else if(previous == 0 && current != 0){
			continue;
		}else if(previous != 0 && current == 0){
			empty_section_count++;
		}else{  // previous != 0 && current != 0
			continue;
		}



	}
	cout << empty_section_count;



	// for(int i=0;i<=n;i++){
	// 	if (totals[i]==0){
	// 		empty_section_count++;
	// 		while(i<n && totals[i]==0){
	// 			i++;
	// 		}
	// 	}
	// }

	// cout << (totals[1] == 0 ? empty_section_count: empty_section_count - 1);
}