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

def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  #xとyが同じ集合に属するかの判定
  def same(x,y):
      return find2(x) == find2(y)

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  #根なら-size,子なら親の頂点

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  import collections
  chk = collections.deque([])
  for i in range(n):
    chk_append = chk.append
    chk_append(find(i)*10**6+find2(i))
  chk = list(chk)
  for i in range(n):
    c = collections.Counter(chk)
    ans[i] += c[chk[i]]

  ans = list(map(str,ans))
  print(' '.join(ans))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  dic = {}
  chk = []
  for i in range(n):
      p1 = find(i)
      p2 = find2(i)
      chk.append((p1,p2))
      if (p1,p2) in dic:
          dic[(p1,p2)] += 1
      else: 
          dic[(p1,p2)] = 1
  print(' '.join([str(dic[chk[i]]) for i in range(n)]))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, *A = map(int, open(0).read().split())
b = 1
for a in A:
  b *= a
print(-1 if b > 10**18 else b)


### FIXED CODE ###

N, *A = map(int, open(0).read().split())
b = 1
A = sorted(A)
for a in A:
  if b > 10**18:
    break
  b *= a
print(-1 if b > 10**18 else b)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for x in range(1, min(b,n) + 1):
    fx = int(a*x/b) - a * int(x/b)
    if ans < fx:
        ans = fx
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
sum = 0
for i in range(N-1):
    for m in range(i+1, N):
        sum += A[i]*A[m]

if sum < 1000000007:
    print(sum)
else:
    print(int(sum%(1e9 + 7)))

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))
S = sum(A)
ans = 0
for i in range(N):
    S -= A[i]
    ans += A[i] * S
    

ans = ans % (10 ** 9  +7)        

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

a, b = map(int, input().split())
 
tmpA = max(a, b)
tmpB = min(a, b)
 
while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB
 
already = [0 for i in range(tmpA)]
already[0] = 1
pointer = 1
tmp = tmpA
 
while tmp != 1:
    for i in range(2, tmp // already[pointer - 1]):
        if tmp % i == 0:
            already[pointer] = i
            pointer += 1
            tmp = tmp // i
            break
    else:
        already[pointer] = tmp
        break

print(max(len(set(already)) - 1, 1))


### FIXED CODE ###

import math

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

tmpA = max(a, b)
tmpB = min(a, b)

while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB

tmp = tmpA
res = 1

for i in range(2, int(math.sqrt(tmp)) + 1):
    if tmp % i == 0:
        res += 1
        tmp //= i
    else:
        continue

    while tmp % i == 0:
        tmp = tmp//i


if tmp != 1:
    res += 1

print(res)
### BUGGY CODE ###

n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

mod = 1000000007
result = [0]*(n+1)
result[0] = 1
for i in range(1,n+1):
    result[i] = (result[i-1] + result[i-2])%mod
    if i in a:
        result[i] = 0

print(result[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for i in range(m)])

mod = 1000000007
result = [0]*(n+1)
result[0] = 1
for i in range(1,n+1):
    if i in a:
        result[i] = 0
    else:
        result[i] = (result[i-1] + result[i-2])%mod

print(result[n])
### BUGGY CODE ###

def sol():
    import sys
    input = sys.stdin.readline

    h,w,d=map(int,input().split())
    A=[]
    for i in range(h):
        l=list(map(int,input().split()))
        for j in range(w):
            A.append([l[j],i,j])
    ans=[]
    for i in sorted(A):
        ans.append(i[1:])
    q=int(input())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,input().split())
    for i in range(h*w-1,d-1,-1):
        ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
    for i in range(d):
        ans[i]=0
    for i in range(q):
        print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))
sol()

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])
### BUGGY CODE ###

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

mod = 1000000000 + 7
ans = 0

for i in range(n):
    for j in range(i+1,n,1):
        pdt = 0
        if i<j:
            pdt = a[i] * a[j]
        ans %= mod
        ans += pdt

ans %= mod
print(ans)

### FIXED CODE ###

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

mod = 1000000000 + 7
ans = 0

for i in range(n):
    sum_a -= a[i]
    pdt = a[i] * sum_a
    ans += pdt

ans %= mod
print(ans)
### BUGGY CODE ###

import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

N,M = map(int,input().split())
ans = M//N
while M%ans != 0 and ans != 1:
    ans -= 1
print(ans)


### FIXED CODE ###

from bisect import bisect_right

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass 


N,M = map(int,input().split())
a = M//N
c = True

li = divisor(M)

x = bisect_right(li,a)

print(li[x-1])
### BUGGY CODE ###

A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in range(1, l):
    S += (int(A[-n])*d)
    sm = S % 2019
    lis[sm] += 1
    d *= 10

result = 0

for n in lis:
    result += (n*(n-1)/2)


print(int(result))


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
  G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

if '#' not in S or '.' not in S:
    print(0)
else:
    ans = []
    for i in range(N):
        if S[i] == '#':
            ans.append(S[:i].count('#') + S[i:].count('.'))
    else:
        print(min(ans))

### FIXED CODE ###

N = int(input())
S = list(input())

white = S.count('.')
black = 0
ans = white + black

for x in S:
    if x == '.':
        white -= 1
    else:
        black += 1
    ans = min(ans, white+black)

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


H,W,M=map(int,input().split())
AB=[tuple(map(int,input().split()))for i in range(M)]
AB=[(a-1,b-1)for a,b in AB]
st=set(AB)

Wc=[0]*W
Hc=[0]*H
for a,b in AB:
    Hc[a]+=1
    Wc[b]+=1

ans=0
for i in range(H):
    for j in range(W):
        add = -1 if (i,j) in st else 0
        tmp= Hc[i] + Wc[j] + add
        ans=max(ans,tmp)

print(ans)

### FIXED CODE ###


from collections import defaultdict

H,W,M=map(int,input().split())
AB=[tuple(map(int,input().split()))for i in range(M)]
AB=[(a-1,b-1)for a,b in AB]
st=set(AB)

Wc=defaultdict(lambda :0)
Hc=defaultdict(lambda :0)
for a,b in AB:
    Hc[a]+=1
    Wc[b]+=1

Hm=max(Hc.values())
hhh=list(Hc.keys())
www=list(Wc.keys())
for i in hhh:
    if Hc[i]!=Hm:
        Hc.pop(i)
Wm=max(Wc.values())
for j in www:
    if Wc[j]!=Wm:
        Wc.pop(j)

ans=0
count=0
for i in Hc.keys():
    for j in Wc.keys():
        add = -1 if (i,j) in st else 0
        tmp= Hc[i] + Wc[j] + add
        ans=max(ans,tmp)
        if count>300000:
            break
        count+=1

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

import math

K = int(input())
N = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            g = math.gcd(a,b)
            g = math.gcd(g,c)
            N += g

print(N)

### FIXED CODE ###

import math
K = int(input())
N = 0

for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            g = math.gcd(a,b)
            g = math.gcd(g,c)
            if(a != 1 or b != 1 or c != 1 ):
                if(a != b or a != c):
                    if(a != K or b != K or c != K ):
                        if(a != b and a != c and b != c):
                            g *= 6
                        else:
                            g *= 3
            N += g

print(N)
### BUGGY CODE ###

from numpy import *
from functools import lru_cache

H, W, D = map(int, input().split())
A = array([list(map(int, input().split())) for _ in range(H)])
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    (h,), (w,) = where(A==i+1)
    dp[i] = (h, w)

@lru_cache(H*W)
def f(p, q) :
    x, y = dp[p-1]
    i, j = dp[q-1]
    return abs(x-i)+abs(y-j)

for l, r in LR :
    print(sum([f(p, p+D) for p in range(l, r, D)], dtype=int))

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [None for _ in range(H*W)]
for i, l in enumerate(A) :
    for j, v in enumerate(l) :
        dp[v-1] = (i, j)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        pass
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])
### BUGGY CODE ###

def add(s,f,c,is_reversed):
    if f == '1':
        ht = 0
    elif f == '2':
        ht = 1
        
    if is_reversed != ht:
            ns = s + c 
    if is_reversed == ht:
            ns = c + s

    return ns

def msf(s,q,ql):
    len_ql = len(ql)
    is_reversed = 0
    for i in range(0,len_ql):
        t1 = ql[i][0]
        if t1 == "1":
            is_reversed ^= 1
        elif t1 == "2":
            f = ql[i][1]
            c = list(ql[i][2])
            s = add(s,f,c,is_reversed)

    return ''.join(s) if not is_reversed else ''.join(reversed(s))
    
if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [list(input().split()) for _ in range(q)]
    
    print(msf(s,q,ql))


### FIXED CODE ###

from collections import deque

def msf(s,queries):
    queue = deque(s)
    addl = queue.appendleft
    addr = queue.append
    is_reversed = 0

    for query in queries:
        if query[0] == '1':
            is_reversed ^= 1
            addl,addr = addr,addl
        elif query[0] == '2':
            f = query[1]
            c = query[2]
            if f == '1':
                addl(c)
            elif f == '2':
                addr(c)
    return ''.join(queue) if not is_reversed else ''.join(reversed(queue))

if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [input().split() for i in range(q)]
    print(msf(s,ql))
### BUGGY CODE ###

import copy
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
flag = False

while flag == False:
    #print(moji)
    moji_old = copy.deepcopy(moji)
    for i in range(h*w):
        y = i//w
        x = i%w
        if moji_old[y][x] == '.':
            flag = False
            break
        else:
            flag = True
    
    for i in range(h*w):
        y = i//w
        x = i%w
        #print(i)
        if moji_old[y][x] == '#':
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                moji[ny][nx] = '#'
    
    if flag == True:
        break
                
    ans += 1
    
print(ans)

### FIXED CODE ###

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

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

dist = [[-1]*w for _ in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
q = deque()

for i in range(h*w):
    y = i//w
    x = i%w
    #print(i)
    if moji[y][x] == '#':
        q.append(i)
        dist[y][x] = 0

#ans = -1

ans = 0

while q:
    #print(q.qsize())
    tmp = q.popleft()
    y = tmp//w
    x = tmp%w
    d = dist[y][x]
    #print(tmp,num)
    for j in range(4):
        nx = x+vx[j]
        ny = y+vy[j]
        #print(ny,nx)
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if dist[ny][nx] == -1:
            dist[ny][nx] = d+1
            #moji[ny][nx] = '#'
            q.append(ny*w+nx)
    #ans += 1
    ans = max(d,ans)

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

num = int(input())
numbers_row = input().split(" ")
numbers = []
for i in numbers_row:
  numbers.append(int(i))
  
noBool = False

for i, number in enumerate(numbers):
  for j in numbers[i+1:]:
    if j == number:
      noBool = True
      break

if noBool == False:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

num = int(input())
numbers_row = input().split(" ")
numbers = []
for i in numbers_row:
  numbers.append(int(i))
  
Bool = len(numbers) != len(set(numbers))

if Bool == True:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

s = input()
q = int(input())
status = 1
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        status *= -1
    else:
        if (query[1] == "1" and status == 1) or (query[1] == "2" and status == -1):
            s = query[2] + s
        else:
            s = s + query[2]

print(s if status == 1 else "".join(list(reversed(s))))


### FIXED CODE ###

s = input()
q = int(input())
status = 1
top = []
bottom = []
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        status *= -1
    else:
        if (query[1] == "1" and status == 1) or (query[1] == "2" and status == -1):
            top.append(query[2])
        else:
            bottom.append(query[2])

tmp = "".join(top[::-1]) + s + "".join(bottom)
print(tmp if status == 1 else tmp[::-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  z=DD.count(0)*((n-1)//k)
  a_n=x+sum(DD)*((n-1)//k)
  for i in range((n-1)%k):
    a_n+=DD[i]
    if DD[i]==0:
      z+=1
  ans-=z+a_n//m
  print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z1,z2,r,s=0,0,0,0
  for i,d in enumerate(DD):
    s+=d
    if i<v:
      r+=d
      if d==0:
        z1+=1
        z2+=1
    elif d==0:
      z2+=1
  ans-=(z2*u+z1)+(x+s*u+r)//m
  print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
num_hen = n-1
info = [list(map(int,input().split())) for i in range(num_hen)]

for i in range(num_hen):
  info[i][0] -=1
  info[i][1] -=1

tree=[[] for i in range(n)]
for i in range(num_hen):
  tree[info[i][0]].append(info[i][1])
  tree[info[i][1]].append(info[i][0])
  
#paintedが0のときまだ塗られていない、1のとき黒、-1のとき白
painted=[0]*n
painted[0]=1
painted[n-1]=-1

#0からn-1まで行くための経路を求める（dfsで経路復元する）。
#keiroが経路になる
que = deque()
for i in range(len(tree[0])):
  que.append([tree[0][i],0])
visited=[False]*n 
visited[0]=True
keiro =[]
while que:
  v = que.pop()
  for i in range(len(keiro))[::-1]:
    if keiro[i][1]>=v[1]:
      del keiro[i]
  keiro.append(v)
  if v[0] == n-1:
    del keiro[-1]
    break
  elif not visited[v[0]]:
    for i in range(len(tree[v[0]])):
      que.append([tree[v[0]][i],v[1]+1])
    visited[v[0]]=True

#経路を黒と白で塗る
for i in range(len(keiro)):
  if i%2==0:
    painted[keiro[i//2][0]]=1
  else:
    painted[keiro[len(keiro)-1-i//2][0]]=-1

#全部の頂点に渡ってペイントするためのdfs
def dfs(i,color):
  que2 = deque()
  for element in tree[i]:
    que2.append(element)
  while que2:
    w = que2.pop()
    if painted[w]==0:
      painted[w]=color
      for element in tree[w]:
        que2.append(element)
  return

for i in range(n):
  if painted[i]==1:
    dfs(i,1)
  elif painted[i]==-1:
    dfs(i,-1)

print("Fennec" if painted.count(1) > painted.count(-1) else "Snuke")


### FIXED CODE ###

from collections import deque
n = int(input())
num_hen = n-1
info = [list(map(int,input().split())) for i in range(num_hen)]

for i in range(num_hen):
  info[i][0] -=1
  info[i][1] -=1

tree=[[] for i in range(n)]
for i in range(num_hen):
  tree[info[i][0]].append(info[i][1])
  tree[info[i][1]].append(info[i][0])
  
#paintedが0のときまだ塗られていない、1のとき黒、-1のとき白
painted=[0]*n
painted[0]=1
painted[n-1]=-1

#0からn-1まで行くための経路を求める（dfsで経路復元する）。
#keiroが経路になる
que = deque()
for i in range(len(tree[0])):
  que.append([tree[0][i],0])
visited=[False]*n 
visited[0]=True
keiro ={}
while que:
  v = que.pop()
  keiro[v[1]]=v[0]
  if v[0] == n-1:
    final = v[1]
    break
  elif not visited[v[0]]:
    for i in range(len(tree[v[0]])):
      que.append([tree[v[0]][i],v[1]+1])
    visited[v[0]]=True

#経路を黒と白で塗る
for i in range(final):
  if i%2==0:
    painted[keiro[i//2]]=1
  else:
    painted[keiro[final-1-i//2]]=-1

#全部の頂点に渡ってペイントするためのdfs
def dfs(i,color):
  que2 = deque()
  for element in tree[i]:
    que2.append(element)
  while que2:
    w = que2.pop()
    if painted[w]==0:
      painted[w]=color
      for element in tree[w]:
        que2.append(element)
  return

for i in range(n):
  if painted[i]==1:
    dfs(i,1)
  elif painted[i]==-1:
    dfs(i,-1)

print("Fennec" if painted.count(1) > painted.count(-1) else "Snuke")
### BUGGY CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)

### FIXED CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

n , m = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()

cut = [l[0]]
for i in range(1,m):
    for j in range(len(cut)):
        key = 0
        if cut[j][0] <= l[i][0]  and l[i][0] < cut[j][1] :
            cut[j][0] = l[i][0]
            key +=1
        if cut[j][0] < l[i][1] and l[i][1] <= cut[j][1]  :
            cut[j][1] = l[i][1]
            key +=1
        if key > 0:
            break
    
    if key == 0 :
        cut.append(l[i])


print(len(cut))
    


### FIXED CODE ###

n , m = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()
l = l[::-1]
cnt = 1
key = l[0][0]
for i in range(1,m):
    if key >= l[i][1]:
        cnt += 1
        key = l[i][0]
print(cnt)