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: competition

Starter code:

Solutions:
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(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())
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)

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()


I = lambda: list(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 = 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())

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())
d = n
for i in range(m):
    l, r = map(int, input().split())
    d = min(d, r - l + 1)
print(d)
for i in range(n):
    print(i % d, 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)


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=" ")



[n, m] = map(int, input().split())
ans = 1e9
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())
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')

import sys

n, m = list(map(int, input().split()))
mex = n
for i in range(m):
    l, r = list(map(int, input().split()))
    mex = min(mex, r-l+1)

A = [i%mex for i in range(n)]
print(mex)
print(' '.join(map(str, A)))


import sys

n, m = list(map(int, input().split()))
mex = n
for line in sys.stdin:
    l, r = list(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)))


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 = [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= ' ')

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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()

import sys
input = sys.stdin.readline
#
n,m = list(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))


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))


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))


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))


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))