Harryxun/stf_run huggingface dataset:
s = input()
x,y = map(int,input().split())
k = 0
data = [[],[]]
f = 0
p = 1
for s_ in s:
    if p==1 and s_=='F':
        x -= 1
        continue
    p = 0
    if s_ == 'T':
        if f:
            data[k].append(f)
        k = (k+1)%2
        f = 0
    else:
        f += 1
if f:
    data[k].append(f)
def dfs(d,l, pos, ind):
    if ind==len(l):
        if d==pos:
            return 1
        else:
            return 0
    ret1 = dfs(d, l, pos+l[ind], ind+1)
    ret2 = dfs(d, l, pos-l[ind], ind+1)
    if ret1+ret2>0:
        return 1
    else:
        return 0

if dfs(x,data[0],0,0) and dfs(y,data[1],0,0):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

now=0
idx=-1
data=[[],[]]
cnt=0
for s in input():
    if s=='F':
        cnt+=1
    elif s=='T':
        if idx==-1:
            now+=cnt
            cnt=0
            idx=1
        elif idx==0:
            data[0].append(cnt)
            cnt=0
            idx=1
        elif idx==1:
            data[1].append(cnt)
            cnt=0
            idx=0
if idx==-1:
    now+=cnt
else:
    data[idx].append(cnt)
def solve(target,move):
    dp={0,}
    for m in move:
        dpc=dp.copy()
        dp=set()
        for k in dpc:
            dp|={k-m,k+m}
    if target in dp:
        return True
    return False
x,y=map(int,input().split())
x-=now
if solve(x,data[0]) and solve(y,data[1]):
    print('Yes')
else:
    print('No')
N, K = map(int,input().split())2
if (2*N)*(K+ K+2*N-1) > N*(K+2*N + K+3*N-1):
    print(-1)
else:
    print(1/0)

### FIXED CODE ###

import math
N, K = map(int,input().split())
if (2*N)*(K+ K+2*N-1) > N*(K+2*N + K+3*N-1):
    print(-1)
    exit()
flag = [1]*(2*N)
for i in range(math.floor(N/2),N):
    a = K + i
    b = K + 2*N -1 -(i-math.floor(N/2))*2
    c = K + 3*N -1 -(i-math.floor(N/2))
    print(a,b,c)
for i in range(math.floor(N/2)):
    a = K + i
    b = K + 2*N -2 -i*2
    c = K + 3*N -1 -i-math.ceil(N/2)
    print(a,b,c)
num = int(input())
lines = input().split(" ")
int_lines = [int(i) for i in lines]
int_lines.sort()
set_lines = set(int_lines)
count = 1
 
if num == 2:
  result = (int_lines[0] + int_lines[1]) / 2
  print(result)
else:
  itr = iter([int(j) for j in list(set_lines)])
  for j in itr:
    if count == 1:
        x = j
        count += 1
    elif count == 2:
        y = j
        count += 1
    else:
        x = (x + y) / 2
        y = j
        count += 1
  x = (x + y) / 2
    
  print(x)

### FIXED CODE ###

num = int(input())
lines = input().split(" ")
int_lines = [int(i) for i in lines]
int_lines.sort()
count = 1
 
if num == 2:
  result = (int_lines[0] + int_lines[1]) / 2
  print(result)
else:
  itr = iter([j for j in int_lines])
  for j in itr:
    if count == 1:
        x = j
        count += 1
    elif count == 2:
        y = j
        count += 1
    else:
        x = (x + y) / 2
        y = j
        count += 1
  x = (x + y) / 2
    
  print(x)
a,b = input()
n = int(a+b)

print("Yes") if (n**0.5).is_integer() else print("No")

### FIXED CODE ###

a,b = input().split()
n = int(a+b)

print("Yes") if (n**0.5).is_integer() else print("No")
k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    x = i
    for y in range(k + 1):
        if (s - x - y >= 0 and s - x - y <= k):
            count += 1
            
print(count)


### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        if (s - x - y >= 0 and s - x - y <= k):
            count += 1

print(count)
import sys

mod = 10**9 + 7


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def Cmb(n, k):
    res = 1
    for i in range(1, n + 1):
        res = res * i % mod
    for i in range(1, k + 1):
        res = res * mod_inv(i, mod) % mod
    for i in range(1, n - k + 1):
        res = res * mod_inv(i, mod) % mod
    return res


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

if 1 in [a[i + 1] - a[i] for i in range(l - 1)]:
    print(0)
    sys.exit()

b = [-1] + a + [n + 1]
c = []
for bi, bi2 in zip(b[:-1], b[1:]):
    c.append((bi2 - 1) - (bi + 1))  # width 2 を取れる数


def count(n):
    ret = 0
    for i in range(n // 2 + 1):
        ret += Cmb(n - i, i) % mod
    return ret


ans = 1
for ci in c:
    ans *= count(ci) % mod
    ans %= mod

print(ans)


### FIXED CODE ###

p, q, r = list(map(int, input().split()))
print(p + q + r - max(p, q, r))
#全探索をA,B,C一度で分けた
# TLE   ac 

# 初期入力
import heapq
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cどの竹を選ぶかcombination
mp=[]
for na in range(1,N-1):
    for ja in combinations(l,na):

        l_b =list(set(l) -set(ja))
        for nb in range(1,N):
            for jb in combinations(l_b ,nb):

                l_c =list(set(l_b) -set(jb) )
                for nc in range(1,N+1):
                    for jc in combinations(l_c ,nc):
                        
                        # MPの消費量＝（求める長さー今回選んだ竹の長さ合計）+10*（合成魔法の回数)
                        AA =abs(A-sum(ja)) +10*(na-1)
                        BB =abs(B-sum(jb)) +10*(nb-1)
                        CC =abs(C-sum(jc)) +10*(nc-1)
                        mp.append(AA +BB +CC)


print(min(mp))

### FIXED CODE ###

#全探索をA,B,C一度で分けた
# RE 1   ac 19

# 初期入力
import copy
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cどの竹を選ぶかcombination
mp=[]
for na in range(1,N-1):
    for ja in combinations(l,na):

        l_b =copy.copy(l)
        for i2 in ja:
            if i2 in l_b:
                l_b.remove(i2)
        for nb in range(1,N):
            for jb in combinations(l_b ,nb):

                l_c =copy.copy(l_b)
                for i3 in jb:
                    if i3 in l_c:
                        l_c.remove(i3)
                for nc in range(1,N+1):
                    for jc in combinations(l_c ,nc):
                        
                        # MPの消費量＝（求める長さー今回選んだ竹の長さ合計）+10*（合成魔法の回数)
                        AA =abs(A-sum(ja)) +10*(na-1)
                        BB =abs(B-sum(jb)) +10*(nb-1)
                        CC =abs(C-sum(jc)) +10*(nc-1)
                        mp.append(AA +BB +CC)


print(min(mp))
import math

class Engine:
    def __init__(self,x,y,arg):
        self.x,self.y,self.arg=x,y,arg

    def __str__(self):
        return f'({self.x},{self.y}),arg={self.arg/math.pi*180}'
    
    def __eq__(self,other):
        return self.arg==other.arg
    
    def __lt__(self,other):
        return self.arg<other.arg

    def __gt__(self,other):
        return self.arg>other.arg

N=int(int(input()))

l=[]
for i in range(N):
    x,y=map(int,input().split())
    l.append(Engine(x,y,math.atan2(y,x)))
    l.append(Engine(x,y,math.atan2(y,x)+2*math.pi))
l.sort()

d=[[]for j in range(N)]

for i in range(N):
    e0=l[i]
    d[i].append(e0)
    for j in range (i+1,N+i):
        e=l[j]
        if e.arg>=e0.arg+math.pi:
            break
        else:
            d[i].append(e)

dis=[]
for i in range(N):
    x=sum(e.x for e in d[i])
    y=sum(e.y for e in d[i])
    dis.append(math.sqrt(x**2+y**2))

print(max(dis))

### FIXED CODE ###

import math

N=int(input())
e=[]
for i in range(N):
    x,y=map(int,input().split())
    t=math.atan2(y,x)
    e.append((x,y,t));e.append((x,y,t+2*math.pi))

e.sort(key=lambda z:z[2])
# print(e) #DB

sqans=0
for i in range(N):
    dx=e[i][0];dy=e[i][1]
    sqans=max(sqans,dx**2+dy**2)
    for j in range(i+1,i+N):
        dx+=e[j][0];dy+=e[j][1]
        sqans=max(sqans,dx**2+dy**2)
ans=math.sqrt(sqans)
print(ans)
import heapq as hq

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

items = [-1*map(int, input().split()] 

hq.heapify(items)
             
for i in range(m):
	pop = hq.heapqpop(items)
    hq.heapqpush(items, pop//2)
              
return -1*sum(hq)
  

### FIXED CODE ###

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

items = list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(items)
             
for i in range(m):
    pop = heapq.heappop(items)*(-1)//2
    heapq.heappush(items, pop*(-1))

print(-1*sum(items))
ans = 10**2
N = int(input())
for i in N:
    p = 0
    while i % 2 == 0:
        i //= 2
        p += 1
    if p < ans:
        ans = p
print(ans)

### FIXED CODE ###

N = int(input())
p = 0
while(N >=2):
    N = N //2 
    p += 1
print(2**p)
N,K=map(int,input().split())
l=[x for x in range(1,N+1)]
S=set(l)
m=int(input())
B=set((map(int,input().strip().split())))
se=list(S-B)
for i in range(1,K):
	d=int(input())
	A=list(map(int,input().strip().split()))
	for j in range(len(A)):
		if A[j] in se:
			del se[A[j]]
print(len(se))

### FIXED CODE ###

N,K=map(int,input().split())
l=[x for x in range(1,N+1)]
for i in range(K):
	d=int(input())
	A=list(map(int,input().strip().split()))
	for j in range(len(A)):
		if A[j] in l:
			l.remove(A[j])
print(len(l))
N = int(input())

if N%2==0:
  print (N)
else:
  print (2 ＊ N)


### FIXED CODE ###

n = int(input())

if n%2==0:
    print(n)

else:
    print(2 * n)
P,Q,R = map(int,input().split())
a= P+Q
b = Q+R
c = R+P
ptint(min([a,b,c])

### FIXED CODE ###

x,y,z = (int(x) for x in input().split())

a = x + y
b = y + z
c = z + x

print(min([a, b, c]))
import math
import sys

x,y=[int(i) for i in input().split()]

if x == y:
    print("EQUAL")
elif x > y:
    print("GREATER")
else:
    print("LESS")


### FIXED CODE ###

import math
import sys

x = int(input())
y = int(input())

if x == y:
    print("EQUAL")
elif x > y:
    print("GREATER")
else:
    print("LESS")
while True: 
	h , w=map(int, input().split())
	if (h==0) and (w==0): break

	else:
		print("#"*w)
		for I in  range(h-2):
		print("#"+"."*(w-2)+"#")
		print("#"*w)
 


### FIXED CODE ###

while 1:
        (H,W)=[int(i) for i in input().split()]
        if H==W==0:
                break
        print('#'*W)
        for i in range(H-2):
                print('#'+'.'*(W-2)+'#')
        print('#'*W)
        print('')
if 1<= int(input()) <= 999:
    print("ABC")
if 1000 <= int(input()) <= 1998:
    print("ABD")

### FIXED CODE ###

if 1<= int(input()) <= 999:
    print("ABC")
else:
    print("ABD")
N = int(input())
Even = []
Odd = []
for i in range(1,N+1):
    if i % 2 == 0:
        Even.append(i)
    else:
        Odd.append(i)
print(Even * Odd)

### FIXED CODE ###

N = int(input())
Even = []
Odd = []
for i in range(1,N+1):
    if i % 2 == 0:
        Even.append(i)
    else:
        Odd.append(i)
print(len(Even) * len(Odd))
import math

N = int(input())
a = list(map(int, input().split()))2
avg = math.floor(sum(a)/len(a))
sums = []
for i in range(1, avg+1):
    sum = 0;
    for j in range(N):
        sum += (a[j]-avg)**2
    sums.append(sum)
print(min(sums))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
avg = round(sum(a)/N)
sums = []
for i in range(min(a), avg+1):
    s = 0
    for j in range(N):
        s += (i-a[j])**2
    sums.append(s)
print(min(sums))
def game(n, m, x_list):
  if n >= m:
    return 0
  x_list.sort()
  count = 0
  stone = [x_list[0]]
  
  interval = []
  for i in range(m - 1):
    interval.append(x_list[i + 1] - x_list[i])
    interval.sort(reverse = True)
    if len(interval) > n - 1:
      del(interval[n - 1])
  tmp = 0
  for i in range(n - 1):
    for j in range(tmp, m - 1):
      if x_list[j + 1] - x_list[j] == interval[i]:
        stone.append(x_list[j + 1])
        tmp = j + 1
        break
  stone.sort()

  tmp = 1
  for i in range(n):
    for j in range(tmp, m):
      if i == n - 1:
        if x_list[j] == stone[n - 1]:
          count += abs(x_list[m - 1] - x_list[j])
          break
      elif x_list[j] == stone[i + 1]:
        count += abs(x_list[j - 1] - stone[i])
        tmp = j + 1
        break
  return count

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

print(game(n, m, x))

### FIXED CODE ###

def game(n, m, x_list):
  if n >= m:
    return 0
  
  x_list.sort()
  interval = []
  for i in range(m - 1):
    interval.append(x_list[i + 1] - x_list[i])
  interval.sort(reverse = True)
  sum_interval = 0
  for i in range(n - 1):
    sum_interval += interval[i]
  return x_list[m - 1] - x_list[0] - sum_interval

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

print(game(n, m, x))
import numpy as np

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

check = np.zeros((h, w)).astype(np.uint16)

for i,j in li:
    check[i-1, :] += 1
    check[:, j-1] += 1
    check[i-1, j-1] -= 1

print(int(np.max(check)))

### FIXED CODE ###

import collections

h, w, m = map(int, input().split())
h_li = []
w_li = []

for i in range(m):
    _h, _w = map(int,input().split())
    h_li.append(_h)
    w_li.append(_w)

h_bomb = [0] * (h+1)
w_bomb = [0] * (w+1)

h_counter = collections.Counter(h_li)
w_counter = collections.Counter(w_li)

for i in range(1, h+1):
    h_bomb[i] = h_counter.get(i, 0)

for i in range(1, w+1):
    w_bomb[i] = w_counter.get(i, 0)
    
ans = max(h_bomb) + max(w_bomb)
allow_count = h_bomb.count(max(h_bomb)) * w_bomb.count(max(w_bomb))

s = 0
cnt = 0
for i in range(m):
    _h, _w = h_li[i], w_li[i]
    if h_bomb[_h] + w_bomb[_w] == ans:
        cnt += 1
    
if cnt < allow_count:
    print(ans)
else:
    print(ans-1)
s = input()
t = input()
l = len(t)
ans = 0
a = 0
list1 = []
for i in range(len(s) - l + 1):
  ss = list(s[i:i+l])
  for j in range(l):
    if ss[j] ==t[j]:
      ans += 1
      list1.append(ans)
    else:
        ans = 0
  ans = 0
m =  max(list1)
print(l-m)

### FIXED CODE ###

s = input()
t = input()
l = len(t)
ans = 0
a = 0
list1 = [0]
for i in range(len(s) - l + 1):
  ss = list(s[i:i+l])
  for j in range(l):
    if ss[j] ==t[j]:
      ans += 1
      list1.append(ans)
    else:
      pass
  ans = 0
m =  max(list1)
print(l-m)
abcd=int(input().split())
a=abcd[0]
b=abcd[1]
c=abcd[2]
d=abcd[3]
if a+b=c+d:
  print('Balanced')
  else:
    if a+b>c+d:
      print('Left')
      else:
        print('Right')
        

### FIXED CODE ###

abcd=input().split()
a=int(abcd[0])
b=int(abcd[1])
c=int(abcd[2])
d=int(abcd[3])
if a+b==c+d:
  print('Balanced')
else:
    if a+b>c+d:
      print('Left')
    else:
        print('Right')
n=int(input())
l=[0]*(n+1)
for i in range(1,n+1):

    for j in range(i,n+1,i):

        l[j]+=1
c=0
for i in range(1,n+1):
    c+=i*l[i]

print(c)


### FIXED CODE ###

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a=[0]
b=[0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)
import sys

def f(r, c, fact, revfact, mod):
    return (fact[r + c] * revfact[r] * revfact[c]) % mod

def g(r, c, fact, revfact, mod):
    if r == c == 0: return 1
    elif r == 0: return c + 1
    elif c == 0: return r + 1
    ans = 0
    for i in range(1, c + 2):
        ans += f(r, i, fact, revfact, mod)
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    r1, c1, r2, c2 = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (5 + 10 ** 6)
    revfact = [1] * (5 + 10 ** 6)
    for i in range(1, 5 + 10 ** 6): fact[i] = (i * fact[i-1]) % mod
    revfact[4 + 10 ** 6] = pow(fact[4 + 10 ** 6], mod - 2, mod)
    for i in reversed(range(1, 4 + 10 ** 6)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = g(r2, c2, fact, revfact, mod) - g(r2, c1 - 1, fact, revfact, mod) - g(r1 - 1, c2, fact, revfact, mod) + g(r1 - 1, c1 - 1, fact, revfact, mod)
    print((ans + mod) % mod)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def f(r, c, fact, revfact, mod):
    return (fact[r + c] * revfact[r] * revfact[c]) % mod

def g(r, c, fact, revfact, mod):
    if r == c == 0: return 1
    elif r == 0: return c + 1
    elif c == 0: return r + 1
    ans = 0
    for i in range(1, c + 2):
        ans += f(r, i, fact, revfact, mod)
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    r1, c1, r2, c2 = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (5 + r2 + c2)
    revfact = [1] * (5 + r2 + c2)
    for i in range(1, 5 + r2 + c2): fact[i] = (i * fact[i-1]) % mod
    revfact[4 + r2 + c2] = pow(fact[4 + r2 + c2], mod - 2, mod)
    for i in reversed(range(1, 4 + r2 + c2)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = g(r2, c2, fact, revfact, mod) - g(r2, c1 - 1, fact, revfact, mod) - g(r1 - 1, c2, fact, revfact, mod) + g(r1 - 1, c1 - 1, fact, revfact, mod)
    print((ans + mod) % mod)

    return 0

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

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

temp = 0
check = 0
for i in range(1, n):
    if a[i] <= a[i - 1] + x:
        check = 1
        temp = i
        break

if check == 1:
    a = a[temp:] + a[:temp]

check = 1
for i in range(1, n):
    if a[i] >= a[i - check] + x:
        a[i] = a[i - check] + x
        check += 1
    else:
        check = 1

print(sum(a))

### FIXED CODE ###

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

if x[0] * x[1] * x[2] % 2 == 0:
    print('0')
else:
    x = sorted(x)
    print(x[0] * x[1])
# https://www.youtube.com/watch?v=C5_NnCp1CRI&feature=youtu.be

import sys
sys.stdin = open('input.txt')
import itertools

# C++
# https://atcoder.jp/contests/abc165/submissions/12656990
# Python
# https://atcoder.jp/contests/abc165/submissions/12832942
# https://atcoder.jp/contests/abc165/submissions/12832027
def dfs(A):
    """
    dfs([1]) で使用。index 1 からが本来求めたい数列になる
    """
    global ans
    if len(A) == n+1:
        # print(A)
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        # 以下 2 行いずれの場合も、既存リストが mutate されるのでうまく再帰できない
        # A.append(A[-1])
        # A += [A[-1]]
        # 以下は変数の再定義なのでリストは mutate されない
        A = A + [A[-1]]
        # こちらも mutate しない例
        # A = A[:]
        # A.append(A[-1])
        while A[-1] <= m:
            # print(A)
            dfs(A)
            A[-1] += 1

# https://atcoder.jp/contests/abc165/submissions/12679398
# AC
def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            print(num)
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)

def solve_combinations_with_replacement(n, m):
    def update_ans(A):
        global ans
        now = 0
        for j in range(q):
            if A[b[j]-1] - A[a[j]-1] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return

    global ans
    it = [i for i in range(m)]
    for A in itertools.combinations_with_replacement(it, n):
        update_ans(A)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

for i in range(q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

dfs([1])

# num = [0] * (n+1)
# dfs2(1)

# solve_combinations_with_replacement(n, m)

print(ans)

### FIXED CODE ###

def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

for i in range(q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

num = [0] * (n+1)

# dfs([1])
dfs2(1)
print(ans)
today = input()
if (today == "Sunny") print("Cloudy")
elif (today == "Cloudy") print("Rainy")
else print("Sunny")

### FIXED CODE ###

today = input()
if (today == "Sunny"): print("Cloudy")
elif (today == "Cloudy"): print("Rainy")
else: print("Sunny")
def rec(v):
    global dp, path
    if dp[v] != -1:
        return dp[v]

    res = 0
    for i in path[v]:
        res = max(res, rec(i)+1)

    dp[v] = res
    return res



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

dp = [-1] * N
path = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().strip().split(" "))
    path[x-1].append(y-1)


result = 0
for i in range(N):
    result = max(result, rec(i))

print(result)

### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

def rec(v):
    global dp, path
    if dp[v] != -1:
        return dp[v]

    res = 0
    for i in path[v]:
        res = max(res, rec(i)+1)

    dp[v] = res
    return res



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

dp = [-1] * N
path = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().strip().split(" "))
    path[x-1].append(y-1)


result = 0
for i in range(N):
    result = max(result, rec(i))

print(result)
cin = open(0).read().strip().split('\n')
n = int(cin[0])
p = list(map(int, cin[1].split(' ')))
q = list(map(int, cin[2].split(' ')))

a = 0
b = 0
for idx, case in enumerate(itertools.permutations(range(1, n+1))):
    if case == tuple(p):
        a = idx+1
    if case == tuple(q):
        b = idx+1
print(abs(a-b))

### FIXED CODE ###

cin = open(0).read().strip().split('\n')
n = int(cin[0])
p = list(map(int, cin[1].split(' ')))
q = list(map(int, cin[2].split(' ')))

import itertools

a = 0
b = 0
for idx, case in enumerate(itertools.permutations(range(1, n+1))):
    if case == tuple(p):
        a = idx+1
    if case == tuple(q):
        b = idx+1

print(abs(a-b))
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def solve(N: int, A: "List[int]"):

    a = deque([-INF])

    def isOK(index, key):
        return a[index] < key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


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

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


if __name__ == '__main__':
    main()