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 li and ri, and its elements are a[li], a[li + 1], ..., a[ri].

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 ≤ 105).

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

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 109.

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

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.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.*;

public class experiment
{

    static int M = 1_000_000_007;
    static int INF = 2_000_000_000;
    static final FastScanner fs = new FastScanner();

    //variable

    public static void main(String[] args) throws IOException {


            int n = fs.nextInt();
            int q = fs.nextInt();
            int minl = INF,mini = -1;
            for(int i=0;i<q;i++) {
                int l = fs.nextInt();
                int r = fs.nextInt();
                if(minl > r-l+1) {
                    minl = r-l+1;
                    mini = l;
                }
            }
            int[] ans = new int[n];
            System.out.println(minl);
            int fact = 0;
            for(int i=mini-1;i<n;i++) {
                if (fact == minl) fact = 0;
                ans[i] = fact;
                fact++;
            }
            fact = minl-1;
            for(int i=mini-2;i>=0;i--) {
                if(fact<0) fact = minl-1;
                ans[i] = fact;
                fact--;

            }
            for(int i:ans) System.out.print(i+" ");
            System.out.println();
    }
    //function

    static int lcm(int x,int y) {
        return (x / gcd(x,y) * y);
    }

    static int gcd(int x, int y) {
        if(x == 0) return y;

        return gcd(y%x,x);
    }
    static void premutation(int n, ArrayList<Integer> arr,boolean[] chosen) {
        if(arr.size() == n) {

        }else {
            for(int i=1; i<=n; i++) {
                if(chosen[i]) continue;
                arr.add(i);
                chosen[i] = true;
                premutation(n,arr,chosen);
                arr.remove(new Integer(i));
                chosen[i] = false;
            }
        }
    }
    static boolean isPalindrome(char[] c) {
        int n = c.length;
        for(int i=0; i<n/2; i++) {
            if(c[i] != c[n-i-1]) return false;
        }
        return true;
    }
    // Template
    static long nCk(int n, int k) {
        return (modMult(fact(n),fastexp(modMult(fact(n-k),fact(k)),M-2)));
    }

    static long fact (long n) {

        long fact =1;
        for(int i=1; i<=n; i++) {
            fact = modMult(fact,i);
        }
        return fact%M;
    }

    static int modMult(long a,long b) {
        return (int) (a*b%M);
    }

    static long fastexp(long x, int y){
        if(y==1) return x;

        long ans = fastexp(x,y/2);
        if(y%2 == 0) return modMult(ans,ans);

        return modMult(ans,modMult(ans,x));
    }

    static final Random random = new Random();

    static void ruffleSort(int arr[])
    {
        int n = arr.length;
        for(int i=0; i<n; i++)
        {
            int j = random.nextInt(n),temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr);
    }


    public static class Pairs implements Comparable<Pairs>
    {
        int value,index;
        Pairs(int value, int index) {
            this.value = value;
            this.index = index;
        }
        public int compareTo(Pairs p) {
            return Integer.compare(this.value,p.value);
        }
    }
}
class FastScanner
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str = new StringTokenizer("");

    String next() throws IOException
    {
        while(!str.hasMoreTokens())
            str = new StringTokenizer(br.readLine());

        return str.nextToken();
    }

    char nextChar() throws IOException {
        return next().charAt(0);
    }

    int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }

    float nextfloat() throws IOException
    {
        return Float.parseFloat(next());
    }

    double nextDouble() throws IOException
    {
        return Double.parseDouble(next());
    }
    long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }
    byte nextByte() throws IOException
    {
        return Byte.parseByte(next());
    }
    int [] arrayIn(int n) throws IOException
    {
        int  arr[] = new int[n];
        for(int i=0; i<n; i++)
        {
            arr[i] = nextInt();
        }
        return arr;
    }
}
