Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        root[x] = find(x)
        return root[x]
    else:
        return x

def unite(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        root[x] += root[y]
        root[y] = x
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * n
def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]
    

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
        

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = len([i for i in root if i < 0]) - 1
print(ans)
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
s1=[0]*n
s1[0]=a[0]
s2=[0]*n
if a[0]>0:
    s2[0]=a[0]
for i in xrange(1,n):
    s1[i]+=s1[i-1]+a[i]
    if a[i]>0:
        s2[i]+=s2[i-1]+a[i]
ans=-float("inf")
for i in xrange(n-k+1):
    tmp1=s1[i+k-1]-s1[max(0,i-1)]
    tmp2=s2[n]-(s2[i+k-1]-s2[max(0,i-1)])
    ans=max(ans,tmp1+tmp2,tmp2)
print ans


### FIXED CODE ###

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
total=[0]*(n+1)
asum=[0]*(n+1)
for i in xrange(n):
    asum[i+1]=asum[i]+a[i]
    if a[i]>0:
        total[i+1]=total[i]+a[i]
    else:
        total[i+1]=total[i]
ans=0
for i in xrange(n-k+1):
    tmp=asum[i+k]-asum[i]
    ans=max(ans,tmp+total[i]+total[n]-total[i+k],total[i]+total[n]-total[i+k])

print(ans)
dp = ["" for i in range(51)]
dp[0] = "P"

def solve(n, dp):
    if n == 0:
        return dp[0]
    else:
        if dp[n] == "":
            k = solve(n - 1,dp)
            return 'B' + k + 'P' + k + 'B'
        else:
            return dp[n]
n, x = list(map(int, input().split()))
dp = solve(n,dp)
print(dp[-x:].count('P'))


### FIXED CODE ###

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

a = [1]
p = [1]
for i in range(1,n):
    a.append(a[i - 1] * 2 + 3)
    p.append(2 * p[i - 1] + 1)

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + a[n-1]:
        return f(n-1, x-1)
    else:
        return p[n-1] + 1 + f(n-1, x-2-a[n-1])
print(f(n,x))
import collections
n=int(input())
a=list(map(int,input().split()))
if len(set(a))==1 and a[0]==0:
  print('Yes')
elif n%3!=0:
  print('No')
elif len(set(a))!=3:
  print('No')
else:
  a=list(set(a))
  for i in range(len(a)):
    a[i]=format(a[i],'020b')
  l=[0 for i in range(20)]
  for i in range(n):
    for j in range(20):
      if a[i][j]=='1':
        l[j]+=1
  ct=0
  for j in range(20):
    if l[j]==2 or l[j]==0:ct+=1
  if ct==20:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=format(a[i],'030b')
l=[0 for i in range(30)]
for i in range(n):
  for j in range(30):
    if a[i][j]=='1':
      l[j]+=1
for j in range(30):
  l[j]=l[j]%2
 
if 1 in l:
  print('No')
else:
  print('Yes')
l=[]
list(map(int,input().split())).append(l)
list(map(int,input().split())).append(l)
list(map(int,input().split())).append(l)
for i in range(2):
  if l[i][1]-l[i][0]!=l[i+1][1]-l[i+1][0] and l[i][2]-l[i][1]!=l[i+1][2]-l[i+1][1]:
    print('No')
    break
  if i==1:
    print('Yes')


### FIXED CODE ###

l=[]
l.append(list(map(int,input().split())))
l.append(list(map(int,input().split())))
l.append(list(map(int,input().split())))
for i in range(2):
  if l[i][1]-l[i][0]!=l[i+1][1]-l[i+1][0] or l[i][2]-l[i][1]!=l[i+1][2]-l[i+1][1]:
    print('No')
    break
  if i==1:
    print('Yes')
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

N, K = map(int, input().split())
As = list(sorted(set(map(int, input().split()))))

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

for i in range(len(As)-1):
    diff = As[i+1] - As[i]
    if i == 0:
        unit = diff
    else:
        unit = gcd(unit, diff)

ok = False
for a in As:
    if (a - K) % unit == 0 and K <= a:
        ok = True

if ok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

N, K = map(int, input().split())
As = list(sorted(set(map(int, input().split()))))

def gcd(a, b):
    while b:
    	a, b = b, a % b
    return a

# corner
if len(As) == 1:
    if K == As[0]:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
else:        
    for i in range(len(As)-1):
        diff = As[i+1] - As[i]
        if i == 0:
            unit = diff
        else:
            unit = gcd(unit, diff)
    
    ok = False
    for a in As:
        if (a - K) % unit == 0 and K <= a:
            ok = True
    
    if ok:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
x = int(input().count(1))
print(x)

### FIXED CODE ###

x = (input().count('1'))
print(x)
n = int(input())
ans = ['']

quo = n
rem = 0

while True:
    rem = quo%26
    quo = quo//26
    if rem == 0:
        ans.insert(0, 'z')
        if quo < 2:
            break
    else:
    
    if quo == 0:
        break

print(*ans, sep="")

### FIXED CODE ###

n = int(input())
ans = ''
check = 'abcdefghijklmnopqrstuvwxyz'

while n != 0:
    n -= 1
    ans += check[n%26]
    n = n//26

print(ans[::-1])
day = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = 7 - index(input())
print(day[S])


### FIXED CODE ###

day = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = 7 - day.index(input())
print(S)
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
a,b,h = IR(3)
print(((a+b)*h)//2)
"""
#B
s = SR(3)
i = 0
while 1:
    x = s[i].pop(0)
    if len(s[i]) == 0:
        if i == 0:print("A")
        if i == 1:print("B")
        if i == 2:print("C")
    if x == "a":i = 0
    if x == "b":i = 1
    if x == "c":i = 2
#C

#D
"""
h,w,n = LI()
dp = [0 for i in range(10)]
dp[0] = (h-2)*(w-2)
q = defaultdict(int)
for i in range(n):
    a,b = LI()
    a -= 1
    b -= 1
    for i in [-1,0,1]:
        for j in [-1,0,1]:
            if 0 < a+i < h-1 and 0 < b+j < w-1:
                q[(a+i)*w+b+j] += 1
                dp[q[(a+i)*w+b+j]] += 1
                dp[q[(a+i)*w+b+j]-1] -= 1
for i in dp:
    print(i)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
a,b,h = IR(3)
print(((a+b)*h)//2)
"""
#B
s = SR(3)
i = 0
while 1:
    if len(s[i]) == 0:
        if i == 0:print("A")
        if i == 1:print("B")
        if i == 2:print("C")
        quit()
    x = s[i].pop(0)
    if x == "a":i = 0
    if x == "b":i = 1
    if x == "c":i = 2
#C

#D
"""
h,w,n = LI()
dp = [0 for i in range(10)]
dp[0] = (h-2)*(w-2)
q = defaultdict(int)
for i in range(n):
    a,b = LI()
    a -= 1
    b -= 1
    for i in [-1,0,1]:
        for j in [-1,0,1]:
            if 0 < a+i < h-1 and 0 < b+j < w-1:
                q[(a+i)*w+b+j] += 1
                dp[q[(a+i)*w+b+j]] += 1
                dp[q[(a+i)*w+b+j]-1] -= 1
for i in dp:
    print(i)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
demands = (tuple(map(int,
                     line.strip().split())) for line in sys.stdin.readlines())
demands.sort(key=lambda demand: demand[1])

bridge = -1
cnt = 0
for ai, bi in demands:

    if ai <= bridge:
        continue

    else:
        bridge = bi - 1
        cnt += 1

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
# demands = [tuple(map(int, input().split())) for i in range(m)]
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda x: x[1])

compressed = []
while demands:
    a, b = demands.pop()

    for i, (ai, bi) in enumerate(compressed):
        if b <= ai or bi <= a:
            continue

        else:
            compressed[i] = [max(a, ai), min(b, bi)]
            break

    else:
        compressed.append([a, b])

print(len(compressed))
x,k,d = map(int, input().split())
lists = []
i = 1
 

if k*d <= x:
  answer = x - k*d
else:
  while i * d <= x and i <= d:
    minx = min(abs(i*d), (i * d - x))
    if (k-i) % 2 == 0:
      answer = abs(minx)
    if (k-i) % 2 == 1:
      answer = abs(min(abs(minx-d), abs(minx+d)))
    i += 1

print(answer)

### FIXED CODE ###

x,k,d = map(int, input().split())
lists = []
x = abs(x)

step = int(x/d) 

if step >= k:
  answer = x - k * d
elif step < k:
  k_left = k - int(step)
  if k_left % 2 == 0:
    answer = x % d
  if k_left % 2 == 1:
    answer = abs(x - step * d - d)

print(answer)
a = int(input())
b = int(input())

ans = a - b + 1
print(ans)


### FIXED CODE ###


l = [int(x) for x in input().split( )]

ans = l[0] - l[1] + 1
print(ans)
N,M = map(int,input().split())
print(math.factorial(N) + math.factorial(M))

### FIXED CODE ###

N,M = map(int,input().split())
print(int(N*(N-1)/2 + M*(M-1)/2))
def f(x,y,z):
    n=x**2 + y**2 + z**2 + x*y + y*z + z*x
    return n

N=int(input())

if N>=7000:
  print(aaa)

anslist=[0]*60100

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            n= f(x,y,z)
            anslist[n-1]+=1

for i in range(N):
    print(anslist[i])


### FIXED CODE ###

def f(a,b,c):
    n=(a+b+c)**2 -a*b -b*c -c*a
    return n

N=int(input())

anslist=[0]*1000005

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            n= f(x,y,z)
            anslist[n-1]+=1

for i in range(N):
    print(anslist[i])
n,k=map(int,input().split())
s=input()
if s[k-1]==A:
  s[k-1]=a
elif s[k-1]==B:
  s[k-1]=b
else:
  s[k-1]=c
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
if s[k-1]=='A':
  s = s[:k-1] + "a" + s[k:]
elif s[k-1]=='B':
  s=s[:k-1] + "b" + s[k:]
else:
  s=s[:k-1] + "c" + s[k:]
print(s)
i = 1
while True:
  pritn 'Case {number}: {input}'.format(number=i, input=raw_input())
  i += 1

### FIXED CODE ###

i = 1
while True:
  x = raw_input()
  if x == '0':
    break
  print 'Case {0}: {1}'.format(i, x)
  i += 1
for i in range(1000):
print "Hello World"

### FIXED CODE ###

for i in range(1000):
    print 'Hello World'
x=input().split()

n=int(x[0])
t=int(x[1])
k=int(x[2])

print(k*ceil(20/12))

### FIXED CODE ###

x=input().split()

n=int(x[0])
t=int(x[1])
k=int(x[2])


if n%t==0: print(k*int(n/t))
else: print(k*int(n/t + 1))
from collections import deque
h,n = map(int, input().split())
p = [10**10]*(2*h)
ab = []
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
q = deque()
for i in ab:
  q.append(i)
while q:
  a,b = q.popleft()
  if b<p[a]: p[a]=b
  else: b=p[a]
  if a>=h: continue
  for i,j in ab:
    if b+j<p[a+i]:
      p[a+i]=b+j
      q.append((a+i,b+j))
print(min(p[h:-1]))

### FIXED CODE ###

h,n = map(int, input().split())
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
amax = max(a for a,b in ab)
p = [0]*(h+amax+1)
for i in range(1,h+amax):
  p[i] = min(p[i-a]+b for a,b in ab)
print(p[h])
a,b,h=map(int,input().split())
print((a+b)/h)

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
print((a+b)*h//2)
n = int(input())
s = []
for _ in range(n):
    s.append(input())
check = []
testc = 1000
for i in range(n):
    test = 0
    for c in s[i]:
        test += int(c)
    if test == testc:
        check.append(i)
    elif test < testc:
        check.clear()
        testc = test
        check.append(i)

res = -1
if testc > 1:
    check = check[0]

for i in check:
    tres = 1
    flag = [-2 for i in range(n)]

    flag[i] = 1
    que = [i]
    while que:
        target = que.pop()
        for j in range(n):
            if s[target][j] == "1":
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    tres = -1
                    break
        if tres == -1:
            break

    if tres == -1:
        continue
    else:
        res = max(res, max(flag))

print(res)


### FIXED CODE ###

import collections

n = int(input())
s = []
for _ in range(n):
    ch = input()
    s.append([int(c) for c in ch])


def graph(i, n, s):
    flag = [-2 for _ in range(n)]
    flag[i] = 1
    que = collections.deque([i])
    while que:
        target = que.popleft()
        for j in range(n):
            if s[target][j] == 1:
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    return [-1, -1]
    mf = max(flag)
    return [flag.index(mf), mf]


r1 = graph(0, n, s)
if r1[0] == -1:
    print(-1)
else:
    res = r1[1]
    for i in range(1, n):
        r = graph(i, n, s)
        res = max(res, r[1])
    print(res)
x = input()
if X == "1":
    print("0")
else:
    print("1")

### FIXED CODE ###

X = input()
if X == "1":
    print("0")
else:
    print("1")
N,M,C=map(int, input().split())
# N:Aのソースコード(配列)数
# M:AとBの配列の中身の数
# C:計算で利用

B=list(map(int,input.split()))
A=[]
for i in range(N):
  a=map(int,input().split())
  A.append(a)
    
ans=0
x=0
for i in range(N):
  for j in range(M):
     ans+=A[i][j]*B[j]
  if ans+C>0:
     x+=1

print(x)

### FIXED CODE ###

N,M,C=map(int, input().split())
# N:Aのソースコード(配列)数
# M:AとBの配列の中身の数
# C:計算で利用

B=list(map(int,input().split()))
A=[]
for i in range(N):
  a=list(map(int,input().split()))
  A.append(a)
    
x=0
for i in range(N):
  ans=0
  for j in range(M):
     ans+=A[i][j]*B[j]
  if ans+C>0:
     x+=1


print(x)
import networkx as nx
n,m=map(int,input().split())
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
if m==0:print(1);exit()
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver and lasttime[atnode][silver-costmoney]>time+costtime:
            heappush(hp,(time+costtime,silver-costmoney,atnode))
            lasttime[atnode][silver-costmoney]=min(lasttime[atnode][silver-costmoney],time+costtime)

    if silver!=2500 and lasttime[node][min(silver+c[node],2500)]>time+d[node]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        lasttime[node][silver+c[node]]=min(lasttime[node][min(silver+c[node],2500)],time+d[node])
        
print(*mintimes[1:],sep="\n")

### FIXED CODE ###

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")
n=int(input())
a=list(map(int,input().split()))
d=[0]*(10**5+1)
ans=0
for i in range(len(a)):
  d[a[i]]+=1
for i in range(1,len(d)):
  if d[i]>i:
    ans+=d[i]-i
  elif d[i]<i:
    ans+=d[i]
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d=[0]*(10**5+1)
ans=0
for i in range(len(a)):
  if a[i]<=10**5:
    d[a[i]]+=1
  else:
    ans+=1
for i in range(1,len(d)):
  if d[i]>i:
    ans+=d[i]-i
  elif d[i]<i:
    ans+=d[i]
print(ans)
k,s=map(int,input().split(" "))
ans=0
for x in range(k+1):
  for y in range(x, k+1):
    for z in range(y, k+1):
      t = x+y+z
      if t == s:
        ans += 1
print(ans)
    

### FIXED CODE ###

a,b,c=map(int,input().split(" "))
if a == b:
  print(c)
elif a == c:
  print(b)
else:
  print(a)
# D - Disjoint Set of Common Divisors

import math

A, B = map(int, input().split())
C = math.gcd(A, B)

primes = []
i = 2
while i * i <= C:
    while C % i == 0:
        C //= i
        primes.append(i)
    i += 1
if C > 1:
    primes.append(C)

print(len(set(primes)) + 1)


### FIXED CODE ###

# D - Disjoint Set of Common Divisors

import fractions

A, B = map(int, input().split())
C = fractions.gcd(A, B)

primes = []
i = 2
while i * i <= C:
    while C % i == 0:
        C //= i
        primes.append(i)
    i += 1
if C > 1:
    primes.append(C)

print(len(set(primes)) + 1)
from itertools
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

l=list(itertools.permutations(list(range(1,n+1))))
print(abs(l.index(p)-L.index(q)))

### FIXED CODE ###

import itertools
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

l=list(itertools.permutations(list(range(1,n+1))))
print(abs(l.index(p) - l.index(q)))
N, M = map(int, input().split())
def dfs(dic, p, memo):
    if memo[p] != -1:
        return memo[p]
    m = 0
    for d in dic[p]:
        m = max(m, dfs(dic, d, memo)+1)
    memo[p] = m
    return m
dic = [[] for i in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(dic, i, memo)
    ans = max(ans,k)
print(ans)

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(100000)
 
N, M = map(int, input().split(" "))
G = [[] for _ in range(N)]
 
for _ in range(M):
    x, y = map(int, input().split(" "))
    G[x-1].append(y-1)
dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]
 
    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen
ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)
s = input()
if s[:4] < 2019 or s[:4] == 2019 and s[6:7] <= 4:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
N=input()
N=int(N)

if N%2==1:
    N=int(((N-1)/2)+1)
    print(N)
else:
    N=int(N/2)
    print(N)
    
N,R=input().split()

N=int(N)
R=int(R)

if N>=10:
    print (R)
else:
    print(R+(100*(10-N)))

### FIXED CODE ###

N,R=input().split()

N=int(N)
R=int(R)

if N>=10:
    print (R)
else :
    print(R+(100*(10-N)))
N,M = map(int,input().split())
Stlist = [1]*N
for i in range(M):
    breakstair = int(input())
    Stlist[breakstair-1] = 0
Comb = [1,2]
if Stlist[0] == 0:
    Comb[0] = 0
    Comb[1] = 1
if Stlist[1] == 0:
    Comb[1] = 0
for i in range(2,N):
    Comb.append((Comb[i-1] + Comb[i-2])%(10**9+7))
    if Stlist[i] == 0:
        Comb[i] = 0
print(Comb[-1])


### FIXED CODE ###

N,M = map(int,input().split())
Stlist = [1]*N
for i in range(M):
    breakstair = int(input())
    Stlist[breakstair-1] = 0
Comb = [1,2]
if N == 1:
    Comb = Stlist
else:
    if Stlist[0] == 0:
        Comb[0] = 0
        Comb[1] = 1
    if Stlist[1] == 0:
       Comb[1] = 0
    for i in range(2,N):
        Comb.append((Comb[i-1] + Comb[i-2])%(10**9+7))
        if Stlist[i] == 0:
            Comb[i] = 0
print(Comb[-1])
li=list(input())
li.sort()
while True:   
    if len(li)==0:
        print("Yes")
        break
    elif li[0]==li[1]:
        li.pop(0)
        li.pop(0)
    else:
        print("No")
        break

### FIXED CODE ###

strlist = list(input())
findlist="qazwsxedcrfvtgbyhnujmikolp"
flist=list(findlist)
flag = "Yes"
for a in flist:
    if not strlist.count(a) % 2 == 0:
        flag = "No"
print(flag)
h, w = map(int, input().split())

print(h*w)
print(2*h + 2*w)



### FIXED CODE ###

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

print(h*w, 2*h+2*w)
import math
n = int(input())

data = list(map(int,input().split()))

s = 0

for i in range(n):
    s += data[i]
    data[i] = s

a = data[-1]
res = math.inf
for i in range(n-1):
    res = min(res,abs(data[i]-(a-data[i])))
print(res)


### FIXED CODE ###

n = int(input())

data = list(map(int,input().split()))

s = 0

for i in range(n):
    s += data[i]
    data[i] = s

a = data[-1]
res = -1
for i in range(n-1):
    if res<0:
        res = abs(data[i]-(a-data[i]))
    else:
        res = min(res,abs(data[i]-(a-data[i])))
print(res)
n,k=map(int,imput().split())
a=list(map(int,input().split()))
a=sorted(a)
sum=0
for i in range(len(a)-1,len(a)-k,-1):
  sum=sum+a[i]
print(sum)

### FIXED CODE ###

n,k=map(int,input().split())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(k):
  ans+=L.pop()
print(ans)
s = input()

flg = 0
for i, c in enumrate(range(s)):
  if i%2!=0:
    if c in ["R", "U", "D"]:
      continue
    else:
      flg = 1
      break
  else:
    if c in ["R", "U", "D"]:
      continue
    else:
      flg = 1
      break
    
ans = "Yes" if flg else "No"
print(ans)

### FIXED CODE ###

s = input()

flg = 0
for i, c in enumerate(s):
  if i%2!=0:
    if c in ["L", "U", "D"]:
      continue
    else:
      flg = 1
      break
  else:
    if c in ["R", "U", "D"]:
      continue
    else:
      flg = 1
      break

ans = "Yes" if not flg else "No"
print(ans)