Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
graph = [[] for _ in range(m + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def my_permutations(nums, t, path):
    if len(nums) == 0:
        path.append(t)
        return
    for i in range(len(nums)):
        my_permutations(nums[:i] + nums[i + 1:], t + [nums[i]], path)

def dfs(graph, permu, n):
    visited = [False] * (n + 1)
    next_nodes = set([1])
    for p in permu:
        if visited[p]:
            return False
        if p not in next_nodes:
            return False
        visited[p] = True
        next_nodes = set(graph[p])
    return True

path = []
my_permutations([i for i in range(1, n + 1)], [], path)
ans = 0
for permu in path:
    if permu[0] != 1:
        continue
    if dfs(graph, permu, n):
        ans += 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def my_permutations(nums, t, path):
    if len(nums) == 0:
        path.append(t)
        return
    for i in range(len(nums)):
        my_permutations(nums[:i] + nums[i + 1:], t + [nums[i]], path)

def dfs(graph, permu, n):
    visited = [False] * (n + 1)
    next_nodes = set([1])
    for p in permu:
        if visited[p]:
            return False
        if p not in next_nodes:
            return False
        visited[p] = True
        next_nodes = set(graph[p])
    return True

path = []
my_permutations([i for i in range(1, n + 1)], [], path)
ans = 0
for permu in path:
    if permu[0] != 1:
        continue
    if dfs(graph, permu, n):
        ans += 1
print(ans)
a=int(input())
b=int(input())
c=int(input())
d=int(input())

if c>=b or d<=a:
    print(0)
else:
    if a<=c and b<=d:
        print(b-c)
    elif a<=c and b>d:
        print(d-c)
    elif a>c and b<=d:
        print(b-a)
    else:
        print(d-a)

### FIXED CODE ###

s = input().split()
a=int(s[0])
b=int(s[1])
c=int(s[2])
d=int(s[3])

if c>=b or d<=a:
    print(0)
else:
    if a<=c and b<=d:
        print(b-c)
    elif a<=c and b>d:
        print(d-c)
    elif a>c and b<=d:
        print(b-a)
    else:
        print(d-a)
N = int(input())
SP = []
for _ in range(N):
  SP.append(input().split())
print(sorted(range(len(s)), key=lambda k: s[k],reverse=True))

### FIXED CODE ###

N = int(input())
SP = []
for _ in range(N):
    SP.append([i for i in input().split()])
for n in range(N):
    SP[n][1] = str(100 - int(SP[n][1])).rjust(3,'0')
SP2 = []
for n in range(N):
    SP2.append(SP[n][0]+SP[n][1])
ans = sorted(range(len(SP2)), key=lambda k: SP2[k])
for i in ans:
    print(i+1)
from functools import reduce

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

limit = pow(10, 18)

ans = 1.0
for e in nums:
    ans *= e

if ans >= limit:
    ans = -1

print(int(ans))


### FIXED CODE ###

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

limit = pow(10, 18)

ans = 1

if 0 in nums:
    ans = 0
else:
    for e in nums:
        if ans > limit / e:
            ans = -1
            break
        else:
            ans *= e

if ans > limit:
    ans = -1

print(int(ans))
a, b = map(int, input().split())
ans = 1 if 1 not in (a, b) else 2 if not in (a, b) else 3
print(ans)

### FIXED CODE ###

a, b = int(input()), int(input())
ans = 1 if 1 not in (a, b) else 2 if 2 not in (a, b) else 3
print(ans)
def main():
    # parse
    N, i = parse() 
    # compute
    result = compute(N, i)
    # show result
    print(result)

def compute(N, i):
    return N + 1 - i

def parse():
    vars = split_stdin(get_stdin())
    return vars[0], vars[1] 

def get_stdin():
    return input()

def split_stdin(stdin_val, delim = ' '):
    return [x for x in stdin_val.split(delim) if x != '']

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    # parse
    N, i = parse()
    # compute
    result = compute(N, i)
    # show result
    print(result)

def compute(N, i):
    return N + 1 - i

def parse():
    vars = split_stdin(get_stdin())
    return int(vars[0]), int(vars[1])

def get_stdin():
    return input()

def split_stdin(stdin_val, delim = ' '):
    return [x for x in stdin_val.split(delim) if x != '']

if __name__ == "__main__":
    main()
a,b =map(int,input().split)
if (a*b)%2:
  print("Odd")
else:
  print("Even")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
import bisect

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
for i in range(1,10):
    if 2**i>2*(10**9):
        break
    else:
        B.append(2**i)
B.append(2**(i+1))
ans=0
#print(B)
for i in range(N):
    X=bisect.bisect_left(B,A[N-1-i])
    if B[X]==A[N-1-i]:
        X+=1
    #print(X)
    if B[X]==2*A[N-1-i]:
        #print(B[X],A[N-i])
        A[N-1-i]+=0.3
        #print(A[bisect.bisect_left(A,B[X]-A[N-i]+0.3)],B[X]-A[N-i]+0.3)
        if A[bisect.bisect_left(A,B[X]-A[N-1-i]+0.3)]==B[X]-A[N-1-i]+0.3:
            ans+=1
            #print(B[X],i)
            #print(B[X])
            A[bisect.bisect_left(A,B[X]-A[N-1-i]-0.2)]-=0.1
    elif A[bisect.bisect_left(A,B[X]-A[N-1-i])]==B[X]-A[N-1-i]:
        ans+=1
        #print(B[X],i)
        A[bisect.bisect_left(A,B[X]-A[N-1-i])]-=0.1
        A[N-1-i]+=0.2
print(ans)
#print(A)
#print(B)

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
A.append(999999999999999)
B=[]
for i in range(1,35):
    B.append(2**i)
ans=0
for i in range(N):
    if A[N-1-i]==int(A[N-1-i]):
        for j in range(len(B)):
            if A[N-1-i]<B[j]:
                break
        if A[bisect.bisect_left(A,B[j]-A[N-1-i])]==B[j]-A[N-1-i]:
            if bisect.bisect_left(A,B[j]-A[N-1-i])<N-1-i:
                A[bisect.bisect_left(A,B[j]-A[N-1-i])]-=0.1
                A[N-1-i]+=0.1
                ans+=1
print(ans)
import math
tan = int(input())
chou = int(input())
ji = int(input())
hun = int(input())

kakudo = abs(((ji*30 + hun*.5) - (hun*6)))

if kakudo > 180:
    kakudo = kakudo-360
kakudo = abs(math.cos(math.radians(kakudo)))
ans =( chou**2 + tan**2 - 2*chou*tan*kakudo)**.5
print(ans)

### FIXED CODE ###

import math
chou, tan, ji, hun = map(int,input().split())

kakudo = abs(((ji*30 + hun*.5) - (hun*6)))

if kakudo > 180:
    kakudo = 360 - kakudo

kakudo = abs((math.radians(kakudo)))
ans =( chou**2 + tan**2 - 2*chou*tan*math.cos(kakudo))**.5
print(ans)
l=[[[0 for i in range(10)] for i in range(3)] for i in range(4)]
n=int(input())
for i in range(n):
	a,b,c,d=list(map(int,input().split()))
	l[a-1][b-1][c-1]=d 
for i in l:
	for j in i:
		print(" ".join(j))
	if not i==l[-1]:
		print("####################")

### FIXED CODE ###

l=[[[0 for i in range(10)] for i in range(3)] for i in range(4)]
n=int(input())
for i in range(n):
	a,b,c,d=list(map(int,input().split()))
	l[a-1][b-1][c-1]+=d
for i in l[:-1]:
	for j in i:
		print(" "+" ".join(list(map(str,j))))
	print("####################")

for j in l[-1]:
	print(" "+" ".join(list(map(str,j))))
a=input()
a=int(a)
if a%2==0:
    print(a)
else
    print(a*2)

### FIXED CODE ###

N=input()
N=int(N)
if N%2==0:
    print(N)
else:
    print(N*2)
n=int(input())
count=0
maxlen=[]
xlist=list(map(int,input().split()))
if n==1:
    print(0)
else:
    for i in range(n - 1):
        if xlist[i] >= xlist[i + 1]:
            count += 1
        else:
            maxlen.append(count)
            count = 0
    print(max(max(maxlen), count))










### FIXED CODE ###

n=int(input())
count=0
maxlen=[]
xlist=list(map(int,input().split()))
if n==1:
    print(0)
elif n==2:
    if xlist[0]>=xlist[1]:
        print(1)
    else:
        print(0)
else:
    for i in range(n - 1):
        if xlist[i] >= xlist[i + 1]:
            count += 1
            if i==n-2:
                maxlen.append(count)
        else:
            maxlen.append(count)
            count = 0
    print(max(maxlen))
n, l = map(int, input().split())
lst = [sorted(input()) for _ in range(n)]
print(''.join(sorted(lst)))

### FIXED CODE ###

n, l = map(int, input().split())
s = [input().rstrip() for i in range(n)]
print(''.join(sorted(s)))
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def rec(a: int, b: int) -> int:
    if a == b:
        return a
    
    else:
        mx = max(a,b)
        mn = min(a,b)
        return 2*mn + rec(mn, mx-mn)
    
n,x = li()
print(n + rec(x, n-x))
    

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def light_length(a:int, b:int) -> int:
    if a > b:
        a,b = b,a
    
    if b%a == 0:
        return 2 * a * (b//a) - a

    return 2 * (b//a) * a + light_length(a, b%a)

n,x = li()

print(n + light_length(x,n-x))
S=input()

S[3]="8"
print(S)

### FIXED CODE ###

a=input().split('/')
a[0]=int(a[0])+1

print(str(a[0])+'/'+a[1]+'/'+a[2])
import math
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, len(a)):
    ans = math.gcd(ans, a[i])
    
print(ans)

### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, len(a)):
    ans = gcd(ans, a[i])
    
print(ans)
n, k = map(int, input().split())
total = 0
for i in range(k, n+2):
  total += i(n+1-i) + 1
  total %= 10**9 + 7
print(total)

### FIXED CODE ###

n, k = map(int, input().split())
total = 0
for i in range(k, n+2):
  total += i*(n+1-i) + 1
  total %= 10**9 + 7
print(total)
s = input()
ll = [i for i in range(97,123,1)]
for j in s:
    s_num = ord(j)
    if s_num in ll:
        ll.remove(s_num)
    else:
        pass
print(chr(ll[0]))


### FIXED CODE ###

s = input()
ll = [i for i in range(97,123,1)]
for j in s:
    s_num = ord(j)
    if s_num in ll:
        ll.remove(s_num)
    else:
        pass
if len(ll) != 0:
    print(chr(ll[0]))
else:
    print("None")
while True:
	n, m = (int(x.strip()) for x in raw_input().split())
	if n == 0 and m == 0: break
	p = [int(x.strip()) for x in raw_input().split()]
	s = sum(p)
	p.sort(reverse=True)
	for x in p[m - 1::m]:
		s -= x
	print s

### FIXED CODE ###

while True:
	try:
		n, m = (int(x.strip()) for x in raw_input().split())
		if n == 0 and m == 0: break
		p = [int(x.strip()) for x in raw_input().split()]
		s = sum(p)
		p.sort(reverse=True)
		for x in p[m - 1::m]:
			s -= x
		print s
	except:
		pass
s = list(input())
t = list(input())
n = len(s)
m = len(t)
i = 0
j = 0
point = []
if n<m:
    print("UNRESTORABLE")
    exit()
while i<n:
    if s[i]==t[j] or s[i]=="?":
        j+=1
        i+=1
    else:
        j=0
        i+=1

    if j==m:
        point.append(i-m)
if len(point)==0:
    print("UNRESTORABLE")
    exit()
i = 0
x = "".join(s)
x = list(x)
ans = [x]*len(point)
for l in range(len(point)):
    while i<n:
        if ans[l][i]=="?" and i!=point[l]:
            ans[l][i]="a"
            i +=1
        elif i==point[l]:
            for k in range(m):
                ans[l][i+k]=t[k]
            i = i+m
        else:
            i+=1
ans.sort()
print("".join(ans[0]))

### FIXED CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
ans = []
for i in range(n-m+1):
    flag = True
    for j in range(m):
        if s[i+j]!="?" and s[i+j]!=t[j]:
            flag = False
            break
    if flag:
        tmp = (s[:i] + t + s[(i+m):])
        a = []
        for j in range(n):
            if tmp[j]=="?":
                a.append("a")
            else:
                a.append(tmp[j])
        tmp = "".join(a)
        ans.append(tmp)

ans.sort()

if len(ans)>0:
    print(ans[0])
else:
    print("UNRESTORABLE")
import math
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    c=int(math.sqrt(a*b))
    if c<2 :
        print('0')
    elif a==1 or b==1:
        print(2c-3)
    elif c*(c+1)<a*b:
        print(2c-1)
    else:
        print(2c-2)

### FIXED CODE ###

import math
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    c=int(math.sqrt(a*b))
    if c*(c+1)<a*b: print(2*c-1)
    elif a*b==c*c and a!=b:  print(2*c-3)
    else:  print(2*c-2)
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N = int(input())
    D = list(map(int, input().split()))

    # cnt[k] = v ... 深さkのノード数
    cnt = {}
    max_depth = 0
    for d in D:
        max_depth = max(max_depth, d)
        if d not in cnt:
            cnt[d] = 1
        else:
            cnt[d] += 1

    # 頂点1との距離が0になるノードは1つしか存在しない
    if 0 not in cnt:
        print(0)
        exit(0)
    elif cnt[0] > 1:
        print(0)
        exit(0)

    ans = 1
    MOD = 998244353
    for i in range(0, max_depth):
        if i not in cnt:
            ans = 0
            break
        ans *= cnt[i] ** cnt[i + 1]
        ans %= MOD

    print(ans)


### FIXED CODE ###

import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N = int(input())
    D = list(map(int, input().split()))

    # cnt[k] = v ... 深さkのノード数
    cnt = {}
    max_depth = 0
    for d in D:
        max_depth = max(max_depth, d)
        if d not in cnt:
            cnt[d] = 1
        else:
            cnt[d] += 1

    # 頂点1との距離が0になるノードは1つしか存在しない
    if D[0] != 0:
        print(0)
        exit(0)
    elif cnt[0] > 1:
        print(0)
        exit(0)

    ans = 1
    MOD = 998244353
    for i in range(0, max_depth):
        if (i not in cnt) or (i + 1 not in cnt):
            ans = 0
            break
        ans *= cnt[i] ** cnt[i + 1]
        ans %= MOD

    print(ans)
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = str(bin(e))
    e=e[2:]
     e=e[::-1]
                

         
           




### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

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

ac=[False]*N
wa=[0]*N

for _ in range(N):
    p,s=input().split()
    p=int(p)-1

    if s=="AC":
        ac[p]=True
    else:
        if not ac[p]:
            wa[p]+=1

a=0
b=0

for i in range(N):
    if ac[i]:
        a+=1
        b+=wa[i]

print(a,b,sep=" ")


### FIXED CODE ###

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

ac=[False]*n
wa=[0]*n

for i in range(m):
    p,s=input().split()
    p=int(p)-1

    if s=="AC":
        ac[p]=True
    else:
        if not ac[p]:
            wa[p]+=1

a=0
b=0

for i in range(n):
    if ac[i]:
        a+=1
        b+=wa[i]

print(a,b,sep=" ")
import sys
import math
w, h, x, y = map(int, sys.stdin.readline().split())

d = [None for i in range(4)]
d[0] = abs(x*1+y*(-1)+w*h)/math.sqrt(1**2 + (-1)**2)
d[1] = abs(x*(-h/w)+y*(-1)+h)/math.sqrt((-h/w)**2 + (-1)**2)
d[2] = abs(x-w*0.5)
d[3] = abs(y-h*0.5)

if int(w-2*x)==0 and int(h-2*y)==0:
  print(w*h/2.0, 1)
  exit()
elif int(w-2*x)==0 or int(h-2*y)==0:
  print(w*h/2.0, 0)
  exit()

if int(d1) == 0 or int(d2) == 0:
  if int(w-2*x)==0 and int(h-2*y)==0:
    print(w*h/2.0, 1)
  else:
    print(w*h/2.0, 0)
elif d.index().min(d) == 0:
  if x > 0.5*w:
    if y < h/w*x:
      print((x*w*w)/y*0.5, 0)
    else:
      print((x*h*h)/y*0.5, 0)
  else:
    b = h - (h-y)/(w-x)*w
    if y < h/w*x:
      print(h*(w-b*(w-x)/(h-y))*0.5, 0)
    else:
      print(w*(h-b)*0.5, 0)
elif d.index().min(d) == 1:
  if int(d[0]-d[1]) == 0:
    casenum = 1
  else:
    casenum = 0
    
  if x > 0.5*w:
    if  y > -h/w*x+h:
      print(w*(-(y-h)*w/x)*0.5, casenum)
    else:
      print(h*x*h/(h-y)*0.5, casenum)
  else:
    b = (h + y*w/(x-w)) * (x-w)/y
    if  y > -h/w*x+h:
      print(h*(w-(b-h)*x/(y-h))*0.5, casenum)
    else:
      print(w*(h-b)*0.5, casenum)
elif d.index().min(d) == 2:
  if y > 0.5*h:
    b = w*y/(w-2*x)
    x1=(x-0.5*w)/y*(b-h)
    if x > 0.5*w:
      print(h*(0.5*w+w-x1)*0.5, 0)
    else:
      print(h*(0.5*w+0.5*w-x1)*0.5, 0)
  else:
    b = h - 0.5*w*y/(x-0.5*w)
    x1=b*y/(0.5*w-x)
    if x > 0.5*w:
      print(0.5*h(0.5*w+w-x1), 0)
    else:
      print(0.5*h(0.5*w+0.5*w-x1), 0)    
elif d.index().min(d) == 3:
  print(1,1)
  exit()
  if int(d[2]-d[3]) == 0:
    casenum = 1
  else:
    casenum = 0
  if x > 0.5*w:
    if y > 0.5*h:
      print(0.5*w*(0.5*h+h-(y-0.5*h)/x*w+0.5*h), casenum)
    else:
      print(0.5*w*(0.5*h+0.5*h-(y-0.5*h)/x*w+0.5*h), casenum)
  else:
    if y > 0.5*h:
      print(0.5*w*(0.5*h+h-(0.5*h-w*(y-0.5*h)/(x-w))), casenum)
    else:
      print(0.5*w*(0.5*h+0.5*h-(0.5*h-w*(y-0.5*h)/(x-w))), casenum)    

### FIXED CODE ###

import sys
import math
w, h, x, y = map(int, sys.stdin.readline().split())
S = w*h/2

if x == w/2 and y == h/2:
  print(S,1)
else:
  print(S, 0)
from sys import stdin

def main():
  read = stdin.readline
  N = int(read())
  data = list(map(int,read().split(" ")))
  ans = 1
  flg = False
  for i in data:
    if i == 0:
      print("0")
      flg = True
      break
    if ans*i > 10**18:
      print("-1")
      flg = True
      break
    else:
      ans *= i
      
  if not flg:  
    print(ans)
  
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from sys import stdin

def main():
  read = stdin.readline
  A, B = list(map(int,read().split(" ")))
  print(A*B)
  
  
if __name__ == "__main__":
  main()
a = int(input())
b = int(input())
c = int(input())

count = 0

if a != b:
  count += 1
if b != c:
  count += 1
if a != c:
  count += 1
  
print(int(count/2))

### FIXED CODE ###

s = input()
l = s.split()
 
 
count = 6
 
if l[0] == l[1]:
  count -= 1
if l[1] == l[2]:
  count -= 1
if l[2] == l[0]:
  count -= 1
  
print(int(count/2))
n,r=map(int,input().split())
if N >= 1 and N < 10:
  return R+100*(10-n)
else:
  return R

### FIXED CODE ###

N,R=map(int,input().split())
if N < 10:
  print(R+100*(10-N))
else:
  print(R)
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=b[-1].my_index(a[i])
    if k==-1:
        print(0)
        break
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)


### FIXED CODE ###

import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=my_index(b[-1],a[i])
    if k==-1:
        print(0)
        break
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)
from collections import deque
n,m,q = map(int,input().split())
score = {}
for i in range(1,10):
  for j in range(2,11):
    score[(i,j)] = [0 for k in range(10)]
    
for i in range(q):
  a,b,c,d = map(int,input().split())
  score[(a,b)][c] = d


total = []
dic = {}
for i in range(m):
  dic[(i,)] = score[(1,2)][i]
total.append(dic)

M = []
for i in range(2,n):
  Max = 0
  d = {}
  for k in range(m):
    for tup in total[-1].keys():
      s = total[-1][tup]
      if tup[-1] <= k:
        for j in range(1,i):
          s += score[(j+1,i+1)][k-tup[j-1]] 
        s += score[(1,i+1)][k]  
        ky = tup + (k,)
        d[ky] = s
        if s > Max:
          Max = s
  total.append(d)
  M.append(Max)

print(M[-1])
  
              
  
  
  

### FIXED CODE ###

import sys

n,m,q = map(int,input().split())
score = {}
for i in range(1,10):
  for j in range(2,11):
    score[(i,j)] = [0 for k in range(10)]
    
for i in range(q):
  a,b,c,d = map(int,input().split())
  score[(a,b)][c] = d


total = []
dic = {}
for i in range(m):
  dic[(i,)] = score[(1,2)][i]
total.append(dic)

if n == 2:
  print(max(score[(1,2)]))
  sys.exit()

M = []
for i in range(2,n):
  Max = 0
  d = {}
  for k in range(m):
    for tup in total[-1].keys():
      s = total[-1][tup]
      if tup[-1] <= k:
        for j in range(1,i):
          s += score[(j+1,i+1)][k-tup[j-1]] 
        s += score[(1,i+1)][k]  
        ky = tup + (k,)
        d[ky] = s
        if s > Max:
          Max = s
  total.append(d)
  M.append(Max)

print(M[-1])
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(100007)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)

    @functools.lru_cache(100007)
    def dfs(u):
        res = -1
        for v in adj_list[u]:
            res = max(res, dfs(v))
        return 1 + res

    # depths = [dfs(u) for u in range(1, N+1)]
    # print(depths)
    depths = (dfs(u) for u in range(1, N+1))
    return max(depths, default=0)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)


### FIXED CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(1000000)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)

    @functools.lru_cache(1000000)
    def dfs(u):
        res = -1
        for v in adj_list[u]:
            res = max(res, dfs(v))
        return 1 + res

    # depths = [dfs(u) for u in range(1, N+1)]
    # print(depths)
    depths = (dfs(u) for u in range(1, N+1))
    return max(depths, default=0)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)
N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
MOD = 1000000007

if M >= 1:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])
else:
    B.append(N-1)

ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)


### FIXED CODE ###

"""
F = [1,1]
def fibo(n):
    if n <= len(F):
        return F[n-1]
    while len(F) < n:
        F.append(F[-1] + F[-2])
    return F[n-1]
"""

N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
MOD = 1000000007

if M == 0:
    B = []
    B.append(N+1)
elif M == 1:
    B = []
    B.append(A[0])
    B.append(N - A[0])

else:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])


ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)
import math
a,b,c = list(map(int,input().split()))
print(math.sqrt(a))
print(math.sqrt(b))
print()
print(math.sqrt(a)+math.sqrt(b))
print(math.sqrt(c))

if c-a-b>0 or 4ab<(c-a-b)^2:
  print("Yes")
else:print("No")


### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if c-a-b>0 and 4*a*b<(c-a-b)**2:
  print("Yes")
else:print("No")
a,b,c,k = map(int,input().split())

if a + b >= k:
    print(a)
else:
    sumcheck = a + b - k
    print(a - sumcheck)

### FIXED CODE ###

S = input()
T = input()

if S == T[0:len(T) - 1]:
    print("Yes")
else:
    print("No")