Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def solve(prev, r, dic):
    d = 0
    t = r
    stack = []
    stack += [[prev, r, d]]
    while stack:
        prev, r, d1 = stack.pop(-1)
        if r in dic:
            for vtx, cost in dic[r]:
                if vtx == prev:
                    continue
                stack += [[r, vtx, d1 + cost]]
                if d < d1 + cost:
                    d = d1 + cost
                    t = vtx
    return d, t

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
for t in range(0, n):
    r1, t1 = solve(-1, t, dic)
    print(r1)


### FIXED CODE ###

def solve(prev, r, n, dic):
    d = [0] * n
    md = 0
    t = r
    stack = []
    stack += [[prev, r, 0]]
    while stack:
        prev, r, d1 = stack.pop(-1)
        if r in dic:
            for vtx, cost in dic[r]:
                if vtx == prev:
                    continue
                stack += [[r, vtx, d1 + cost]]
                if d[vtx] < d1 + cost:
                    d[vtx] = d1 + cost
                    if md < d[vtx]:
                        md = d[vtx]
                        t = vtx
    return d, t

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
d1, t1 = solve(-1, 0, n, dic)
d2, t2 = solve(-1, t1, n, dic)
d3, t3 = solve(-1, t2, n, dic)
print("\n".join(map(str, [max(a, b) for a, b in zip(d2, d3)] )))
### BUGGY CODE ###

from collections import Counter

n = int(input())
S = [input() for _ in range(n)]

char_list = []

for s in S:
	char_list.append(Counter(s))

ans = 0
for i in range(n-1):
	for j in range(i+1,n):
		if char_list[i] == char_list[j]:
			ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
S = [input() for i in range(n)]

ans = 0
cnt = {}

for s in S:
    s = "".join(sorted(s))
    if s in cnt:
        ans += cnt[s]
        cnt[s] += 1
    else:
        cnt[s] = 1

print(ans)
### BUGGY CODE ###

S='10'
Input=int(input())
A=[]
while Input!=len(A)+9:
    count=0
    for i in range(len(S)-1):
        if abs(int(S[i])-int(S[i+1])) <=1:
            count+=1
        if count==len(S)-1:
            A.append(S)
    S=str(int(S)+1)
print(int(A[-1]))

### FIXED CODE ###

import heapq
K=int(input())
queue=[i for i in range(1,10)]
heapq.heapify(queue)
for i in range(K-1):
    n=heapq.heappop(queue)
    if n%10==0:
        heapq.heappush(queue,n*10+0)
        heapq.heappush(queue,n*10+1)
    elif n%10==9:
        heapq.heappush(queue,n*10+8)
        heapq.heappush(queue,n*10+9) 
    else:
        heapq.heappush(queue,n*10+(n%10))
        heapq.heappush(queue,n*10+(n%10)+1)
        heapq.heappush(queue,n*10+(n%10)-1)
print(queue[0])
### BUGGY CODE ###


import itertools

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = 10 ** 20
    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = list(map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c
    for k in range(1,N+1):
        for j in range(1, N + 1):
            for i in range(1, N + 1):
                graph[j][i] = min(graph[j][i] , graph[j][k] + graph[k][i])

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i,j in zip(range(0,R-1),range(1,R)):
            fr = temp[i]
            to = temp[j]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(ans)

if __name__ == "__main__":
    do()

### FIXED CODE ###


import itertools

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = 10 ** 20
    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = (map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c
    for k in range(1,N+1):
        for j in range(1, N + 1):
            for i in range(1, N + 1):
                graph[j][i] = min(graph[j][i] , graph[j][k] + graph[k][i])

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i in range(0,R-1):
            fr = temp[i]
            to = temp[i + 1]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(ans)

if __name__ == "__main__":
    do()
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        for j in range(-2, 3):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-2, 3):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j * \
                                k == 0 and abs(j) != 2 and abs(k) != 2 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x]
                            queue.appendleft([new_y, new_x])
                        elif maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x] + 1
                            queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

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


prod = sorted(prod,reverse=True)

for _ in range(m):
    prod[0]=prod[0]//2

    prod=sorted(prod,reverse=True)



print(sum(prod))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
prod = list(map(int,input().split()))
prod = list(map(lambda x: x*(-1),prod))

heapq.heapify(prod)

for _ in range(m):
    a = heapq.heappop(prod)*(-1)

    a = a//2

    heapq.heappush(prod,(-1)*a)


ans = list(map(lambda x: (-1)*x,prod))

print(sum(ans))
### BUGGY CODE ###

import queue

h, w = list(map(int, input().split()))
smat = [input() for _ in range(h)]

def bfs(x0, y0):
    dist = {}
    q = queue.Queue()
    q.put((x0, y0, -1))

    mx = 0
    while not q.empty():
        x, y, d = q.get()
        nd = d + 1
        dist[(x, y)] = nd
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if (nx, ny) in dist:
                # already visited
                continue
            v = (nx, ny, nd)
            q.put(v)
    
    return mx

mxall = 0
for x0 in range(h):
    for y0 in range(w):
        if smat[x0][y0] == '.':
            mx = bfs(x0, y0)
            mxall = max(mxall, mx)
print(mxall)


### FIXED CODE ###

import collections

h, w = list(map(int, input().split()))
smat = [input() for _ in range(h)]

def bfs(x0, y0):
    visited = [[0 for _ in range(w)] for _ in range(h)]
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

if all(all(col == '.' for col in row) for row in smat):
    print((w - 1) + (h - 1))
else:
    mxall = 0
    for x0 in range(h):
        for y0 in range(w):
            if smat[x0][y0] == '.':
                mx = bfs(x0, y0)
                mxall = max(mxall, mx)
    print(mxall)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf') for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

print(dp[n - 1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * (n + k + 10)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            if dp[i + j] == float('inf'):
                dp[i + j] = dp[i] + abs(h[i + j] - h[i])
            else:
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
        else:
            break


print(dp[n-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N = input()
input_line = input()
Ai = input_line.split(" ")
NumAi = np.array(Ai)
Comment = "YES"
N = int(N)
for i in range(N):
  for j in range(i+1,N):
    if(NumAi[i] == NumAi[j]):
      Comment = "NO"
      break
      
print(Comment)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N = input()
input_line = input()
Ai = input_line.split(" ")
NumAi = np.array(Ai)
Comment = "NO"
N = int(N)
if(len(NumAi) == len(np.unique(NumAi))):
  Comment = "YES"

#if(NumAi != set)
      
print(Comment)
### BUGGY CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))

now = 1
i = 0
while i < k:
    now *= a[i]
    i += 1
while i < n:
    old = now
    now = (now / a[i-k]) * a[i]
    print("Yes" if now > old else "No")
    i += 1


### FIXED CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))

i = k
# while i < k:
#     now *= a[i]
#     i += 1
while i < n:
    old = a[i-k]
    now = a[i]
    print("Yes" if now > old else "No")
    i += 1
    # old = now
    # now = (now / a[i-k]) * a[i]
    # print("Yes" if now > old else "No")
    # i += 1
### BUGGY CODE ###

s=input()
s_=s
while "01" in s or "10" in s:
	s=s.replace("01","")
	s=s.replace("10","")
print(len(s_)-len(s))

### FIXED CODE ###

s=input()
sum1=len([i for i in s if i=="1"])
sum0=len([i for i in s if i=="0"])
if sum1>sum0:
	print(sum0*2)
else:
	print(sum1*2)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    x=l[i]
    dp[i]=min((dp[j]+abs(x-l[j])) for j in range(max(0,i-k),i))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

def f(x, y, z):
    return (x+y+z)**2 - x*y - y*z - z*x

  
N = int(input())
pattern = []

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            pattern.append(f(x, y, z))

for i in range(1, N+1):
    print(pattern.count(i))


### FIXED CODE ###

def f(x, y, z):
    return (x+y+z)**2 - x*y - y*z - z*x


N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, int(i**0.5)+2):
        for y in range(x, int(i**0.5)+2):
            if f(x, y, y-1) >= i:
                break
            l = y - 1
            r = int(i**0.5) + 1
            while r >= l:
                z = (r+l) // 2
                if f(x, y, z) == i:
                    if x < y:
                        if x == z or y == z:
                            ans += 3
                        else:
                            ans += 6
                    else:
                        if z == y:
                            ans += 1
                        else:
                            ans += 3
                if f(x, y, z) > i:
                    r = z - 1
                else:
                    l = z + 1

    print(ans)
### BUGGY CODE ###

from collections import*
I=lambda:map(int,input().split())
n,m=I()
a=Counter(I())
exec("b,c=I();a[c]+=b;"*m)
s=0
for k,v in sorted(a.items())[::-1]:
 if n<v:exit(print(s+k*n))
 n-=v;s+=k*v

### FIXED CODE ###

from collections import Counter
n, m, *d = map(int, open(0).read().split())
a = Counter(d[:n])
for b, c in zip(d[n::2], d[n+1::2]):
    a[c] += b
ans = 0
for k, v in sorted(a.items())[::-1]:
    if n < v:
        exit(print(ans + k * n))
    n -= v
    ans += k * v
### BUGGY CODE ###

from collections import deque
N = int(input())
ans = deque([])
for _ in range(N):
    a = int(input())
    if a not in ans:
        ans.append(a)
    else:
        ans.remove(a)
print(len(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
ans = Counter([int(input()) for _ in range(N)])
cnt = 0
for c in ans.values():
    if c%2 == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))


S = [0]
for i in range(1, N + 1):
    S.append(A[i - 1] + S[i-1])


ans = 0
for l in range(0, N):
    for r in range(l + 1, N + 1):
        if (S[r] - S[l]) % M == 0:
            ans += 1


print(ans)


### FIXED CODE ###

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))

S = [0]
m = defaultdict(lambda: 0)
for i in range(1, N + 1):
    tmp = (A[i - 1] + S[i - 1]) % M
    S.append(tmp)

ans = 0
for i in range(N + 1):
    ans += m[S[i]]
    m[S[i]] += 1

print(ans)
### BUGGY CODE ###

from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0
arrived = [[0 for i in range(W)] for j in range(H)]
arrived[C_h-1][C_w-1] = 1

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    elif S[h][w] == "#":
        return False
    elif arrived[h][w] == True:
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    if cost > dist[h][w] and dist[h][w] != -1:
        continue
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
            arrived[h+dh][w+dw] = True
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int, S: int):
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            for r in range(K+1):
                if(i+j+r == S):
                    ans += 1

    print(ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

k,s = (int(_) for _ in input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if(0 <= z <= k):
            ans += 1

print(ans)
### BUGGY CODE ###

l,r=map(int,input().split())
if l-r>=2019:
    print(0)
    exit()
ans=2020
for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans=min((i*j)%2019,ans)
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())
if r-l>=2019:
    print(0)
    exit()
ans=2020
for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans=min((i*j)%2019,ans)
print(ans)
### BUGGY CODE ###

from math import sqrt, floor
from collections import deque


def prime_generator():
    prime = set()
    yield 2
    i = 3
    while True:
        for d in prime:
            if not (i % d):
                break
        else:
            yield i
            prime.add(i)
        i += 2


nstr = input()
n = int(nstr)
max = floor(sqrt(n))
a = deque()

for p in prime_generator():
    if p > n:
        break
    while not (n % p):
        n = n // p
        a.append(p)

a.appendleft(nstr + ':')
print(*a)

### FIXED CODE ###

from math import sqrt
from collections import deque


def divide_repeat(p):
    global n, a, limit
    while not (n % p):
        a.append(p)
        n = n // p
        limit = sqrt(n)


nstr = input()
n, p = int(nstr), 3
limit = sqrt(n)
a, i = deque(), 3

divide_repeat(2)

while p <= limit:
    divide_repeat(p)
    p += 2

if n > 1:
    a.append(n)

print(nstr + ': ', end='')
print(*a)
### BUGGY CODE ###

N, M = map(int, input().split())

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(a in war):
        if(b < war[a]):
            war[a] = b
    else:
        war[a] = b

ans = 0

while(war != {}):
    # print(war)
    ans += 1
    bridge = [0 for i in range(N - 1)]
    for a, b in war.items():
        for i in range(a, b):
            bridge[i - 1] += 1
    index = bridge.index(max(bridge))
    # print(index)
    for a, b in list(war.items())[:]:
        if(a <= index + 1 < b):
            war.pop(a)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

for b in b_list:
    a = war[b]
    if(a <= r_bridge):
        continue
    else:
        r_bridge = b - 1
        ans += 1

print(ans)