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

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: not d in checked, dests)
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = [0 for _ in range(N+1)]

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: guide[d] == 0, dests)
        # 道しるべを置く
        for d in dests:
            guide[d] = n
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()
### BUGGY CODE ###

N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.append(0)
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

from functools import reduce
import math

num = int(input())
a = 1
sum = 0

def gcd(*numbers):
  return reduce(math.gcd, numbers)

def loopC(a, b, num):
  c = 1
  sum = 0
  while c <= num:
      ans = gcd(a, b, c)
      # print(a, b, c, ans)
      sum += ans
      c += 1
  return sum

def loopB(a, num):
  b = 1
  sum = 0
  while b <= num:
    ans = loopC(a, b, num)
    b += 1
    sum += ans
  return sum

while a <= num:
  ans = loopB(a, num)
  sum += ans
  a += 1

print(sum)

### FIXED CODE ###

import math

num = int(input())
sum = 0

for a in range(1, num + 1):
  for b in range(1, num + 1):
    gcd_ab = math.gcd(a, b)
    for c in range(1, num + 1):
      sum += math.gcd(gcd_ab, c)

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

import math

def prime(m):
    pf = {}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def main():
    N = int(input())
    ans = 0
    for c in range(1, N):
        p = prime(N - c)
        tmp = 1
        for v in p.values():
            tmp *= (v + 1)
        ans += tmp
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
 
p_list = get_sieve_of_eratosthenes(10**3)
 
def factorization_counta(n):
    arr = []
    temp = n
    for i in p_list:
        if i * i > n:
            break
        elif temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(cnt)
            
    if temp != 1:
        arr.append(1)
    if arr == []:
        arr.append(1)
    return arr

def main():
    N = int(input())
    ans = 1
    for c in range(2, N):
        p = factorization_counta(c)
        tmp = 1
        for v in p:
            tmp *= (v + 1)
        ans += tmp
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import numpy as np

def e(dice):
    return sum([r / dice for r in range(1, dice+1)])

n, k = map(int, input().split())
p = np.cumsum(list(map(e, (map(int, input().split())))))

p = [0] + list(p)

ans = 0
for i in range(k, n+1):
    ans = max(ans, p[i] - p[i-k])

print(ans)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from itertools import accumulate

    def e(dice):
        ans = 0
        for r in range(1, dice+1):
            ans += r /dice
        return ans

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

    p_cum = [0] + list(accumulate(p))

    ma = 0
    ind = 0
    for i in range(k, n+1):
        temp = p_cum[i] - p_cum[i-k]
        if ma < temp:
            ma = temp
            ind = i

    x = p[ind-k:ind]

    print(sum(e(d) for d in x))

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [5e9] * (n + 2)
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if not i + j < n:
            break
        dp[i + j] = min([dp[i + j], dp[i] + abs(h[i] - h[i + j])])

print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [5e9] * (n + 2)
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if not i + j < n:
            break
        dp[i + j] = min([dp[i + j], dp[i] + abs(h[i] - h[i + j])])

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

from collections import deque   ##deque 라는 데이터형 편리한듯. print도그렇고 append,pop속도도 빠르고
n = int(input())
xdeque = deque()
for i in range(n):
    command = input().split()
    if (command[0][0] == 'i'):
        x = command[1]
        xdeque.appendleft(int(x))
    elif (command[0] == 'delete'):
        x = command[1]
        try:
            xdeque.remove(int(x))
        except ValueError:
            pass
    elif (command[0][6] == 'F'):
        xdeque.popleft()
    else:
        xdeque.pop()
print(*xdeque)




### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.popleft()
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        if c == "insert":
            a.appendleft(v)
        else:
            try:
                a.remove(v)
            except:
                pass
print(" ".join(a))
### BUGGY CODE ###

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

ans_sum = 0
for i in range(0,n-1):
        for j in range(i+1,n):
                ans_sum += a[i] * a[j]

print(ans_sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

S = sum(a) % mod
ans_sum = 0
for i in range(n-1):
	S -= a[i]
	ans_sum += a[i] * S
	
print(ans_sum%mod)
### BUGGY CODE ###

from heapq import heappush, heappop
n = input()
A = map(int, raw_input().split())
left = [None]*(3*n+1)
right = [None]*(3*n+1)
lsum = rsum = 0
que = []
for i in xrange(3*n):
    lsum += A[i]
    heappush(que, A[i])
    if len(que) > n:
        v = heappop(que)
        lsum -= v
    if len(que) == n:
        left[i] = lsum
que = []
for i in xrange(3*n-1, -1, -1):
    rsum += A[i]
    heappush(que, -A[i])
    if len(que) > n:
        v = heappop(que)
        rsum += v
    if len(que) == n:
        right[i] = rsum
ans = -10**18
for i in xrange(3*n):
    if left[i] is not None and right[i+1] is not None:
        ans = max(ans, left[i] - right[i+1])
print ans


### FIXED CODE ###

from heapq import heappush, heappop
n = input()
A = map(int, raw_input().split())
left = [None]*(3*n+1)
right = [None]*(3*n+1)
lsum = rsum = 0
que = []
for i in xrange(3*n):
    lsum += A[i]
    heappush(que, A[i])
    if len(que) > n:
        v = heappop(que)
        lsum -= v
    if len(que) == n:
        left[i] = lsum
que = []
for i in xrange(3*n-1, -1, -1):
    rsum += A[i]
    heappush(que, -A[i])
    if len(que) > n:
        v = heappop(que)
        rsum += v
    if len(que) == n:
        right[i] = rsum
ans = -10**18
for i in xrange(3*n):
    if left[i] is not None and right[i+1] is not None:
        ans = max(ans, left[i] - right[i+1])
print ans
### BUGGY CODE ###

n=int(input())
a = list(map(lambda x:format(x,'b'),map(int,input().split())))
b = list(map(len,a))

p = 10**9+7
s = 0
for i in range(max(b)):
    zero = 0
    one = 0
    for j in range(n):
        if len(a[j]) < i+1:
            zero += 1
            continue
        if a[j][-(1+i)]=='1':
            one += 1
        else:
            zero += 1
    s += (one*zero)*2**i%p

print(s%p)


### FIXED CODE ###

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

p = 10**9+7
ans = 0
for i in range(60):
    x = 1<<i
    one = sum(1 for j in a if j&x)
    ans += pow(2,i,p)*one*(n-one)

print(ans%p)
### BUGGY CODE ###

if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[]] * n
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        if len(nexts[ai]) == 0:
            nexts[ai] = [bi]
        else:
            nexts[ai].append(bi)
        if len(nexts[bi]) == 0:
            nexts[bi] = [ai]
        else:
            nexts[bi].append(ai)

    scores = [m] * m
    scores[0] = 0

    red_set = [0]
    new_red_set = []
    blue_set = [x + 1 for x in range(n - 1)]
    new_blue_set = blue_set

    arrows = [0] * n

    j = 0

    while len(blue_set) != 0:
        for r in red_set:
            for nxt in nexts[r]:
                if nxt in blue_set:
                    new_blue_set.remove(nxt)
                    if nxt not in new_red_set:
                        new_red_set.append(nxt)
                    arrows[nxt] = r
                blue_set = new_blue_set

        red_set = new_red_set
        new_red_set = []
    
    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)
    

### FIXED CODE ###

from sys import stdin
from collections import deque
input = stdin.readline


def main():
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for _ in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    blues = [-1] * n # 1 is in blues
    blues[0] = 0 # 0 is not in blues
    checked = [0] * n

    red_deque = deque([0])

    while len(red_deque) > 0:
        rd = red_deque[0]
        red_deque.popleft()
        if checked[rd] == 0:
            checked[rd] = 1
            for nxt in nexts[rd]:
                if blues[nxt] == -1:
                    blues[nxt] = rd
                    red_deque.append(nxt)

    print("Yes")
    for blue in blues[1:]:
        print(blue + 1)
    

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

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

ans = 1

for i in range(n):
    ans *= a[i]
    
if(ans > 1000000000000000000):
    print(-1)
    
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1

for i in range(n):
    ans *= a[i]
    if(ans > 1000000000000000000):
        break
    
if(ans > 1000000000000000000):
    print(-1)
    
else:
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC98 D

import sys
input = sys.stdin.readline
def d():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    for r in range(n):
        for l in range(r+1):
            s = []
            f = 1
            for c in a[l:r+1]:
                for k in range(20):
                    if (c >> k) & 1:
                        if k in s:
                            f = 0
                            break
                        else:
                            s.append(k)
                if not f:
                    break
            if f:
                ans += 1
    print(ans)

if __name__ == '__main__':
    d()


### FIXED CODE ###

#!/usr/bin/env python3
#ABC98 D

import sys
input = sys.stdin.readline
def d():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    l = 0
    r = 0
    s = 0
    while l < n and r < n:
        while s&a[r] == 0:
            s += a[r]
            r += 1
            ans += r-l
            if r == n:
                break
        if l==r:
            s += a[r]
            r += 1
        s -= a[l]
        l += 1
    print(ans)

if __name__ == '__main__':
    d()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
INF = 10**10
f=[INF for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if f[sg[0]] == INF:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if f[i] == INF:
            if not dfs(i,0):
                return "No"
    return "Yes"

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
f=[False for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if type(f[sg[0]]) == bool:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if type(f[i]) == bool:
            if not dfs(i,1):
                return "No"
    return "Yes"

print(main())
### BUGGY CODE ###

from fractions import gcd as bltin_gcd
#return arr
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def coprime(a, b):
    return bltin_gcd(a, b) == 1
def rmdb(n, li):
  lst = [x for x in li if x%n != 0]
  return lst

a, b = map(int, input().split())
cf_list = cf(a,b)

ng_set = set()
for i in range(1, len(cf_list)):
  for j in range(1, i):
    if cf_list[i] % cf_list[j] == 0:
      ng_set.add(cf_list[i])
      break
  
print(len(cf_list)-len(ng_set))


### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a, b = map(int, input().split())
a_list = prime_factorize(a)
b_list = prime_factorize(b)
a_set = set(a_list)
b_set = set(b_list)

ans_set = a_set & b_set
ans_set.add(1)
print(len(ans_set))
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)

print(max(dist))

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)
print(max(dist))
### BUGGY CODE ###

def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = [0] * height
    count_by_width = [0] * width
    bomb_is = [[False] * width for _ in range(height)]
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is[bom_h][bom_w] = True
        # 最大らしき十字はわかるが，交差点にあるかどうかが不明だ。
        # 最大になりそうな十字がいっぱい（前マスに爆弾，など）だと，
        # 結局 O(H*W) で間に合わなそう。3秒あるけど 10^10 じゃあなあ。
        # DP ぽくはあるが，どう DP を作るかだ。

    # h, w にでいくつ爆破できるか。
    dp = [[0] * width for _ in range(height)]
    dp[0][0] = count_by_height[0] + count_by_width[0] - bomb_is[0][0]
    ans = 0
    for x in range(height):
        for y in range(width):
            now = dp[x][y]
            ans = max(ans, now)
            if x < height - 1:
                if dp[x + 1][y] != 0:
                    continue
                dp[x + 1][y] = (
                    now + count_by_height[x + 1] - count_by_height[x]
                    + bomb_is[x][y] - bomb_is[x + 1][y])
            if y < width - 1:
                if dp[x][y + 1] != 0:
                    continue
                dp[x][y + 1] = (
                    now + count_by_width[y + 1] - count_by_width[y]
                    + bomb_is[x][y] - bomb_is[x][y + 1])
    return ans


if __name__ == '__main__':
    ans = main()
    print(ans)


### FIXED CODE ###

from collections import defaultdict


def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = defaultdict(int)
    count_by_width = defaultdict(int)
    bomb_is = set()
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is.add((bom_h, bom_w))
    max_h = max(v for v in count_by_height.values())
    max_w = max(v for v in count_by_width.values())
    max_h_index = [i for i, x in count_by_height.items() if x == max_h]
    max_w_index = [i for i, x in count_by_width.items() if x == max_w]
    no_cross = any(
        (hh, ww) not in bomb_is for hh in max_h_index for ww in max_w_index)
    return max_h + max_w - (not no_cross)


if __name__ == '__main__':
    ans = main()
    print(ans)
### BUGGY CODE ###

n,k =map(int,input().split())
s =[]
for i in range(k):
    l,r=map(int,input().split())
    s+=(list(range(l,r+1)))
S= set(s)

mod = 998244353
step = [0] * (n+1)

step[0]=1
for i in range(0,n+1):
    for s in S:
        if i+s<=n:
            step[i+s]=(step[i]+step[i+s])%mod

print(step[n-1]%mod)

   

### FIXED CODE ###

mod = 998244353
n,k =map(int,input().split())
step =[0]*(n+1)
# step[0]=1
step[1]=1
stepsum=[0]*(n+1)
stepsum[1]=1
l=[0]*k
r=[0]*k
for i in range(k):
    l[i],r[i]=map(int,input().split())

for i in range(2,n+1):
    for j in range(k):
        li = i - r[j]
        ri = i - l[j]
        if ri <= 0:
            continue
        # li = max(1,li)
        step[i] += stepsum[ri] - stepsum[max(0,li-1)]
        # step[i] %= mod
        # print(step)
    stepsum[i] = ( stepsum[i-1] + step[i] )%mod


print(step[n]%mod)
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(n)]

for i in range(n):
    #print(A)
    tmp = A.pop(i)
    print(max(A))
    A.insert(i, tmp)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(n)]
tmp = sorted(A)
maxa = max(A)
for i in range(n):
    if A[i] == maxa:
        print(tmp[-2])
    else:
        print(maxa)
### BUGGY CODE ###

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged
N,M = map(int,input().split(" "))
isbr = []
for i in range(M):
  isbr.append(list(map(int,input().split(" "))))
isbr = merge_sort(isbr)
rem = []
i = 0
while i < M:
  a = isbr[i][0]
  b = isbr[i][1]
  flag = 0
  while a <= b:
    if b in rem:
      flag = 1
      break
    else:
      b-=1
  if flag == 0:
    rem.append(isbr[i][1]-1)
  i+=1
print(len(rem))

### FIXED CODE ###

#D問題
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1]-1)
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1]-1)
print(len(bridges))