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.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.awt.Point;

public class Newbie {

    static InputReader sc = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        solver s = new solver();
        long t = 1;
        while (t > 0) {
            s.sol();
            t--;
        }
        out.close();
    }
           /* static class descend implements Comparator<pair1> {
                public int compare(pair1 o1, pair1 o2) {
                    if (o1.pop != o2.pop)
                        return (int) (o1.pop - o2.pop);
                    else
                        return o1.in - o2.in;
                }
            }*/

    static class InputReader {
        public BufferedReader br;
        public StringTokenizer token;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
            token = null;
        }

        public String sn() {
            while (token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return token.nextToken();
        }

        public int ni() {
            return Integer.parseInt(sn());
        }

        public String snl() throws IOException {
            return br.readLine();
        }

        public long nlo() {
            return Long.parseLong(sn());
        }

        public double nd() {
            return Double.parseDouble(sn());
        }

        public int[] na(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = sc.ni();
            return a;
        }

        public long[] nal(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = sc.nlo();
            return a;
        }
    }

    static class ascend implements Comparator<pair> {
        public int compare(pair o1, pair o2) {
            return o2.b - o1.b;
        }
    }

    static class extra {

        static boolean v[] = new boolean[100001];
        static List<Integer> l = new ArrayList<>();
        static int t;

        static void shuffle(int a[]) {
            for (int i = 0; i < a.length; i++) {
                int t = (int) Math.random() * a.length;
                int x = a[t];
                a[t] = a[i];
                a[i] = x;
            }
        }

        static void shufflel(long a[]) {
            for (int i = 0; i < a.length; i++) {
                int t = (int) Math.random() * a.length;
                long x = a[t];
                a[t] = a[i];
                a[i] = x;
            }
        }

        static int gcd(int a, int b) {
            if (b == 0)
                return a;
            else
                return gcd(b, a % b);
        }

        static boolean valid(int i, int j, int r, int c) {
            if (i >= 0 && i < r && j >= 0 && j < c) {
                // System.out.println(i+" /// "+j);
                return true;
            } else {
                //  System.out.println(i+" //f "+j);
                return false;
            }
        }

        static void seive() {
            for (int i = 2; i < 101; i++) {
                if (!v[i]) {
                    t++;
                    l.add(i);
                    for (int j = 2 * i; j < 101; j += i)
                        v[j] = true;
                }
            }
        }

        static int binary(LinkedList<Integer> a, long val, int n) {
            int mid = 0, l = 0, r = n - 1, ans = 0;
            while (l <= r) {
                mid = (l + r) >> 1;
                if (a.get(mid) == val) {
                    r = mid - 1;
                    ans = mid;
                } else if (a.get(mid) > val)
                    r = mid - 1;
                else {
                    l = mid + 1;
                    ans = l;
                }
            }
            return (ans + 1);
        }

        static long fastexpo(long x, long y) {
            long res = 1;
            while (y > 0) {
                if ((y & 1) == 1) {
                    res *= x;
                }
                y = y >> 1;
                x = x * x;
            }
            return res;
        }

        static long lfastexpo(long x, long y, long p) {
            long res = 1;
            x = x % p;
            while (y > 0) {
                if ((y & 1) == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }

               /* void dijsktra(int s, List<pair> l[], int n) {
                    PriorityQueue<pair> pq = new PriorityQueue<>(new ascend());
                    int dist[] = new int[100005];
                    boolean v[] = new boolean[100005];
                    for (int i = 1; i <= n; i++)
                        dist[i] = 1000000000;
                    dist[s] = 0;
                    for (int i = 1; i < n; i++) {
                        if (i == s)
                            pq.add(new pair(s, 0));
                        else
                            pq.add(new pair(i, 1000000000));
                    }
                    while (!pq.isEmpty()) {
                        pair node = pq.remove();
                        v[node.a] = true;
                        for (int i = 0; i < l[node.a].size(); i++) {
                            int v1 = l[node.a].get(i).a;
                            int w = l[node.a].get(i).b;
                            if (v[v1])
                                continue;
                            if ((dist[node.a] + w) < dist[v1]) {
                                dist[v1] = dist[node.a] + w;
                                pq.add(new pair(v1, dist[v1]));
                            }
                        }
                    }
                }*/
    }

    static class pair {
        int a;
        int b;

        public pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    static class pair1 {
        pair p;
        int in;

        public pair1(pair a, int n) {
            this.p = a;
            this.in = n;
        }
    }

    static int inf = 5000013;

    static class solver {
        DecimalFormat df = new DecimalFormat("0.00000000");
        extra e = new extra();
        long mod = (long) (1000000007);

        void sol() throws IOException {
            int n = sc.ni();
            int m = sc.ni();
            long ans[] = new long[n];
            long mex = Long.MAX_VALUE;
            for (int i = 0; i < m; i++) {
                int l = sc.ni() - 1;
                int r = sc.ni() - 1;
                mex = Math.min(mex, r - l + 1);
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < mex && i < n; j++) {
                    ans[i++] = j;
                }
                if (i != n)
                    i -= 1;
            }
            out.println(mex);
            for (int i = 0; i < n; i++)
                out.print(ans[i] + " ");
            out.println();
        }
    }
}
