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: interview

Starter code:

Solutions:
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 = [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)


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 = list(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 = list(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

    # print(max_div2)
    # print(min_div1)

    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 = list(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:
            #print(i,a1,a2)
            if i >= a2 and i <= b:
                r += 1
    if a1 == -1:
        r -= 1
    if a2 == -1:
        r -= 1
    print(r)
else:
    print(0)


read = lambda: list(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=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)




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()

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 = 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)

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)

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
        else:
            if (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))

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())
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())
#a = [1]*n
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(j-i+1)
print(max(j-i+1,0))

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 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
		#if a < div1Min:
		#	div1Min 

main()
# L = [(1, 4), (5, 2)]
# print(solver(5, L))

# L2 = [(1, 2), (2, 3), (1, 3)]
# print(solver(3, L2))

# L3 = [(3, 1), (3, 2)]
# print(solver(3, L3))

#print(solver(2, [(1, 2)]))
# used = [False, True, True, True]
# a = [b for b in used if b == True]
# print(a)
#print(max({1, 2, 3}))


# coding: utf-8





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)



'''
Created on May 8, 2016

@author: Md. Rezwanul Haque
'''
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)) 
            

def __starting_point():
    main()
__starting_point()

#coding:utf-8
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 = list(map(int, input().split()))

A, B = 1, n

for _ in range(m):
    u, v = list(map(int, input().split()))
    if u > v:
        u, v = v, u
    A = max(A, u)
    B = min(B, v)

print(max(B-A, 0))

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)

n,m=list(map(int,input().split()))
div1=[]
div2=[]
i=0
ans=-5
while i<m:
    a,b=list(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 = list(map(int, input().split()))
div1 = {}
div2 = {}
tot = n
ans = False
p = -1 #max div2
q = 100000000000 #min div1
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)
    else:
        if 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)