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 u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}). 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.

Difficulty: EASY
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
div1 = []
div2 = []
i = 0
ans = -5
while i < m:
	(a, b) = map(int, input().split())
	div1.append(max(a, b))
	div2.append(min(a, b))
	i += 1
if m == 0:
	print(n - 1)
else:
	ans = min(div1) - max(div2)
	if ans <= 0:
		print(0)
	else:
		print(ans)


(n, m) = input().split(' ')
n = int(n)
m = int(m)
av = []
bv = []
for i in range(m):
	t = input()
	(a, b) = t.split(' ')
	a = int(a)
	b = int(b)
	if a > b:
		(a, b) = (b, a)
	av.append(a)
	bv.append(b)
if m == 0:
	print(n - 1)
	return
res = min(bv) - max(av)
if res <= 0:
	res = 0
print(res)


inpt = [int(i) for i in input().split(' ')]
a = inpt[0]
b = 1
i = 0
while i < inpt[1]:
	ln = [int(j) for j in input().split(' ')]
	ln = sorted(ln)
	if a > ln[1]:
		a = ln[1]
	if b < ln[0]:
		b = ln[0]
	i += 1
if a - b >= 0:
	print(a - b)
else:
	print(0)


def main():
	(n, m) = (int(x) for x in input().split())
	L = [None] * m
	for i in range(m):
		(x, y) = (int(x) for x in input().split())
		L[i] = (x, y)
	print(solver(n, L))

def solver(n, L):
	used = [False] * (n + 1)
	div1 = set()
	div2 = set()
	for (x, y) in L:
		a = max(x, y)
		b = min(x, y)
		if a in div2 or b in div1:
			return 0
		div1.add(a)
		div2.add(b)
		used[a] = True
		used[b] = True
	if len(div1) == 0:
		div1Min = n + 1
	else:
		div1Min = min(div1)
	if len(div2) == 0:
		div2Max = 0
	else:
		div2Max = max(div2)
	if div2Max > div1Min:
		return 0
	else:
		count = 0
		for i in range(div2Max + 1, div1Min):
			if used[i] == False:
				count += 1
		if len(div1) == 0 and len(div2) == 0:
			return count - 1
		elif len(div1) == 0 or len(div2) == 0:
			return count
		else:
			return count + 1
main()


(a, b) = map(int, input().split())
(l, r) = (1, a)
for _ in ' ' * b:
	(u, v) = sorted(map(int, input().split()))
	l = max(l, u)
	r = min(r, v)
print(max(r - l, 0))


(n, m) = map(int, input().split())
a = list((0 for i in range(n)))
e = 0
if m == 0:
	print(n - 1)
	return
for i in range(m):
	(q, w) = map(int, input().split())
	if a[min(q, w) - 1] == 0:
		a[min(q, w) - 1] = 1
	if a[min(q, w) - 1] == 2:
		e = 1
		break
	if a[max(q, w) - 1] == 0:
		a[max(q, w) - 1] = 2
	if a[max(q, w) - 1] == 1:
		e = 1
		break
c = r = t = 0
if e == 1:
	print(0)
else:
	for i in range(n):
		if a[i] == 1:
			r = i
	for i in range(n):
		if a[i] == 2:
			t = i
			break
	print(t - r if t > r else 0)


(n, m) = map(int, input().split())
(div_o, div_t) = (set(), set())
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	if v > u:
		div_o.add(v)
		div_t.add(u)
	else:
		div_o.add(u)
		div_t.add(v)
if len(div_o) == 0:
	print(n - 1)
else:
	print(max(0, min(div_o) - max(div_t)))


from sys import *
(n, m) = (int(z) for z in stdin.readline().split())
minofmax = n
maxofmin = 1
for i in range(m):
	(u, v) = (int(z) for z in stdin.readline().split())
	if u > v:
		(u, v) = (v, u)
	maxofmin = max(u, maxofmin)
	minofmax = min(v, minofmax)
if maxofmin > minofmax:
	stdout.write('0\n')
else:
	stdout.write(str(minofmax - maxofmin) + '\n')


(n, m) = list(map(int, input().split()))
left = 0
right = n
for i in range(m):
	(ui, vi) = list(map(int, input().split()))
	if ui > vi:
		left = max(left, vi)
		right = min(right, ui)
	else:
		left = max(left, ui)
		right = min(right, vi)
if m == 0:
	right -= 1
if right > left:
	print(right - left)
else:
	print(0)


(n, m) = [int(i) for i in input().split()]
s1 = [1]
s2 = [n]
for i in range(m):
	(a, b) = [int(i) for i in input().split()]
	s1.append(min(a, b))
	s2.append(max(a, b))
s1.sort()
s2.sort()
if s1[-1] < s2[0]:
	print(s2[0] - s1[-1])
else:
	print(0)


def start():
	a = input().split()
	n = int(a[0])
	p = int(a[1])
	small1 = n
	large2 = 0
	arr = []
	for i in range(0, n):
		arr.append(0)
	pairs = []
	for i in range(0, p):
		pairs.append(input().split())
	if n < 2:
		print('0')
	for i in range(0, p):
		s = pairs[i]
		a1 = int(s[0])
		a2 = int(s[1])
		if a1 > a2:
			if arr[a1 - 1] == 2:
				print('0')
				return
			else:
				arr[a1 - 1] = 1
				if small1 > a1:
					small1 = a1
			if arr[a2 - 1] == 1:
				print('0')
				return
			else:
				arr[a2 - 1] = 2
				if large2 < a2:
					large2 = a2
		else:
			if arr[a1 - 1] == 1:
				print('0')
				return
			else:
				arr[a1 - 1] = 2
				if large2 < a1:
					large2 = a1
			if arr[a2 - 1] == 2:
				print('0')
				return
			else:
				arr[a2 - 1] = 1
				if small1 > a2:
					small1 = a2
	if small1 <= large2:
		print('0')
		return
	w = 1
	for i in range(0, n):
		if arr[i] == 0:
			if small1 > i + 1:
				if large2 < i + 1:
					w += 1
	if p == 0:
		w -= 1
	print(str(w))
	return
start()


(n, m) = map(int, input().split())
(i, j) = (2, n)
for k in range(m):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	(i, j) = (max(i, x + 1), min(j, y))
print(max(j - i + 1, 0))


def main():
	(n, m) = [int(i) for i in input().strip().split()]
	u = []
	v = []
	for i in range(m):
		(a, b) = [int(i) for i in input().strip().split()]
		u.append(min(a, b))
		v.append(max(a, b))
	max_min = max(u + [1])
	min_max = min(v + [n])
	if max_min >= min_max:
		print(0)
		return
	print(min_max - max_min)
main()


(n, m) = map(int, input().split())
uv = []
for i in range(m):
	mapp = list(map(int, input().split()))
	mapp.sort()
	uv.append(mapp)
all_tasks = [1, n]
for s in uv:
	all_tasks = [max(all_tasks[0], s[0]), min(all_tasks[1], s[1])]
if all_tasks[1] - all_tasks[0] + 1 < 2:
	print(0)
else:
	print(all_tasks[1] - all_tasks[0])


(n, m) = map(int, input().split())

def getResult(n, m):
	listForDiv1 = []
	listForDiv2 = []
	sumList = []
	for i in range(m):
		(a, b) = map(int, input().split())
		if a < b:
			listForDiv1.append(a)
			listForDiv2.append(b)
		if a > b:
			listForDiv1.append(b)
			listForDiv2.append(a)
	if len(listForDiv1) > 0:
		if max(listForDiv1) >= min(listForDiv2):
			return 0
	result = 1
	if len(listForDiv1) > 0:
		mn = min(listForDiv2)
		mx = max(listForDiv1)
	ostList = []
	for i in range(n):
		if len(listForDiv1) > 0:
			if mn > i and i > mx:
				ostList.append(i)
		else:
			ostList.append(i)
	if len(ostList) == 0:
		return result
	elif len(listForDiv1) == 0:
		return len(ostList) - 1
	else:
		return len(ostList) + 1
print(getResult(n, m))


(n, m) = map(int, input().split())
if m == 0:
	print(n - 1)
else:
	div1 = set()
	min_div1 = 100001
	div2 = set()
	max_div2 = -1
	ans = 1
	for i in range(m):
		(a, b) = map(int, input().split())
		(x, y) = (max(a, b), min(a, b))
		if ans:
			if x < max_div2 or y > min_div1:
				ans = 0
			if x in div2 or y in div1:
				ans = 0
			div1.add(x)
			if x < min_div1:
				min_div1 = x
			div2.add(y)
			if y > max_div2:
				max_div2 = y
	if ans:
		for i in range(1, n + 1):
			if i not in div1 and i not in div2:
				if i > max_div2 and i < min_div1:
					ans += 1
	print(ans)


(n, m) = map(int, input().split())
s1 = set()
s2 = set()
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	if a in s2 or b in s1:
		print(0)
		exit(0)
	s1.add(a)
	s2.add(b)
if not s2:
	s2.add(n)
	s1.add(1)
print(max(0, min(s2) - max(s1)))


(n, m) = map(int, input().split())
lb = 1
ub = n
for _ in range(m):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	lb = max(lb, a)
	ub = min(ub, b)
print(max(0, ub - lb))


(n, m) = map(int, input().split())
A = 1
B = n
for i in range(m):
	(u, v) = map(int, input().split())
	if u > v:
		(u, v) = (v, u)
	A = max(u, A)
	B = min(v, B)
print(max(0, B - A))


(n, m) = map(int, input().split())
x = 10000000
y = 0
if m != 0:
	for i in range(m):
		(a, b) = map(int, input().split())
		c = min(a, b)
		d = max(a, b)
		if c > y:
			y = c
		if d < x:
			x = d
	if x - y < 0:
		print(0)
	else:
		print(x - y)
else:
	print(n - 1)


(total, similar) = (int(_) for _ in input().split())
first = set()
second = set()
for _ in range(similar):
	(x, y) = (int(_) for _ in input().split())
	first.add(max(x, y))
	second.add(min(x, y))
if first & second:
	print(0)
else:
	if not first:
		first = {total}
	if not second:
		second = {1}
	print(max(min(first) - max(second), 0))


(n, m) = map(int, input().split())
a = set()
b = set()
u = set([i for i in range(1, n + 1)])
f = False
for _ in range(m):
	(x, y) = map(int, input().split())
	if x in u:
		u.remove(x)
	if y in u:
		u.remove(y)
	if x < y:
		if x in b or y in a:
			f = True
		a.add(x)
		b.add(y)
	else:
		if x in a or y in b:
			f = True
		a.add(y)
		b.add(x)
if m == 0:
	print(n - 1)
elif f or min(b) < max(a):
	print(0)
else:
	print(min(b) - max(a))


from collections import deque

def bfs(i, G, V):
	V[i] = 1
	Q = deque([i])
	while Q:
		u = Q.popleft()
		for v in G[u]:
			if not V[v]:
				V[v] = 1 if V[u] == 2 else 2
				Q.append(v)
			elif V[v] == V[u]:
				return False
	return True
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
I = []
possible = True
for i in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
	I.append(u)
	I.append(v)
I.sort()
V = [0 for _ in range(n + 1)]
for i in I:
	if not V[i]:
		possible = bfs(i, G, V)
		if not possible:
			print(0)
			break
if possible:
	(m1, m2) = (1, n)
	for i in range(1, n + 1):
		if V[i] == 1:
			m1 = i
		elif V[i] == 2 and m2 == n:
			m2 = i
	if m2 < m1:
		print(0)
	else:
		print(m2 - m1)


(n, m) = map(int, input().split())
div1 = []
div2 = []
if m == 0:
	print(n - 1)
else:
	for _ in range(m):
		(a, b) = map(int, input().split())
		div1.append(max(a, b))
		div2.append(min(a, b))
	print(max(0, min(div1) - max(div2)))


nm = input().split()
n = int(nm[0])
m = int(nm[1])
if m == 0:
	print(n - 1)
else:
	i = 0
	d1 = []
	d2 = []
	while i < m:
		uv = input().split()
		u = int(uv[0])
		v = int(uv[1])
		d1.append(max(u, v))
		d2.append(min(u, v))
		i += 1
	x = min(d1)
	y = max(d2)
	if x <= y:
		print(0)
	else:
		print(x - y)


def main():
	(n, m) = map(int, input().split())
	(lo, hi) = (1, n)
	for _ in range(m):
		(u, v) = map(int, input().split())
		if u > v:
			if lo < v:
				lo = v
			if hi > u:
				hi = u
		elif v > u:
			if lo < u:
				lo = u
			if hi > v:
				hi = v
	print(max(hi - lo, 0))
main()


(n, m) = map(int, input().split())
count = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	(low, high) = (min(a, b) - 1, max(a, b) - 1)
	count[low] += 1
	count[high] -= 1
(cur, res) = (0, 0)
for i in range(n - 1):
	cur += count[i]
	if cur == m:
		res += 1
print(res)


(n, m) = map(int, input().split())
l = 1
r = n - 1
for i in range(m):
	(x, y) = map(int, input().split())
	if x > y:
		tmp = x
		x = y
		y = tmp
	r = min(r, y - 1)
	l = max(l, x)
print(max(0, r - l + 1))


(n, m) = map(int, input().split())
lst = [0] * (n + 1)
cnt = 0
first = []
second = []
llst = []
if m == 0:
	print(n - 1)
	exit(0)
for i in range(m):
	(a, b) = map(int, input().split())
	first.append(min(a, b))
	second.append(max(a, b))
	lst[a] = 1
	lst[b] = 1
if len(set(first).intersection(set(second))):
	print(0)
else:
	mx = max(first)
	mn = min(second)
	print(max(0, mn - mx))


import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect

def array2d(d1, d2, init=None):
	return [[init for _ in range(d1)] for _ in range(d2)]
(n, m) = list(map(int, input().split(' ')))
div1 = [n]
div2 = [1]
for i in range(m):
	(u, v) = list(map(int, input().split(' ')))
	if u > v:
		(u, v) = (v, u)
	div1.append(v)
	div2.append(u)
min_div1 = min(div1)
max_div2 = max(div2)
if min_div1 < max_div2:
	print(0)
else:
	print(min_div1 - max_div2)


(n, m) = map(int, input().split())
(f, s) = ([], [])
if m == 0:
	print(n - 1)
	exit(0)
for i in range(m):
	(a, b) = map(int, input().split())
	f.append(min(a, b))
	s.append(max(a, b))
if len(set(f).intersection(set(s))):
	print(0)
else:
	print(max(0, min(s) - max(f)))


import math
import sys
from collections import Counter

def solve():
	(n, m) = [int(x) for x in input().split()]
	(L, R) = (1, n)
	for line in sys.stdin:
		(x, y) = [int(x) for x in line.split()]
		(x, y) = (min(x, y), max(x, y))
		(L, R) = (max(L, x), min(R, y))
	return max(R - L, 0)
print(solve())


(n, m) = map(int, input().split())
l = [[0 for col in range(2)] for row in range(m + 1)]
maxx = 1
minn = n
for i in range(0, m):
	(l[i][0], l[i][1]) = map(int, input().split())
	if l[i][0] > l[i][1]:
		(l[i][0], l[i][1]) = (l[i][1], l[i][0])
	maxx = max(l[i][0], maxx)
	minn = min(l[i][1], minn)
if minn < maxx:
	print(0)
else:
	print(minn - maxx)


(n, m) = list(map(int, input().split()))
div1 = {}
div2 = {}
tot = n
ans = False
p = -1
q = 100000000000
for i in range(m):
	(a, b) = list(map(int, input().split()))
	if b > a:
		if a in div1:
			ans = True
		else:
			div1[b] = 1
			div2[a] = 1
			p = max(a, p)
			q = min(b, q)
	elif a in div2:
		ans = True
	else:
		div1[a] = 1
		div2[b] = 1
		p = max(b, p)
		q = min(a, q)
if ans:
	print(0)
else:
	tot = q - p - 1
	if tot < 0:
		print(0)
	elif tot == 0:
		print(1)
	elif len(div1) == 0 and len(div2) == 0:
		print(n - 1)
	else:
		print(tot + 1)


(n, m) = map(int, input().split())
left = 2
right = n
for i in range(m):
	(a, b) = map(int, input().split())
	c = min(a, b) + 1
	d = max(a, b)
	left = max(left, c)
	right = min(right, d)
print(right - left + 1 if left <= right else 0)


def readInts():
	return map(int, input().split())
(n, m) = readInts()
lo = 1
hi = n
for _ in range(m):
	(a, b) = readInts()
	lo = max(lo, min(a, b))
	hi = min(hi, max(a, b))
print(max(0, hi - lo))


(a, b) = map(int, input().split())
(l, r) = (0, a)
ans = 1
z = [0] * (a + 1)
for _ in ' ' * b:
	(u, v) = sorted(map(int, input().split()))
	if z[u] == 2 or z[v] == 1:
		ans = 0
	elif z[u] != 0 and z[v] != 0 and (z[u] == z[v]):
		ans = 0
	else:
		z[u] = 1
		z[v] = 2
		if u >= r:
			ans = 0
		if v <= l:
			ans = 0
		l = max(l, u)
		r = min(r, v)
if ans == 0:
	print(ans)
elif l == 0 and r == a:
	print(a - 1)
else:
	print(r - l)


read = lambda : map(int, input().split())
(n, m) = read()
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(m):
	(u, v) = read()
	if u > v:
		(u, v) = (v, u)
	a[u] = b[v] = 1
(L, R) = (1, n)
for i in range(1, n + 1):
	if b[i] == 1:
		R = i
		break
for i in range(n, 0, -1):
	if a[i] == 1:
		L = i
		break
ans = max(0, R - L)
print(ans)


(n, m) = map(int, input().split())
a = [0] * (n + 1)
c = [0] * 4
d = [0] * 4
ans = 0
for i in range(m):
	(x, y) = sorted(map(int, input().split()))
	a[x] |= 1
	a[y] |= 2
for x in a:
	c[x] += 1
if c[3] == 0:
	for i in range(1, n):
		if a[i] > 1:
			break
		d[a[i]] += 1
		c[a[i]] -= 1
		if c[1] > 0:
			continue
		ans += 1
print(ans)


f = lambda : map(int, input().split())
(n, m) = f()
(a, b) = (1, n)
for i in range(m):
	(u, v) = sorted(f())
	a = max(a, u)
	b = min(b, v)
print(max(0, b - a))


def compute():
	(n, m) = [int(s) for s in input().split()]
	p = {}
	for i in range(m):
		(u, v) = [int(s) for s in input().split()]
		if u > v:
			if p.get(u) == 2:
				return 0
			if p.get(v) == 1:
				return 0
			p[u] = 1
			p[v] = 2
		else:
			if p.get(v) == 2:
				return 0
			if p.get(u) == 1:
				return 0
			p[v] = 1
			p[u] = 2
	(div1, div2) = ([], [])
	for (k, v) in list(p.items()):
		if v == 1:
			div1.append(k)
		else:
			div2.append(k)
	p_left = [i for i in range(1, n + 1) if i not in p]
	if not div1:
		if p_left:
			div1.append(p_left[-1])
			p_left.remove(p_left[-1])
		else:
			return 0
	if not div2:
		if p_left:
			div2.append(p_left[0])
			p_left.remove(p_left[0])
		else:
			return 0
	div1_easiest = min(div1)
	div2_hardest = max(div2)
	if div2_hardest > div1_easiest:
		return 0
	res = 1
	for i in range(len(p_left)):
		if p_left[i] > div1_easiest:
			pass
		elif p_left[i] < div2_hardest:
			pass
		else:
			res += 1
	return res
res = compute()
print(res)


(n, m) = map(int, input().split())
a = set()
b = set()
for _ in range(m):
	(x, y) = map(int, input().split())
	if x < y:
		a.add(x)
		b.add(y)
	else:
		a.add(y)
		b.add(x)
if m == 0:
	print(n - 1)
else:
	print(max(0, min(b) - max(a)))


def main():
	(n, m) = list(map(int, input().split()))
	(lo, hi) = (1, n)
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		if u > v:
			if lo < v:
				lo = v
			if hi > u:
				hi = u
		else:
			if lo < u:
				lo = u
			if hi > v:
				hi = v
	print(max(hi - lo, 0))

def __starting_point():
	main()
__starting_point()


def solve(data, n, m):
	i = 1
	j = n
	flags1 = [False] * (n + 1)
	flags2 = [False] * (n + 1)
	for x in data:
		if flags1[x[0]] and flags1[x[1]]:
			return 0
		elif flags2[x[0]] and flags2[x[1]]:
			return 0
		elif x[0] > x[1]:
			flags1[x[0]] = True
			flags2[x[1]] = True
		else:
			flags2[x[0]] = True
			flags1[x[1]] = True
	while i < n + 1 and flags1[i] == False:
		i += 1
	while j > 0 and flags2[j] == False:
		j -= 1
	if j == 0:
		return n - 1
	elif i < j:
		return 0
	else:
		return i - j
numb = [int(x) for x in input().split()]
n = numb[0]
m = numb[1]
data = []
for k in range(m):
	data.append([int(x) for x in input().split()])
print(solve(data, n, m))


(n, m) = map(int, input().split())
l1 = set()
l2 = set()
for i in range(m):
	(k, t) = sorted(map(int, input().split()))
	l1.add(k)
	l2.add(t)
if m == 0:
	print(n - 1)
else:
	(q1, q2) = (l1.intersection(l2), l1.union(l2))
	if len(q1):
		print(0)
	else:
		maxl = max(l1)
		minh = min(l2)
		if maxl > minh:
			print(0)
		elif len(q2) == n:
			print(1)
		else:
			t = 0
			for i in range(1, n + 1):
				if i not in q2:
					if minh > i > maxl and i < minh:
						t += 1
			print(t + 1)


(n, m) = map(int, input().split())
l1 = set()
l2 = set()
for i in range(m):
	(k, t) = sorted(map(int, input().split()))
	l1.add(k)
	l2.add(t)
if m == 0:
	print(n - 1)
else:
	l3 = set()
	for i in l1:
		l3.add(i)
	for i in l2:
		l3.add(i)
	if len(l3) != len(l1) + len(l2):
		print(0)
	else:
		maxl = max(l1)
		minh = min(l2)
		if maxl > minh:
			print(0)
		elif len(l3) == n:
			if len(l1) != 0 and len(l2) != 0:
				print(1)
			else:
				print(0)
		elif maxl > minh:
			print(0)
		else:
			t = 0
			for i in range(1, n + 1):
				if i not in l3:
					if i < maxl:
						pass
					elif i > minh:
						pass
					else:
						t += 1
			print(t + 1)


import sys
import math
import bisect

def solve(n, A):
	m = len(A)
	left = 1
	right = n
	for i in range(m):
		A[i].sort()
		left = max(left, A[i][0])
		right = min(right, A[i][1])
	if left >= right:
		return 0
	return right - left

def main():
	(n, m) = map(int, input().split())
	A = []
	for i in range(m):
		(a, b) = map(int, input().split())
		A.append([a, b])
	ans = solve(n, A)
	print(ans)
main()


[n, m] = list(map(int, input().split()))
upper = n
lower = 1
for i in range(m):
	[u, v] = list(map(int, input().split()))
	upper = min(upper, max(u, v))
	lower = max(lower, min(u, v))
res = max(0, upper - lower)
print(res)


read = lambda : map(int, input().split())
(n, m) = read()
l = 1
r = n
for i in range(m):
	(u, v) = read()
	l = max(l, min(u, v))
	r = min(r, max(u, v))
print(r - l if l <= r else 0)


import sys
sys.stderr = sys.stdout

def division(n, m, S):
	u0 = 1
	v0 = n
	for (u, v) in S:
		if v < u:
			(u, v) = (v, u)
		u0 = max(u0, u)
		v0 = min(v0, v)
		if u0 >= v0:
			return 0
	return v0 - u0

def main():
	(n, m) = readinti()
	S = readinttl(m)
	print(division(n, m, S))

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.__stderr__)
main()


(n, m) = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(m)]
D1 = [0 for _ in range(n)]
D2 = [0 for _ in range(n)]
for i in range(m):
	s = S[i]
	a = max(s)
	b = min(s)
	D1[a - 1] += 1
	D2[b - 1] += 1
ok = 1
a1 = -1
a2 = -1
for i in range(n):
	if D1[i] and D2[i]:
		ok = 0
	if D1[i] and a1 < 0:
		a1 = i
	if D2[i]:
		a2 = i
if a1 < a2:
	ok = 0
if ok:
	r = 1
	G = []
	b = a1
	if b == -1:
		b = n + 1
	for i in range(n):
		if D1[i] == 0 and D2[i] == 0:
			if i >= a2 and i <= b:
				r += 1
	if a1 == -1:
		r -= 1
	if a2 == -1:
		r -= 1
	print(r)
else:
	print(0)


(n, m) = map(int, input().split())
L = 1
R = n
for i in range(m):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	L = max(a, L)
	R = min(b, R)
if R - L <= 0:
	print(0)
else:
	print(R - L)


(n, m) = map(int, input().split())
(l, r) = (1, n)
for _ in range(m):
	(a, b) = map(int, input().split())
	l = max(l, min(a, b))
	r = min(r, max(a, b))
print(max(0, r - l))


import sys
import math
import itertools as it
import operator as op
import fractions as fr
(n, m) = map(int, sys.stdin.readline().split())
(l, r) = (1, n - 1)
for _ in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	if a > b:
		(a, b) = (b, a)
	l = max(l, a)
	r = min(r, b - 1)
if l <= r:
	r = r - l + 1
else:
	r = 0
print(r)


(n, m) = (int(z) for z in input().split())
minofmax = n
maxofmin = 1
for i in range(m):
	(u, v) = (int(z) for z in input().split())
	if u > v:
		(u, v) = (v, u)
	maxofmin = max(u, maxofmin)
	minofmax = min(v, minofmax)
if maxofmin > minofmax:
	print(0)
else:
	print(minofmax - maxofmin)


(n, m) = map(int, input().split())
maxDiv2 = 0
minDiv1 = 100000
for i in range(0, m):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	if a > maxDiv2:
		maxDiv2 = a
	if b < minDiv1:
		minDiv1 = b
if m == 0:
	print(n - 1)
else:
	print(max(0, minDiv1 - maxDiv2))


(n, m) = map(int, input().strip().split(' '))
l = [0] * n
ma = 0
mb = 1000000
f = 0
for j in range(m):
	(a1, a2) = map(int, input().strip().split(' '))
	if a2 < a1:
		(a1, a2) = (a2, a1)
	if a1 > ma:
		ma = a1
	if a2 < mb:
		mb = a2
	if a1 >= mb or a2 <= ma:
		f = 1
		print(0)
		break
	else:
		l[a1 - 1] = 1
		l[a2 - 1] = 1
if f == 0:
	l2 = 0
	for j in range(n):
		if l[j] == 0:
			if j + 1 > ma and j + 1 < mb:
				l2 += 1
	if m == 0:
		print(l2 - 1)
	else:
		print(l2 + 1)


(n, m) = map(int, input().split())
div1 = []
div2 = []
res = 0
if m == 0:
	res = n - 1
	div1.append(1)
	div2.append(n)
for i in range(m):
	(a, b) = map(int, input().split())
	if a < b:
		div1.append(a)
		div2.append(b)
	else:
		div2.append(a)
		div1.append(b)
div1.sort()
div2.sort()
if div1[len(div1) - 1] >= div2[0]:
	res = 0
else:
	res = div2[0] - div1[len(div1) - 1]
print(res)


(n, m) = map(int, input().split())
ma = 0
mi = 10000000000000000
for _ in range(m):
	l = [int(x) for x in input().split()]
	l.sort()
	ma = max(l[0], ma)
	mi = min(l[1], mi)
if m == 0:
	print(n - 1)
else:
	print(max(0, mi - ma))