Alyona's mother wants to present an array of n non-negative integers to Alyona. The array should be special. 

Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays. Subarray is a set of some subsequent elements of the array. The i-th subarray is described with two integers l_{i} and r_{i}, and its elements are a[l_{i}], a[l_{i} + 1], ..., a[r_{i}].

Alyona is going to find mex for each of the chosen subarrays. Among these m mexes the girl is going to find the smallest. She wants this minimum mex to be as large as possible. 

You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.

The mex of a set S is a minimum possible non-negative integer that is not in S.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5).

The next m lines contain information about the subarrays chosen by Alyona. The i-th of these lines contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n), that describe the subarray a[l_{i}], a[l_{i} + 1], ..., a[r_{i}].


-----Output-----

In the first line print single integer — the maximum possible minimum mex.

In the second line print n integers — the array a. All the elements in a should be between 0 and 10^9.

It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 10^9.

If there are multiple solutions, print any of them.


-----Examples-----
Input
5 3
1 3
2 5
4 5

Output
2
1 0 2 1 0

Input
4 2
1 4
2 4

Output
3
5 2 0 1


-----Note-----

The first example: the mex of the subarray (1, 3) is equal to 3, the mex of the subarray (2, 5) is equal to 3, the mex of the subarray (4, 5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, m) = [int(i) for i in input().split()]
mn = n
for i in range(m):
	(l, r) = [int(i) for i in input().split()]
	mn = min(mn, r - l + 1)
a = list(range(mn))
print(mn)
print(*(a * ((n + len(a) - 1) // len(a)))[:n])


(n, m) = map(int, input().split())
mex = 10000000
for i in range(m):
	(a, b) = map(int, input().split())
	mex = min(mex, b - a)
mex = mex + 1
print(mex)
num = 0
x = ' '.join([str(i % mex) for i in range(n)])
print(x)


(n, m) = map(int, input().split())
ans = n
for i in range(m):
	(x, y) = map(int, input().split())
	ans = min(ans, y - x + 1)
print(ans)
for i in range(n):
	print(i % ans, end=' ')
print()


(n, m) = map(int, input().split())
mex = 10 ** 9
for i in range(m):
	(l, r) = list(map(int, input().split()))
	mex = min(mex, r - l + 1)
print(mex)
a = [i % mex for i in range(n)]
print(' '.join(map(str, a)))


(n, m) = map(int, input().split())
minx = 268435455
for i in range(0, m):
	(u, v) = map(int, input().split())
	minx = min(v - u + 1, minx)
print(minx)
for i in range(0, n):
	print(i % minx, end=' ')


(n, m) = map(int, input().split())
(l, r) = map(int, input().split())
min = r - l
for _ in range(m - 1):
	(l, r) = map(int, input().split())
	if r - l < min:
		min = r - l
min += 1
print(min)
for i in range(n):
	print(i % min, end=' ')


(n, m) = map(int, input().split())
lens = []
answer = []
for i in range(m):
	(n1, n2) = map(int, input().split())
	lens.append(n2 - n1 + 1)
k = min(lens)
w = 0
while len(answer) < n:
	q = w * k
	for i in range(k):
		if i + q == n:
			break
		answer.append(i)
	w += 1
print(k)
for elem in answer:
	print(elem, end=' ')


(n, m) = map(int, input().split())
ans = 100005
for _ in range(m):
	(l, r) = map(int, input().split())
	ans = min(ans, r - l + 1)
print(ans)
pos = 0
for i in range(n):
	print(pos, end=' ')
	pos += 1
	if pos == ans:
		pos = 0


(n, m) = map(int, input().split())
minlen = n
for i in range(m):
	(a, b) = map(int, input().split())
	minlen = min(minlen, b - a + 1)
print(minlen)
ans = [i for i in range(minlen)] * (n // minlen) + [i for i in range(minlen)][0:n % minlen]
print(*ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
mex = []
for i in range(m):
	mex.append(list(map(int, input().split())))
ans = min([j - i + 1 for (i, j) in mex])
print(ans)
lis = []
for i in range(n):
	lis.append(str(i % ans))
print(' '.join(lis))


from operator import itemgetter
(n, m) = map(int, input().split())
ans = 10 ** 9
for i in range(m):
	(l, r) = map(int, input().split())
	ans = min(ans, r - l + 1)
print(ans)
for i in range(n):
	print(i % ans, end=' ')


import sys
(n, m) = list(map(int, input().split()))
le = 2 ** 30
for i in range(m):
	(l, r) = list(map(int, input().split()))
	le = min(r - l + 1, le)
a = (list(range(0, le)) * ((n + le - 1) // le))[:n]
res = ' '.join(map(str, a))
print(le)
print(res)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
seg = [list(map(int, input().split())) for i in range(m)]
min_l = 10 ** 18
for (l, r) in seg:
	min_l = min(min_l, r - l + 1)
ans = [i for i in range(min_l)] * ((n + min_l - 1) // min_l)
ans = ans[:n]
print(min_l)
print(*ans)


(n, m) = map(lambda x: int(x), input().split())
ans = n
for i in range(m):
	(l, r) = map(lambda x: int(x), input().split())
	ans = min(ans, r - l + 1)
print(ans)
for i in range(n):
	print(i % ans, end=' ')


(n, m) = map(int, input().split())
mx = 1000000000
for _ in range(m):
	(l, r) = map(int, input().split())
	mx = min(mx, r - l + 1)
print(mx)
result = []
j = 0
for i in range(n):
	result.append(j)
	j += 1
	if j == mx:
		j = 0
print(' '.join(map(str, result)))


def mex(arr, n):
	mini = float('inf')
	for (l, r) in arr:
		mini = min(mini, r - l + 1)
	print(mini)
	for i in range(n):
		print(i % mini, end=' ')
	return ''
(a, b) = map(int, input().strip().split())
blanck = []
for i in range(b):
	(x, y) = map(int, input().strip().split())
	blanck.append([x, y])
print(mex(blanck, a))


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
ans = n
lists = []
for k in range(m):
	(st, en) = list(map(int, input().split()))
	ans = min(ans, en - st + 1)
print(ans)
for i in range(n):
	lists.append(str(i % ans))
print(' '.join(lists))


(n, m) = map(int, input().split())
d = []
k = n
for i in range(m):
	(l, r) = map(int, input().split())
	k = min(k, r - l + 1)
print(k)
for i in range(n):
	print(i % k, end=' ')


def main():
	(n, m) = list(map(int, input().split()))
	a = [list(map(int, input().split())) for i in range(m)]
	z = min((y - x + 1 for (x, y) in a))
	print(z)
	print(' '.join([str(i % z) for i in range(n)]))
main()


from sys import stdin
(n, m) = map(int, stdin.readline().split())
intervals = []
for _ in range(m):
	interval = list(map(lambda x: int(x) - 1, stdin.readline().split()))
	interval[1] += 1
	intervals.append(interval)
s = []
for (l, r) in intervals:
	s.append(r - l)
sort = sorted(s)
result = sort[0]
a = [-1] * n
for i in range(n):
	a[i] = (i + 1) % result
print(result)
print(' '.join((str(x) for x in a)))


(n, m) = [int(i) for i in input().split()]
data = []
ans = 9999999
for i in range(m):
	data.append([int(i) for i in input().split()])
	ans = min(ans, abs(data[i][1] - data[i][0]) + 1)
data.sort(key=lambda x: x[1] - x[0])
print(ans)
gg = [-1] * n
index = 0
for i in range(n):
	gg[i] = index
	index += 1
	index %= ans
print(' '.join([str(i) for i in gg]))


I = lambda : map(int, input().split())
(n, m) = I()
(l, r) = I()
min_length = r - l + 1
for _ in range(m - 1):
	(l, r) = I()
	min_length = min(r - l + 1, min_length)
print(min_length)
print(' '.join(([str(x) for x in range(min_length)] * (n // min_length + 1))[:n]))


(n, m) = (int(x) for x in input().split())
mindif = n
for i in range(m):
	(a, b) = (int(x) for x in input().split())
	if mindif > b - a:
		mindif = b - a
print(mindif + 1)
print(' '.join([str(x % (mindif + 1)) for x in range(n)]))


(n, m) = map(int, input().split())
mn = 10 ** 10
for i in range(m):
	(b, e) = map(int, input().split())
	if e - b < mn:
		mn = e - b + 1
print(mn)
for i in range(n):
	print(i % mn, end=' ')


(n, m) = map(int, input().split())
ar = []
ln = 10000000000000
for i in range(m):
	(a, b) = map(int, input().split())
	ar.append([a, b])
	ln = min(ln, b - a + 1)
print(ln)
for i in range(n):
	print(i % ln, end=' ')


(n, m) = map(int, input().split())
k = n + 179
for i in range(m):
	(l, r) = map(int, input().split())
	k = min(k, r - l + 1)
a = [i % k for i in range(n)]
print(k)
print(' '.join(map(str, a)))


[n, m] = [int(x) for x in input().split(' ')]
mex = n + 1
for i in range(m):
	[l, r] = [int(x) for x in input().split(' ')]
	if r - l + 1 < mex:
		mex = r - l + 1
res = [''] * n
i = 0
for j in range(n):
	res[j] = str(i)
	i += 1
	if i == mex:
		i = 0
print(mex)
print(' '.join(res))


(n, m) = list(map(int, input().split()))
a = []
for i in range(m):
	b = list(map(int, input().split()))
	a.append(b[1] - b[0] + 1)
c = min(a)
b = [0] * n
for i in range(n):
	b[i] = i % c
print(c)
print(*b)


def main():
	(n, m) = input().split()
	maxminmex = int(n)
	for item in range(int(m)):
		(li, ri) = input().split()
		maxminmex = min(maxminmex, int(ri) - int(li) + 1)
	print(maxminmex)
	for i in range(int(n)):
		print(i % maxminmex)

def __starting_point():
	main()
__starting_point()


(n, m) = [int(x) for x in input().split()]
l = []
dis = []
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	s = b - a + 1
	l.append([s, a, b])
	dis.append(b - a + 1)
ans = min(dis)
print(min(dis))
l.sort()
a = l[0][1]
b = l[0][2]
li = [0] * n
for i in range(0, ans):
	li[a + i - 1] = str(i)
num = ans
if a != 1:
	for i in range(a - 2, -1, -1):
		if num > 0:
			li[i] = str(num - 1)
			num -= 1
		else:
			num = ans
			li[i] = str(num - 1)
num = -1
if b != n:
	for i in range(b, n):
		if num < ans - 1:
			li[i] = str(num + 1)
			num += 1
		else:
			num = 0
			li[i] = str(num)
print(' '.join(li))


(n, m) = map(int, input().split())
(ans, l, r) = ([0] * n, 0, float('inf'))
for i in range(m):
	(l1, r1) = map(int, input().split())
	if r1 - l1 < r - l:
		(l, r) = (l1, r1)
l -= 1
r -= 1
c = 0
for i in range(l, r + 1):
	ans[i] = c
	c += 1
for i in range(l - 1, -1, -1):
	if ans[i + 1]:
		ans[i] = ans[i + 1] - 1
	else:
		ans[i] = r - l
for i in range(r + 1, n):
	if ans[i - 1] < r - l:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = 0
print(r - l + 1)
print(*ans)


(n, k) = map(int, input().split())
t = n
for i in range(k):
	(l, r) = map(int, input().split())
	l = r - l + 1
	if l < t:
		t = l
print(t)
print(' '.join([str(i % t) for i in range(n)]))


(n, m) = map(int, input().split())
min_val = 9999999
for _ in range(m):
	(y, x) = map(int, input().split())
	if min_val > x - y:
		x1 = x
		y1 = y
		min_val = x - y
print(min_val + 1)
L = [0] * n
tp = 0
listNum = []
for i in range(n):
	listNum.append(tp)
	tp += 1
	if tp > min_val:
		tp = 0
for i in listNum[:-1]:
	print(i, end=' ')
print(listNum[-1])


def main():
	(n, m) = map(int, input().split())
	k = 1000000000.0
	for i in range(m):
		(l, r) = map(int, input().split())
		k = min(k, r - l + 1)
	print(k)
	p = (n + k - 1) // k
	a = [i for i in range(k)] * p
	print(*a[:n])
	return
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
MOD = 1000000007

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m) = value()
mex = inf
(ans_l, ans_r) = (0, 0)
for i in range(m):
	(l, r) = value()
	l -= 1
	r -= 1
	if r - l + 1 < mex:
		ans_l = l
		ans_r = r
		mex = r - l + 1
c = 0
a = [0] * n
for i in range(ans_l, n):
	a[i] = c
	c = (c + 1) % mex
c = mex - 1
for i in range(ans_l - 1, -1, -1):
	a[i] = c
	c = (c - 1 + mex) % mex
print(mex)
print(*a)


(n, m) = [int(x) for x in input().split()]
p = 999999999999999999999
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	p = min(p, b - a + 1)
print(p)
for i in range(n):
	print(i % p, end=' ')


from sys import stdin
test = stdin.readlines()
(n, m) = map(int, test[0].split())
min_len = n
for i in range(1, m + 1):
	(l, r) = map(int, test[i].split())
	min_len = min(min_len, r - l + 1)
ans = list(range(min_len)) * (n // min_len + 1)
ans = ans[:n]
print(min_len)
print(*ans)


from math import *
from collections import *
from random import *
from decimal import Decimal
from heapq import *
from bisect import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def inp():
	return int(input())

def st():
	return input().rstrip('\n')
d = 100000000000
(n, m) = ma()
for i in range(m):
	(x, y) = ma()
	d = min(d, y - x)
r = [i for i in range(d + 1)]
i = 0
print(d + 1)
while i < n:
	print(r[i % (d + 1)], end=' ')
	i += 1


x = 1000000
(n, m) = [int(x) for x in input().split()]
while m:
	(a, b) = [int(x) for x in input().split()]
	x = min(x, b - a + 1)
	m -= 1
print(x)
mylist = list(map(lambda y: y % x, range(n)))
for _ in mylist:
	print(_, end=' ')


import os, io
from sys import stdout
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
(n, m) = list(map(int, input().split()))
minRange = 1000000.0
for _ in range(m):
	(l, r) = list(map(int, input().split()))
	minRange = min(minRange, r - l + 1)
print(minRange)
print(' '.join([str(e % minRange) for e in range(n)]))


(n, m) = map(int, input().split())
v = min((int(r) - int(l) + 1 for i in m * '_' for (l, r) in [input().split()]))
print(v, *(list(range(v)) * (n // v + 1))[:n])


(n, m) = map(int, input().split())
ans = min([y - x + 1 for (x, y) in [list(map(int, input().split())) for _ in range(m)]])
print(ans)
num = list(map(str, range(ans))) * (n // ans + 1)
print(' '.join(num[:n]))


import sys
(n, m) = map(int, input().split())
mex = n
for line in sys.stdin:
	(l, r) = map(int, line.split())
	mex = min(mex, r - l + 1)
A = [i % mex for i in range(n)]
print(mex)
print(' '.join(map(str, A)))


(n, m) = map(int, input().split())
r = [list(map(int, input().split())) for j in range(m)]
v = min((ri[1] - ri[0] + 1 for ri in r))
print(v, ' '.join((str(i % v) for i in range(n))), sep='\n')


(n, m) = list(map(int, input().split()))
minimum = 10000000000
for i in range(m):
	(a, b) = list(map(int, input().split()))
	if b - a + 1 < minimum:
		minimum = b - a + 1
now = 0
line = []
for i in range(n):
	line += [now]
	now += 1
	if now >= minimum:
		now = 0
print(minimum)
print(' '.join(map(str, line)))


from itertools import cycle, islice
(n, m) = [int(x) for x in input().split()]
res = min([int(b) - int(a) + 1 for (a, b) in [input().split() for _ in range(m)]])
print(res)
print(' '.join(islice(cycle([str(x) for x in range(res)]), n)))


(n, m) = [int(i) for i in input().split()]
ans = 100000000
for i in range(m):
	(k, l) = [int(i) for i in input().split()]
	ans = min(ans, l - k + 1)
print(ans)
print(' '.join([str(i % ans) for i in range(n)]))


(n, m) = map(int, input().split())
aa = []
for i in range(m):
	(l, r) = map(int, input().split())
	aa.append([l, r])
mm = min((aa[i][1] - aa[i][0] for i in range(m)))
print(mm + 1)
ans = [0] * n
for i in range(n):
	ans[i] = i % (mm + 1)
print(*ans)


from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
l1 = 0
r1 = 0
t = 10 ** 7
s = []
for i in range(m):
	(l, r) = map(int, stdin.readline().strip().split())
	s.append([l, r])
s.sort()
for i in range(m):
	(l, r) = s[i]
	if r - l < t:
		l1 = l
		r1 = r
		t = r - l
ans = [0 for i in range(n)]
x = 0
n1 = r1 - l1 + 1
for i in range(0, n):
	ans[i % n] = x % n1
	x += 1
print(r1 - l1 + 1)
print(*ans)


(n, m) = map(int, input().split())
ans = 1000000000
for i in range(1, m + 1):
	(x, y) = map(int, input().split())
	ans = min(ans, y - x + 1)
print(str(ans) + '\n' + ' '.join(map(str, [x % ans for x in range(0, n)])))


import sys
input = sys.stdin.readline
(length, subs) = list(map(int, input().strip().split()))
lol = 9999999999999999999999999999
for i in range(subs):
	(start, end) = list(map(int, input().strip().split()))
	if abs(start - end) + 1 < lol:
		lol = abs(start - end) + 1
print(lol)
construct = []
count = 0
while count < length:
	construct.append(str(count % lol))
	count += 1
print(' '.join(construct))


import sys
input = sys.stdin.readline
nm = input().strip().split()
m = int(nm[1])
n = int(nm[0])
lengths = []
for i in range(m):
	subs = input().strip().split()
	a = int(subs[0])
	b = int(subs[1])
	lengths.append(abs(a - b) + 1)
lmex = min(lengths)
print(lmex)
for i in range(n):
	print(i % lmex, end='')
	print(' ', end='')


(n, m) = map(int, input().split())
Len = float('inf')
for i in range(m):
	(l, r) = map(int, input().split())
	Len = min(Len, r - l + 1)
ans = []
for i in range(n):
	ans.append(i % Len)
print(Len)
print(*ans)


[n, m] = map(int, input().split())
ans = 1000000000.0
for i in range(m):
	[l, r] = map(int, input().split())
	ans = min(ans, r - l + 1)
print(ans)
for i in range(n):
	print(i % ans, end=' ')
print()


(n, m) = map(int, input().split())
mm = 10 ** 5 + 1
for i in range(m):
	(l, r) = map(int, input().split())
	mm = min(mm, r - l)
print(mm + 1)
for i in range(n):
	if i != n - 1:
		print(i % (mm + 1), end=' ')
	else:
		print(i % (mm + 1))


(n, m) = map(int, input().split())
minlen = 900000001
for i in range(m):
	(t1, t2) = map(int, input().split())
	minlen = min(t2 - t1 + 1, minlen)
print(minlen)
print(*[i for i in list(range(minlen)) * (n // minlen) + list(range(n % minlen))])


(n, m) = map(int, input().split())
s = [0] * m
k = [0] * m
t = 100000
for i in range(m):
	s[i] = list(map(int, input().split()))
	k[i] = s[i][1] - s[i][0]
	if k[i] < t:
		t = k[i]
print(t + 1)
ans = [0] * n
k = n - (t + 1) * (n // (t + 1))
c = n // (t + 1)
for i in range(0, c * (t + 1), t + 1):
	for j in range(t + 1):
		ans[j + i] = j
for i in range(n // (t + 1) * (t + 1), n // (t + 1) * (t + 1) + k):
	ans[i] = i % (t + 1)
s = ' '.join(list(map(str, ans)))
print(s)


(n, m) = map(int, input().split())
mn = 100000000
for _ in range(m):
	(x, y) = map(int, input().split())
	mn = min(mn, y - x + 1)
print(mn)
for i in range(n):
	print(i % mn, end=' ')


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
a = list()
for i in range(m):
	(l, r) = map(int, input().split())
	a.append((r - l + 1, l - 1, r - 1))
a.sort()
l = a[0][0]
b = [0] * n
j = 0
for i in range(n):
	b[i] = j
	j += 1
	j %= l
print(l)
print(*b)


(n, m) = list(map(int, input().split()))
ret = 1000000001
for i in range(0, m):
	(u, v) = [int(i) for i in input().split()]
	ret = min(ret, v - u + 1)
print(ret)
for i in range(0, n):
	print(i % ret, end=' ')


(n, m) = map(int, input().split())
ml = n
for _ in range(m):
	(l, r) = map(int, input().split())
	ml = min(ml, r - l + 1)
(ans, cur) = ([0] * n, 0)
for i in range(n):
	ans[i] = cur % ml
	cur += 1
print(ml)
print(*ans)


import math

def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	(n, m) = read_ints()
	min_len = math.inf
	for _ in range(m):
		(a, b) = read_ints()
		min_len = min(min_len, b - a + 1)
	print(min_len)
	print(' '.join((str(i % min_len) for i in range(n))))
solve()


from itertools import cycle, islice
(n, m) = [int(x) for x in input().split()]
dlzky = []
for _ in range(m):
	(a, b) = input().split()
	c = int(b) - int(a) + 1
	dlzky.append(c)
minimum = min(dlzky)
cisla = [str(x) for x in range(minimum)]
vysledok = islice(cycle(cisla), n)
print(minimum)
print(' '.join(vysledok))


(n, m) = map(int, input().split())
s = 10 ** 9
L = []
a = []
for i in range(m):
	(l, r) = map(int, input().split())
	if abs(r - l) + 1 < s:
		s = abs(r - l) + 1
	L.append([l, r])
print(s)
while len(a) < n:
	for j in range(s):
		a.append(str(j))
		if len(a) == n:
			break
for i in a:
	print(i, end=' ')


r = lambda : list(map(int, input().split()))
(n, m) = r()
d = lambda x: x[1] - x[0] + 1
l = min((d(r()) for _ in range(m)))
print(l)
print(' '.join((str(i % l) for i in range(n))))


import sys
from math import *
readints = lambda : map(int, input().strip('\n').split())
(n, m) = readints()
smallest = float('inf')
for _ in range(m):
	(l, r) = readints()
	smallest = min(smallest, r - l + 1)
ans = [0] * n
for i in range(n):
	ans[i] = i % smallest
print(smallest)
print(' '.join(list(map(lambda i: str(i), ans))))


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	(ans1, array) = ans
	sys.stdout.write(str(ans1) + '\n')
	for ele in array:
		sys.stdout.write(str(ele) + ' ')
	sys.stdout.write('\n')

def solve(n, sets):
	array = [0 for _ in range(n)]
	sets.sort()
	sets.sort(key=lambda x: x[1] - x[0], reverse=True)
	prev = (0, 0)
	ans1 = sets[-1][1] - sets[-1][0] + 1
	for i in range(len(array)):
		array[i] = i % ans1
	return (ans1, array)

def readinput():
	(n, m) = getInts()
	sets = []
	for _ in range(m):
		(li, ri) = getInts()
		sets.append((li, ri))
	printOutput(solve(n, sets))
readinput()


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, m) = (int(i) for i in input().split())
d = {}
k = n + 1
for i in range(m):
	(a, b) = (int(i) for i in input().split())
	k = min(k, b - a + 1)
l = []
for i in range(n):
	l.append(i % k)
print(k)
print(*l)


data = list(map(int, input().split()))
(n, m) = (data[0], data[1])
a = []
for i in range(m):
	tmp = list(map(int, input().split()))
	a.append(tmp)
min_len = 10 ** 6
min_idx = 0
for i in range(len(a)):
	if a[i][1] - a[i][0] + 1 < min_len:
		min_len = a[i][1] - a[i][0] + 1
		min_idx = i
print(min_len)
cnt = 0
for i in range(n):
	print(cnt % min_len, end=' ')
	cnt += 1


(n, m) = map(int, input().split())
A = [-1 for i in range(n)]
f = 0
e = 999999999999999
for i in range(m):
	(a, b) = map(int, input().split())
	e = min(b - a + 1, e)
print(e)
for i in range(n):
	A[i] = f
	f += 1
	if f == e:
		f = 0
print(*A)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
(n, m) = Ri()
minn = INF
for i in range(m):
	(l, r) = Ri()
	minn = min(minn, r - l + 1)
ans = [0] * n
for i in range(n):
	ans[i] = i % minn
print(minn)
print(*ans)


(n, m) = map(int, input().split())
A = [0] * m
for j in range(m):
	A[j] = list(map(int, input().split()))
mins = float('infinity')
for j in range(m):
	mins = min(mins, A[j][1] - A[j][0] + 1)
print(mins)
ans = [0] * mins
for j in range(mins):
	ans[j] = j
print(' '.join(map(str, n // mins * ans + ans[:n % mins])))


(n, m) = [int(i) for i in input().split()]
c = n
for i in range(m):
	(a, b) = [int(i) for i in input().split()]
	c = min(b - a + 1, c)
print(c)
for i in range(n):
	print(i % c, end=' ')


(n, m) = map(int, input().split())
k = 100000
seg = []
for i in range(m):
	(l, r) = map(int, input().split())
	k = min(k, r - l + 1)
a = [i % k for i in range(n)]
print(k)
for i in range(len(a)):
	print(a[i], end=' ' if i != len(a) - 1 else '\n')


(n, m) = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(m)]
min_len = n
for (l, r) in arr:
	min_len = min(min_len, r - l + 1)
print(min_len)
print(' '.join(map(str, [i % min_len for i in range(n)])))


class CodeforcesTask739ASolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.ms = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.ms.append([int(x) for x in input().split(' ')])

	def process_task(self):
		lens = [x[1] - x[0] + 1 for x in self.ms]
		target = min(lens)
		result = []
		current = 0
		for x in range(self.n_m[0]):
			result.append(current)
			current += 1
			if current == target:
				current = 0
		self.result = '{0}\n{1}'.format(target, ' '.join([str(x) for x in result]))

	def get_result(self):
		return self.result
Solution = CodeforcesTask739ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, m) = map(int, input().split())
ans = n + 1
for i in range(m):
	(a, b) = map(int, input().split())
	ans = min(ans, b - a + 1)
print(ans)
arr = [0] * n
put = 0
for i in range(n):
	arr[i] = put
	put += 1
	if put == ans:
		put = 0
print(*arr)


import sys
lines = sys.stdin.readlines()
(n, m) = map(int, lines[0].strip().split(' '))
minQLen = n
for i in range(1, m + 1):
	(l, r) = map(int, lines[i].strip().split(' '))
	minQLen = min(minQLen, r - l + 1)
print(minQLen)
arr = [i % minQLen for i in range(n)]
print(' '.join(map(str, arr)))


(n, m) = map(int, input().split())
mexi = 1000000000.0
for i in range(m):
	(r, l) = map(int, input().split())
	mexi = min(mexi, l - r + 1)
print(mexi)
d = [str(j % mexi) for j in range(n)]
print(' '.join(d))


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f

def eprint(*args):
	print(*args, file=sys.stderr)
pl = 1
from math import *
import copy
if pl:
	input = sys.stdin.readline

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
d = []
from bisect import *

def siv(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	prev = 0
	for p in range(2, n + 1):
		if prime[p]:
			d.append(p)
from itertools import permutations
from bisect import *
(n, m) = mi()
d = []
for i in range(m):
	(l, r) = mi()
	d.append([r - l + 1, l - 1, r - 1])
a = [-1 for i in range(n)]
d.sort()
for i in range(n):
	a[i] = (a[i - 1] + 1) % d[0][0]
print(d[0][0])
print(*a)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = 10 ** 18
for _ in range(m):
	(l, r) = map(int, input().split())
	a = min(a, r - l + 1)
print(a)
ans = [-1] * n
for i in range(n):
	ans[i] = i % a
print(*ans)


f = lambda : list(map(int, input().split()))
(n, m) = f()
lr = lambda x: x[1] - x[0] + 1
sq = min((lr(f()) for _ in range(m)))
print(sq)
x = ' '.join([str(i % sq) for i in range(n)])
print(x)


(n, m) = map(int, input().split())
segments = []
for i in range(m):
	(x, y) = map(int, input().split())
	segments.append((y - x, (x, y)))
m_seg = min(segments)
print(m_seg[0] + 1)
lst = [0] * n
k = 0
for i in range(n):
	lst[i] = str(k)
	k = (k + 1) % (m_seg[0] + 1)
print(' '.join(lst))


(n, m) = (int(i) for i in input().split())
maxd = 10 ** 10
l = -1
r = -1
for i in range(m):
	(a, b) = (int(i) for i in input().split())
	if b - a < maxd:
		l = a - 1
		r = b - 1
		maxd = r - l
ans_l = [0] * n
for i in range(l, r + 1):
	ans_l[i] = i - l
k = maxd
t = -1
for i in range(l - 1, -1, -1):
	if t < 0:
		t = k
	ans_l[i] = t
	t -= 1
t = 0
for i in range(r + 1, n):
	if t > maxd:
		t = 0
	ans_l[i] = t
	t += 1
print(maxd + 1)
print(' '.join(list(map(str, ans_l))))


def main():
	(n, m) = map(int, input().split())
	res = []
	for _ in range(m):
		(lo, hi) = map(int, input().split())
		res.append(hi - lo)
	mi = min(res) + 1
	aa = list(range(mi)) * ((n + mi - 1) // mi)
	print(mi)
	print(' '.join(map(str, aa[:n])))
main()


(n, m) = map(int, input().split())
mini = 1000000000000000
for i in range(m):
	(l, r) = map(int, input().split())
	mini = min(mini, r - l + 1)
print(mini)
for i in range(n):
	print(i % mini, end=' ')


(n, m) = list(map(int, input().split()))
mini = float('inf')
for i in range(m):
	(a, b) = list(map(int, input().split()))
	mini = min(mini, b - a + 1)
a = []
for i in range(n):
	a.append(i % mini)
print(mini)
print(*a)


(n, m) = map(int, input().split())
ans = n
for i in range(m):
	(a, b) = map(int, input().split())
	ans = min(ans, b - a + 1)
print(ans)
q = [i for i in range(ans)]
w = []
while len(w) < n:
	w += q
print(*w[:n])


(n, m) = map(int, input().split())
ans = 10 ** 10
for i in range(m):
	(li, ri) = map(int, input().split())
	ans = min(ri - li + 1, ans)
print(ans)
for i in range(n):
	print(i % ans, end=' ')


(n, m) = list(map(int, input().split()))
inter = []
mini = 1000000000
for i in range(m):
	(l, r) = list(map(int, input().split()))
	inter.append([l, r])
	diff = r - l + 1
	if diff < mini:
		mini = diff
print(mini)
res = [i % mini for i in range(n)]
print(' '.join(map(str, res)))


import math, sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda : int(input())
li = lambda : list(map(int, input().split()))

def case():
	(n, k) = li()
	a = []
	for i in range(k):
		a.append(li())
	m = n
	(p, q) = (-1, -1)
	for i in range(k):
		if m >= a[i][1] - a[i][0]:
			(p, q) = (a[i][0], a[i][1])
			m = a[i][1] - a[i][0]
	ans = [0] * n
	c = 0
	for i in range(n):
		ans[i] = i % (q - p + 1)
	print(q - p + 1)
	print(*ans)
for _ in range(1):
	case()


(n, m) = map(int, input().split())
store = 10000000
ans = []
for i in range(m):
	(l, r) = map(int, input().split())
	store = min(store, r - l + 1)
for i in range(n):
	ans.append(i % store)
print(store)
print(*ans)


def get_line(func=int, sym=' '):
	return [func(i) for i in input().split(sym)]
(n, m) = get_line()
ans = 1 << 1000
for i in range(m):
	(l, r) = get_line()
	ans = min(ans, r - l + 1)
print(ans)
k = 0
data = ''
for i in range(n):
	data += '%d%s' % (k, ' ' if i < n - 1 else '')
	k = (k + 1) % ans
print(data)


(amount, mass) = map(int, input().split())
minim = amount
for i in range(mass):
	(l, r) = map(int, input().split())
	if minim > r - l + 1:
		minim = r - l + 1
i = 0
print(minim)
while i < amount:
	print(i % minim, end=' ')
	i += 1


(n, m) = map(int, input().split())
w = min((int(r) - int(l) + 1 for _ in 'a' * m for (l, r) in [input().split()]))
print(w, *(list(range(w)) * (n // w + 1))[:n])


(n, m) = map(int, input().split())
mn = n
for _ in range(m):
	(l, r) = map(int, input().split())
	mn = min(mn, r - l + 1)
print(mn)
print(*[i % mn for i in range(n)])


(n, m) = list(map(int, input().split()))
mi = 10 ** 10
for i in range(m):
	(l, r) = list(map(int, input().split()))
	mi = min(r - l + 1, mi)
print(mi)
for i in range(n):
	print(i % mi, end=' ')


(n, cuts) = (int(x) for x in input().split())
shortest = n
for i in range(cuts):
	(l, r) = (int(x) for x in input().split())
	shortest = min(shortest, r - l + 1)
ans = [i % shortest for i in range(n)]
print(shortest)
print(*ans)


s = input().split()
n = int(s[0])
m = int(s[1])
mn = 100000000
for i in range(m):
	str = input().split()
	if int(str[1]) - int(str[0]) < mn:
		mn = int(str[1]) - int(str[0])
print(mn + 1)
for i in range(n):
	print(i % (mn + 1), end=' ')


import sys

class Pair:

	def __init__(self, l, r):
		self.l = l
		self.r = r
		self.diff = r - l

	def __lt__(self, other):
		return self.diff < other.diff

	def __str__(self):
		return str(self.diff)

	def __repr__(self):
		return '[{x}]'.format(x=self.diff)
(n, m) = [int(x) for x in input().strip().split()]
a = [0] * (n + 1)
INF = sys.maxsize
mex = INF
indices = []
for i in range(m):
	(l, r) = [int(x) for x in input().strip().split()]
	indices.append(Pair(l, r))
indices.sort()
assert len(indices) > 0
min_length = indices[0].diff + 1
for i in range(1, n + 1):
	a[i] = i % min_length
print(min_length)
print(' '.join((str(a[i]) for i in range(1, n + 1))))


cases = input().split()
n = int(cases[0])
m = int(cases[1])
least_mex = 1000000
for i in range(m):
	inputs = input().split()
	start = int(inputs[0])
	end = int(inputs[1])
	value = end - start + 1
	if value < least_mex:
		least_mex = value
print(least_mex)
for j in range(n):
	print(str(j % least_mex), end=' ')


(n, m) = map(int, input().split())
mex = 1000000000.0
for i in range(m):
	(l, r) = map(int, input().split())
	mex = min(mex, r - l + 1)
print(mex)
out = ''
for i in range(n):
	out += str(i % mex) + ' '
print(out)


(n, m) = map(int, input().split())
ip = []
ans = []
k = n + 1
for i in range(m):
	(a, b) = map(int, input().split())
	if b - a < k:
		k = b - a
print(k + 1)
i = 0
k += 1
for j in range(n):
	ans.append(i % k)
	i += 1
for i in ans:
	print(i, end=' ')


from math import *
from sys import *
from queue import *
from decimal import *
(n, m) = (int(z) for z in input().split())
e = n
for i in range(m):
	(j, k) = (int(z) for z in input().split())
	e = min(e, k - j + 1)
res = []
for i in range(n):
	res.append(i % e)
print(e)
print(' '.join(map(str, res)))


nm = [int(n) for n in input().split()]
n = nm[0]
m = nm[1]
ans = n + 1
for i in range(m):
	ab = [int(n) for n in input().split()]
	a = ab[0]
	b = ab[1]
	ans = min(ans, b - a + 1)
print(ans)
for i in range(n):
	print(i % ans, end=' ')


(n, m) = map(int, input().split())
a = [0] * n
p = [0] * m
ans = 10 ** 6
for i in range(m):
	(l, r) = map(int, input().split())
	ans = min(ans, r - l + 1)
k = 0
for i in range(n):
	a[i] = k
	k = (k + 1) % ans
print(ans)
print(' '.join(map(str, a)))


from sys import stdin
from sys import stdout
(n, m) = [int(x) for x in stdin.readline().split()]
ans = -1
for _ in range(m):
	(t, p) = tuple((int(x) for x in stdin.readline().split()))
	if ans == -1 or ans > p - t + 1:
		ans = p - t + 1
stdout.write(str(ans) + '\n')
a = [str(i % ans) for i in range(n)]
stdout.write(' '.join(a))