You're given an undirected graph with $n$ nodes and $m$ edges. Nodes are numbered from $1$ to $n$.

The graph is considered harmonious if and only if the following property holds:  For every triple of integers $(l, m, r)$ such that $1 \le l < m < r \le n$, if there exists a path going from node $l$ to node $r$, then there exists a path going from node $l$ to node $m$. 

In other words, in a harmonious graph, if from a node $l$ we can reach a node $r$ through edges ($l < r$), then we should able to reach nodes $(l+1), (l+2), \ldots, (r-1)$ too.

What is the minimum number of edges we need to add to make the graph harmonious? 


-----Input-----

The first line contains two integers $n$ and $m$ ($3 \le n \le 200\ 000$ and $1 \le m \le 200\ 000$).

The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), that mean that there's an edge between nodes $u$ and $v$.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).


-----Output-----

Print the minimum number of edges we have to add to the graph to make it harmonious.


-----Examples-----
Input
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12

Output
1

Input
200000 3
7 9
9 8
4 5

Output
0



-----Note-----

In the first example, the given graph is not harmonious (for instance, $1 < 6 < 7$, node $1$ can reach node $7$ through the path $1 \rightarrow 2 \rightarrow 7$, but node $1$ can't reach node $6$). However adding the edge $(2, 4)$ is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

Difficulty: interview

Starter code:

Solutions:
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

used = set()
ans = 0
mp = -1
for i in range(N):
    if i in used:
        continue
    if mp >= i:
        ans += 1
        Edge[mp].append(i)
        Edge[i].append(mp)
        mp = max(mp, i)
    else:
        st = i
    
    stack = [i]
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                mp = max(mp, vf)
                used.add(vf)
                stack.append(vf)

print(ans)

import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self.cnt -= 1
          
    def is_same(self, x, y):
        return self.root(x) == self.root(y)
             
    def get_size(self, x):
        return -self.parent[self.root(x)]
    
    def get_cnt(self):
        return self.cnt



n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
uf = UnionFind(n)

for a, b in info:
    uf.merge(a - 1, b - 1)

ans = 0
i = 0
while True:
    if i >= n:
        break
    cnt = uf.get_size(i)
    j = i
    while cnt:
        if uf.is_same(i, j):
            cnt -= 1
            j += 1
        else:
            cnt -= 1
            cnt += uf.get_size(j)
            ans += 1
            uf.merge(i, j)
            j += 1
    i = j
print(ans)

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

import sys
from operator import itemgetter
def main():
    input = sys.stdin.readline
    N, M = list(map(int, input().split()))
    # harmonious <=> l < m < r で、l から r に辿り着けるなら、l から m に辿り着ける

    uf = Uf(N+1)
    for u, v in zip(*[iter(map(int, sys.stdin.read().split()))]*2):
        uf.unite(u, v)

    L = [10**9] * (N+1)
    R = [-1] * (N+1)
    for i in range(1, N+1):
        r = uf.root(i)
        L[r] = min(L[r], i)
        R[r] = max(R[r], i)
    ans = 0
    LR = []
    for l, r in zip(L, R):
        if r != -1:
            LR.append((l, r))
    LR.sort(key=itemgetter(0))
    rr = -1
    for l, r in LR:
        if rr > l:
            ans += 1
        rr = max(rr, r)
    print(ans)


main()


def main():
    from sys import stdin, stdout
    from array import array
    n, m = list(map(int, stdin.readline().split()))
    n += 1
    g = [array('l', ()) for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, stdin.readline().split()))
        g[u].append(v)
        g[v].append(u)
    ans = 0
    new = array('i', (1,)) * n
    vr = 0
    for v1 in range(n):
        if new[v1]:
            if v1 < vr:
                ans += 1  # v1 vr
            stack = [v1]
            while stack:
                u = stack.pop()
                if new[u]:
                    new[u] = 0
                    vr = max(vr, u)
                    for v in g[u]:
                        stack.append(v)
    print(ans)


main()


import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = list(map(int, input().split()))
P = [-1 for i in range(N)]
def par(a):
    L = []
    while P[a] >= 0:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    if par(a) == par(b): return 0
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)

for _ in range(M):
    u, v = list(map(int, input().split()))
    unite(u-1, v-1)

C = [[] for _ in range(N)]
D = [0] * N
for i in range(N):
    C[par(i)].append(i)
    D[par(i)] = 1
ma = -1
ans = 0
for i in range(N):
    p = par(i)
    if D[p] == 0:
        continue
    D[p] = 0
    if min(C[p]) < ma:
        ans += 1
    ma = max(ma, max(C[p]))
print(ans)


#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

class DisjointSet:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * n
        self.max_member = [i for i in range(n)]

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def has_same_root(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        return self.size[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.max_member[y] = max(self.max_member[x], self.max_member[y])
        else:
            self.par[y] = x
            self.max_member[x] = max(self.max_member[x], self.max_member[y])
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n, m = [int(item) for item in input().split()]
DS = DisjointSet(n)
for i in range(m):
    u, v = [int(item) - 1 for item in input().split()]
    DS.unite(u, v)
goal = 0
par = 0
ans = 0
for i in range(n):
    if goal <= i:
        par = DS.par[i]
        goal = DS.max_member[par]
        continue
    if DS.has_same_root(par, i): 
        continue
    else:
        DS.unite(par, i)
        ans += 1
        par = DS.par[i]
        goal = DS.max_member[par]
print(ans)

from sys import stdin

input = stdin.readline

edge = [[] for _ in range(200005)]
n, m = map(int, input().split())

check = [0] * 200005
mx = 0

from collections import deque

def dfs(x):
    l = deque([x])
    check[x] = 1
    while len(l):
        p = l.popleft()
        nonlocal mx
        mx = max(mx,p)
        for i in edge[p]:
            if check[i]:
                continue
            l.append(i)
            check[i] = 1


for i in range(m):
    u, v = map(int, input().split())
    edge[u].append(v)
    edge[v].append(u)

r = 0
ans = 0
for i in range(1, n + 1):
    if check[i]:
        continue
    mx = 0
    dfs(i)
    if i <= r:
        ans += 1
    r = max(r, mx)

print(ans)

import sys
from collections import defaultdict

def dfs(s, compN):
    visited[s] = compN
    queue = set(adj[s])
    maxV = s
    while queue:
        v = queue.pop()
        if not visited[v]:
            visited[v] = compN
            maxV = max(maxV, v)
            queue.update(adj[v])
    return maxV
            
def countEdges(adj, n, m):
    compN = 0
    comps = []
    for s in range(1, n + 1):
        if not visited[s]:
            compN += 1
            minV = s
            maxV = dfs(s, compN)
            comps.append((minV, compN, 0))
            comps.append((maxV, compN, 1))
    
    comps.sort()
#     print(comps)
    opened = set()
    ctr = 0
    for v, compN, closed in comps:
        if closed:
            opened.remove(compN)
        else:
            if opened:
                ctr += 1
            opened.add(compN)
    return ctr


# inf = open('input.txt', 'r')
# reader = (map(int, line.split()) for line in inf)
reader = (list(map(int, s.split())) for s in sys.stdin)

n, m = next(reader)
adj = defaultdict(list)
for _ in range(m):
    i, j = next(reader)
    adj[i].append(j)
    adj[j].append(i)
visited = [False] * (n + 1)
ans = countEdges(adj, n, m)
print(ans)
    
# inf.close()


import sys
from collections import deque

class UnionFind(object):
    __slots__ = ['nodes']

    def __init__(self, n: int):
        self.nodes = [-1]*n

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y, nodes = self.find(x), self.find(y), self.nodes

        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x
            nodes[root_x] += nodes[root_y]
            nodes[root_y] = root_x

        return root_x != root_y


n, m = list(map(int, input().split()))
uf = UnionFind(n)
adj = [[] for _ in range(n)]

for u, v in (list(map(int, sys.stdin.readline().split())) for _ in range(m)):
    u = u-1
    v = v-1
    adj[u].append(v)
    adj[v].append(u)
    uf.unite(u, v)


g_range = []
visited = [0]*n

for i in range(n):
    if visited[i] or not adj[i]:
        continue

    dq = deque([i])
    visited[i] = 1

    min_v, max_v = i, i
    v_set = []
    size = 0

    while dq:
        v = dq.popleft()
        min_v = min(min_v, v)
        max_v = max(max_v, v)
        v_set.append(v)
        size += 1
        for dest in adj[v]:
            if visited[dest]:
                continue
            visited[dest] = 1
            dq.append(dest)

    g_range.append((min_v, max_v))

g_range.sort()
ans = 0
checked_max = 0

for s, t in g_range:
    if t <= checked_max:
        continue
    for v in range(max(s, checked_max)+1, t):
        if uf.unite(s, v):
            ans += 1
    checked_max = max(checked_max, t)

print(ans)


# @author 

import sys


class DHarmoniousGraph:
    def solve(self):
        from collections import defaultdict

        class Node:
            def __init__(self, val):
                self.parent = self
                self.size = 1
                self.val = val

        def union(x, y):
            xRoot, yRoot = find(x), find(y)
            if xRoot == yRoot:
                return
            if xRoot.size >= yRoot.size:
                yRoot.parent = xRoot
                xRoot.size += yRoot.size
            else:
                xRoot.parent = yRoot
                yRoot.size += xRoot.size

        def find(x):
            while x.parent != x:
                x = x.parent
            return x

        n, m = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        nodes = [Node(i) for i in range(n)]
        parent = [-1] * n
        for i in range(m):
            u, v = [int(_) for _ in input().split()]
            u -= 1
            v -= 1
            adj[u].append(v)
            adj[v].append(u)
            union(nodes[u], nodes[v])

        for i in range(n):
            parent[i] = find(nodes[i]).val

        cc = defaultdict(tuple)

        for g in parent:
            cc[g] = (float('inf'), -float('inf'))

        for i in range(n):
            g = parent[i]
            cc[g] = (min(cc[g][0], i), max(cc[g][1], i))

        ccs = [[g, cc[g][0], cc[g][1]] for g in cc]
        ccs.sort(key=lambda x:x[1])

        ans = 0
        done = {g : 0 for g in cc}
        for g, cur, r in ccs:
            if done[g]:
                continue
            # print(g, cur, r, ans)
            while cur < r:
                cur_p = find(nodes[cur])
                r_p = find(nodes[r])
                # print(cur, r, cur_p.val, r_p.val)
                if cur_p != r_p:
                    ans += 1
                    done[cur_p.val] = 1
                    new_r = max(r, cc[cur_p.val][1])
                    union(nodes[cur], nodes[r])
                    r = new_r

                cur += 1

        print(ans)

solver = DHarmoniousGraph()
input = sys.stdin.readline

solver.solve()


from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10**8)
def inpl(k=0): return [int(x)+k for x in sys.stdin.readline().split()]

visited = [False]*(200100)
lines = defaultdict(set)

def dfs(s):
    nonlocal visited
    visited[s] = True
    ret = s
    for t in lines[s]:
        if visited[t] == False:
            ret = max(dfs(t), ret)
    return ret

def main():
    nonlocal visited
    N,M = inpl()
    for _ in range(M):
        x,y = inpl(-1)
        lines[x].add(y)
        lines[y].add(x)
    maxr = 0
    ans = 0
    for l in range(N):
        if visited[l] == False:
            r = dfs(l)
            if l < maxr:
                ans += 1
            maxr = max(r,maxr)

    print(ans)


def __starting_point():
    threading.stack_size(1024 * 100000)
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

__starting_point()

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = list(map(int, input().split()))
P = [-1 for i in range(N)]
def par(a):
    L = []
    while P[a] >= 0:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    if par(a) != par(b):
        if P[par(b)] >= P[par(a)]:
            if P[par(b)] == P[par(a)]: P[par(a)] -= 1
            P[par(b)] = par(a)
        else:
            P[par(a)] = par(b)

for _ in range(M):
    u, v = list(map(int, input().split()))
    unite(u-1, v-1)

C = [[] for _ in range(N)]
D = [0] * N
for i in range(N):
    C[par(i)].append(i)
    D[par(i)] = 1
ma = -1
ans = 0
for i in range(N):
    p = par(i)
    if D[p] == 0:
        continue
    D[p] = 0
    if min(C[p]) < ma:
        ans += 1
    ma = max(ma, max(C[p]))
print(ans)


import sys
import collections
import heapq
import math
 
input = sys.stdin.readline
 
def rints(): return list(map(int, input().strip().split()))
def rstr(): return input().strip()
def rint(): return int(input().strip())
def rintas(): return [int(i) for i in input().strip().split()]
    
def gcd(a, b):       
    if (b == 0): 
         return a 
    return gcd(b, a%b) 

n, m = rints()
graphs = collections.defaultdict(list)
nums = set()
for _ in range(m):
    u, v = rints()
    graphs[u].append(v)
    graphs[v].append(u)
    nums.add(u)
    nums.add(v)

times = list()
seen = set()
for i in nums:
    if i in seen: continue
    mn, mx = i, i    
    queue = []
    queue.append(i)
    while queue:
        cur = queue.pop()
        if cur in seen: continue
        seen.add(cur)
        mn = min(mn, cur)
        mx = max(mx, cur)

        for k in graphs[cur]:
            queue.append(k)
    times.append([mn, mx])

times.sort()
u, v = times[0]
ans = 0
merges = list()
# print(times)
for i in range(1, len(times)):
    i, j = times[i]
    if i <= v:
        ans += 1
        v = max(v, j)
    else:
        merges.append([u,v])
        u, v = i, j

merges.append([u,v])
# print(merges)
for u, v in merges:
    for x in range(u, v+1):
        if x not in seen:
            ans += 1
print(ans)


import sys
readline = sys.stdin.readline
N, M = list(map(int, readline().split()))
 
Edge = [[] for _ in range(N)]
 
for _ in range(M):
    a, b = list(map(int, readline().split()))
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
 
used = set()
ans = 0
mp = -1
for i in range(N):
    if i in used:
        continue
    if mp >= i:
        ans += 1
        Edge[mp].append(i)
        Edge[i].append(mp)
        mp = max(mp, i)
    else:
        st = i
    
    stack = [i]
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                mp = max(mp, vf)
                used.add(vf)
                stack.append(vf)
 
print(ans)


import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
#E=[tuple(map(int,input().split())) for i in range(m)]

Group=[i for i in range(n+1)]
Nodes=[1]*(n+1)

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)]<Nodes[find(y)]:
            
            Nodes[find(y)]+=Nodes[find(x)]
            Nodes[find(x)]=0
            Group[find(x)]=find(y)
            
        else:
            Nodes[find(x)]+=Nodes[find(y)]
            Nodes[find(y)]=0
            Group[find(y)]=find(x)
            

for i in range(m):
    x,y=list(map(int,input().split()))
    Union(x,y)

MINI=[i for i in range(n+1)]
for i in range(n+1):
    MINI[find(i)]=min(MINI[find(i)],i)

ANS=0

MIN=n
ANS=0
 
for i in range(n,0,-1):
    if MIN<MINI[find(i)]:
        MINI[find(i)]=min(MINI[find(i)],MINI[find(MIN)])
        Union(MIN,i)     
        ANS+=1
 
    else:
        MIN=MINI[find(i)]

    #print(i,ANS)
 
print(ANS)


import sys
input = sys.stdin.readline

n,m = list(map(int,input().split()))
edge = [[] for _ in [0]*n]
for i in range(m):
    u,v = list(map(int,input().split()))
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

#-1:not used -2:used plus:group max
ma = [-1]*n
for i in range(n):
    if ma[i] != -1:
        continue
    tank = []
    new = [i]
    tmp = i
    while len(new) > 0:
        tank = []
        for e in new:
            for go in edge[e]:
                if ma[go] == -1:
                    ma[go] = -2
                    tmp = max(tmp,go)
                    tank.append(go)
        new = tank
    ma[i] = tmp
#print(ma)
res = 0
p = -1
for i in range(n):
    if ma[i] >= 0:
        if i < p:
            res += 1
        p = max(p,ma[i])
print(res)


from sys import stdin
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi
def ii(): return int(stdin.readline())
def fi(): return float(stdin.readline())
def mi(): return map(int, stdin.readline().split())
def fmi(): return map(float, stdin.readline().split())
def li(): return list(mi())
def si(): return stdin.readline()
n, e=mi()
a=[[] for _ in range(n+1)]
for _ in range(e):
    x, y=mi()
    a[x].append(y)
    a[y].append(x)
v=[1]*(n+1)
c=0
m=1
for i in range(1, n+1):
    #print(i, m)
    if v[i]:
        s=[i]
        if i<m:
            c+=1
        while s!=[]:
            x=s.pop()
            if v[x]:
                s+=a[x]
                v[x]=0
                if x>m:
                    m=x
print(c)

import sys
from collections import defaultdict

def main():
    n, m = [int(x) for x in sys.stdin.readline().split(" ")]
    graph = defaultdict(list)
    for _ in range(m):
        u, v = [int(x) for x in sys.stdin.readline().split(" ")]
        graph[u].append(v)
        graph[v].append(u)
    # DFS for connected components in increasing order
    maxB = -1
    count = 0
    visited = [False for v in range(0,n+1)]
    stack = []
    for i in range(1, n+1):
        # connected components
        if visited[i]:
            continue
        if i < maxB:
            count += 1
        stack = [i]
        while (len(stack) > 0):
            u = stack.pop()
            for v in graph[u]:
                if v > maxB:
                    maxB = v
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
    return(count)

print(main())


import sys
input=sys.stdin.readline
def root(k):
    while (k)!=l[k]:
        k=l[l[k]]
    return(k)
n,m=list(map(int, input().split()))
l=[i for i in range(n+1)]
sz=[1]*(n+1)
maxnode=[i for i in range(n+1)]
max_=0
for j in range(m):
    b,c=list(map(int, input().split()))
    max_=max(max_,(max(b,c)))
    ro1=root(b)
    ro2=root(c)
    if c>maxnode[ro1]:
        maxnode[ro1]=c
    if b>maxnode[ro2]:
        maxnode[ro2]=b
    if ro1!=ro2:
        if sz[ro1]>=sz[ro2]:
            sz[ro1]+=sz[ro2]
            sz[ro2]=0
            l[ro2]=ro1
        else:
            sz[ro2]+=sz[ro1]
            sz[ro1]=0
            l[ro1]=ro2
#print(l,sz,maxnode)
end=0
j=0
while end<(max_):
    for k in range(end,n):
        if maxnode[k]>k:
            kj=maxnode[k]
            jk=max(maxnode[k:maxnode[k]])
            #print(jk,kj)
            while jk>kj:
                h=jk
                jk=max((maxnode[kj:jk]))
                kj=h
                #print(jk,kj)
            end=kj
            break
    #print(end)
    for i in range(kj,k-1,-1):
        if l[root(i)]!=root(k):
            l[root(i)]=root(k)
            j+=1
            #print(l[root(i)],(i),(k),j)
        #print(l)
print(j)
        
            

            


import sys
from sys import stdin,stdout
sys.setrecursionlimit(200001)
visit=[]
def bfs(adj,i,m):
    queue = []
    queue.append(i)
    visit[i]=1
    while queue:
        h = queue.pop()
        if h>m:
            m=h
        visit[h]=1
        for j in adj[h]:
            if visit[j]==0:
                visit[j]=1
                queue.append(j)
    return m

# input = sys.stdin.readline()
n,m = stdin.readline().split()
n = int(n)
m = int(m)
adj = [[] for _ in range(n+1)]
while m>0:
    x,y = stdin.readline().split()
    x=int(x)
    y=int(y)
    adj[x].append(y)
    adj[y].append(x)
    m-=1
visit = [0]*(n+1)
result=0
count=0
k=0
for i in range(1,n+1):
    if visit[i]==0:
        if count>0 and i<k:
            result+=1
        if visit[i]==0 and len(adj[i])>0:
            count+=1
            k = bfs(adj,i,k)
stdout.write(str(result))
        
        


import sys
from sys import stdin,stdout
# sys.setrecursionlimit(300001)
visit=[]
def bfs(adj,i,m):
    queue = []
    queue.append(i)
    visit[i]=1
    while queue:
        h = queue.pop()
        if h>m:
            m=h
        visit[h]=1
        for j in adj[h]:
            if visit[j]==0:
                visit[j]=1
                queue.append(j)
    return m

# input = sys.stdin.readline()
n,m = stdin.readline().split()
n = int(n)
m = int(m)
adj = [[] for _ in range(n+1)]
while m>0:
    x,y = stdin.readline().split()
    x=int(x)
    y=int(y)
    adj[x].append(y)
    adj[y].append(x)
    m-=1
visit = [0]*(n+1)
result=0
count=0
k=0
for i in range(1,n+1):
    if visit[i]==0:
        if count>0 and i<k:
            result+=1
        if visit[i]==0 and len(adj[i])>0:
            count+=1
            k = bfs(adj,i,k)
stdout.write(str(result))
        
        


import sys
input=sys.stdin.readline
from collections import defaultdict as dd,deque as dq
def bfs(vis,u,d):
    l=[]
    q=dq([u])
    while q:
        u=q.popleft()
        vis[u]=1
        l.append(u)
        for j in d[u]:
            if(vis[j]==-1):
                
                q.append(j)
    return (min(l),max(l))
n,m=map(int,input().split())
d=dd(list)

while m:
    u,v=map(int,input().split())
    d[u].append(v)
    d[v].append(u)
    m-=1
vis=[-1]*(n+1)
seg=[]
for i in range(1,n+1):
    if(vis[i]==-1):
        seg.append(bfs(vis,i,d))
seg.sort()
mi=seg[0][0]
mx=seg[0][1]
cou=0
for i in range(1,len(seg)):
    if(seg[i][0]>=mi and seg[i][0]<=mx):
        cou+=1
        mx=max(seg[i][1],mx)
    else:
        mx=max(seg[i][1],mx)
print(cou)