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.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main {
	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskA {
		int[] dx = { 1, 0, -1, 0, -1, -1, 1, 1 }, 
			  dy = { 0, 1, 0, -1, -1, 1 - 1, 1 };
		int MAX = (int) (1e5+10);

		// GCD && LCM
		long gcd(long a, long b) {
			return b == 0 ? a : gcd(b, a % b);
		}

		long lcm(long a, long b) {
			return a * (b / gcd(a, b));
		}

		// REverse a String
		String rev(String s) {
			return new StringBuilder(s).reverse().toString();
		}
		
		/*^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ SOLUTION IS RIGHT HERE^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/

		public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
			int n = in.nextInt(),m = in.nextInt();
			int[] l = new int[m] , r = new int[m];
			//pair[] pair = new pair[m];
			int min = Integer.MAX_VALUE;
			for(int i = 0; i < m; i++){
				l[i] = in.nextInt();
				r[i] = in.nextInt();
				//pair[i] = new pair(l[i],r[i]);
				if(r[i]-l[i]< min)
					min = r[i]-l[i];
			}
			out.println(min+1);
			//int[] res = new int[n];
			/*sort(pair);
			fill(res,-1);
			for(int i = 0; i < m; i++){
				//out.println(pair[i].first+" "+pair[i].second+" qq");
				if(min == pair[i].second-pair[i].first){
					//out.println(min+" "+l[i]+" "+r[i]);
				for(int j = pair[i].first-1,k=0; j < pair[i].second; j++){
					if(res[j] == -1){
						//out.println((j+1)+" b");
						res[j] = k++;
					}else if(k == res[j])
						k++;
				}
				}
			}
			for(int i = 0; i < m; i++){
				//if(min == r[i]-l[i])
				for(int j = pair[i].first-1,k=0; j < pair[i].second; j++){
					//out.println(l[i]+" "+r[i]);
					if(res[j] == -1){
						res[j] = k++;
					}
				}
			}*/
			for(int i = 0,k=0; i < n; i++){
				if(k > min)
					k = 0;
				out.print(k+" ");
				k++;
			}
		}
	}

	// pair class
	static class pair implements Comparable<pair> {
		int first, second;

		public pair() {
			this.first = 0;
			this.second = 0;
		}

		public pair(int f, int s) {
			this.first = f;
			this.second = s;
		}

		@Override
		public int compareTo(pair one) {
			if (this.first < one.first)
				return -1;
			if (this.first > one.first)
				return 1;
			return 0;
		}

	}

	/*^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^`````````````````````````^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/
	static class InputReader {
		private byte[] buf = new byte[8000];
		private int index;
		private int total;
		private InputStream in;
		// BufferedReader br = new BufferedReader(new
		// InputStreamReader(System.in));

		public InputReader(InputStream stream) {
			in = stream;
		}

		public int scan() {
			if (total == -1)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				try {
					total = in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public long scanlong() {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		private int scanInt() {
			int integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scandouble() {
			double doubll = 0;
			int n = scan();
			int neg = 1;
			while (isWhiteSpace(n))
				n = scan();
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doubll *= 10;
					doubll += n - '0';
					n = scan();
				}
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doubll += (n - '0') * temp;
						n = scan();
					}
				}
			}
			return neg * doubll;
		}

		private float scanfloat() {
			float doubll = 0;
			int n = scan();
			int neg = 1;
			while (isWhiteSpace(n))
				n = scan();
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doubll *= 10;
					doubll += n - '0';
					n = scan();
				}
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doubll += (n - '0') * temp;
						n = scan();
					}
				}
			}
			return neg * doubll;
		}

		public String scanstring() {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		public String scan_nextLine() {
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(n);
				n = scan();
			} while (!isEndOfLine(n));
			return res.toString();
		}

		public boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
		/// Input module

		public int nextInt() {
			return scanInt();
		}

		public long nextLong() {
			return scanlong();
		}

		public double nextDouble() {
			return scandouble();
		}

		public float nextFloat() {
			return scanfloat();
		}

		public String next() {
			return scanstring();
		}

		public String nextLine() throws IOException {
			return scan_nextLine();
		}

		public int[] readintArray(int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++) {
				array[i] = nextInt();
			}
			return array;
		}

		public Integer[] readIntegerArray(int size) {
			Integer[] array = new Integer[size];
			for (int i = 0; i < size; i++) {
				array[i] = nextInt();
			}
			return array;
		}
	}

}