There are n problems prepared for the next Codeforces round. They are arranged in ascending order by their difficulty, and no two problems have the same difficulty. Moreover, there are m pairs of similar problems. Authors want to split problems between two division according to the following rules: 

  * Problemset of each division should be non-empty. 
  * Each problem should be used in exactly one division (yes, it is unusual requirement). 
  * Each problem used in division 1 should be harder than any problem used in division 2. 
  * If two problems are similar, they should be used in different divisions. 



Your goal is count the number of ways to split problem between two divisions and satisfy all the rules. Two ways to split problems are considered to be different if there is at least one problem that belongs to division 1 in one of them and to division 2 in the other.

Note, that the relation of similarity is not transitive. That is, if problem i is similar to problem j and problem j is similar to problem k, it doesn't follow that i is similar to k.

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) — the number of problems prepared for the round and the number of pairs of similar problems, respectively.

Each of the following m lines contains a pair of similar problems ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi). It's guaranteed, that no pair of problems meets twice in the input.

Output

Print one integer — the number of ways to split problems in two divisions.

Examples

Input

5 2
1 4
5 2


Output

2


Input

3 3
1 2
2 3
1 3


Output

0


Input

3 2
3 1
3 2


Output

1

Note

In the first sample, problems 1 and 2 should be used in division 2, while problems 4 and 5 in division 1. Problem 3 may be used either in division 1 or in division 2.

In the second sample, all pairs of problems are similar and there is no way to split problem between two divisions without breaking any rules.

Third sample reminds you that the similarity relation is not transitive. Problem 3 is similar to both 1 and 2, but 1 is not similar to 2, so they may be used together.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.security.interfaces.DSAKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class a {

	public static class in {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		static void init(InputStream input) throws FileNotFoundException {
			// reader = new BufferedReader(new FileReader("B-large.in"));
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(reader.readLine());
			return tokenizer.nextToken();
		}

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

		static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}

	public static long comp(int n, int r) {
		r = Math.min(r, n - r);
		long ans = 1;
		for (int i = 1; i <= r; i++) {
			ans = ans * (long) (n - r + i) / (long) i;
		}
		return ans;

	}

	public static class node {

		int a;
		int b;
		int pos;

		node(int a, int b, int pos) {
			this.a = a;
			this.b = b;
			this.pos = pos;

		}

	}

	public static long gcd(int x, int y) {
		if (y == 0)
			return x;
		return gcd(y, x % y);
	}

	public static int tree[];

	public static void add(int idx, long val, int n) {

		while (idx <= n) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}

	public static int get(int idx) {
		int g = 0;
		while (idx > 0) {

			g += tree[idx];
			idx -= (idx & -idx);
		}

		return g;
	}

	public static class point implements Comparable<point> {
		int min;
		int a;
		int b;

		point(int min, int a, int b) {
			this.min = min;
			this.a = a;
			this.b = b;
		}

		@Override
		public int compareTo(point o) {
			if (o.min > min)
				return 1;
			else if (o.min < min)
				return -1;
			return 0;
		}
	}

	public static HashMap<Integer, Integer> dp[];
	public static int n;
	public static String a[];
	public static String b[];

	public static int solve(int mask_taken, int mask_real) {

		if (mask_taken == (1 << n) - 1)
			return 0;

		if (dp[mask_taken].containsKey(mask_real))
			return dp[mask_taken].get(mask_real);
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			if ((1 << i & mask_taken) != 0)
				continue;
			boolean ok1 = false;
			boolean ok2 = false;
			for (int j = 0; j < n; j++) {
				if ((1 << j & mask_real) != 0) {
					if (a[i].equals(a[j]))
						ok1 = true;
					if (b[i].equals(b[j]))
						ok2 = true;
				}
			}

			if (ok1 && ok2) {
				max = Math
						.max(max, solve(mask_taken | (1 << i), mask_real) + 1);
			} else
				max = Math.max(max,
						solve(mask_taken | (1 << i), mask_real | (1 << i)));
		}

		dp[mask_taken].put(mask_real, max);
		return max;

	}

	public static int LCS(String a, String b) {
		int max = 0;
		int dp[][] = new int[a.length() + 1][b.length() + 1];
		for (int i = 1; i <= a.length(); i++) {
			for (int j = 1; j <= b.length(); j++) {
				if (a.charAt(i - 1) == b.charAt(j - 1))
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

				max = Math.max(max, dp[i][j]);
			}
		}

		return max;
	}

	// for bad input
	static String ReadLn(int maxLg) {
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;
		String line = "";

		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null);
		return (new String(lin, 0, lg));
	}

	public static int[] replaceValues(int arr[]) {
		int i, j, len = arr.length;
		if (len % 2 == 0) {
			for (i = 0; i <= len; i++)
				arr[i] = 0;
		} else {
			for (j = 0; j <= len; j++)
				arr[j] = 1;
		}
		return arr;
	}

	public static boolean vis[];
	public static ArrayList<Integer> arr[];
	public static int div[];
	public static boolean ok = true;
	public static int max;
	public static int min;

	public static void dfs(int node, int d) {

		vis[node] = true;
		if (arr[node].size() == 0)
			return;
		if (!ok)
			return;
		div[node] = d;
		if (d == 1) {
			min = Math.min(min, node);

		} else
			max = Math.max(max, node);

		for (int i = 0; i < arr[node].size(); i++) {
			int ne = arr[node].get(i);
			if (div[ne] == d) {
				ok = false;
				return;
			}
			if (vis[ne])
				continue;
			if (d == 1)
				dfs(ne, 2);
			else
				dfs(ne, 1);
		}
	}

	public static void main(String[] args) throws IOException {
		// StringBuilder qq = new StringBuilder();
		in.init(System.in);
		// PrintWriter out = new PrintWriter("output.txt");
		PrintWriter out = new PrintWriter(System.out);

		// source code
		// String hostNamee = "http://";
		// System.out.println(hostNamee.length());
		int n = in.nextInt();
		int m = in.nextInt();

		int div[] = new int[n];
		boolean ok = true;
		int min1 = n - 1;
		int max2 = 0;
		div[0] = 2;
		div[n - 1] = 1;
		for (int i = 0; i < m; i++) {
			int one = in.nextInt() - 1;
			int two = in.nextInt() - 1;
			if (div[Math.min(one, two)] == 1) {
				ok = false;
			} else if (div[Math.max(one, two)] == 2)
				ok = false;
			div[Math.min(one, two)] = 2;
			div[Math.max(one, two)] = 1;
			min1 = Math.min(min1, Math.max(one, two));
			max2 = Math.max(max2, Math.min(one, two));
		}

		if (!ok||max2>=min1) {
			System.out.println(0);
			return;
		}
		int ans = 1;
		for (int i = 0; i < n; i++) {
			if (div[i] == 0) {
				if (i <= max2 || i >= min1)
					continue;
				else {
					ans++;

				}
			}
		}
		System.out.println(ans);

		out.close();

	}
}
