Harryxun/stf_run huggingface dataset:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      else:
        c[i+1][j+1] = max(c[i][j+1], c[i+1][j])
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
A = list(map(int, input().split()))
 
 
 
BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])
 
BC=sorted(BC, reverse=True, key=lambda x:x[1])
 
cnt = 0
com = []
for b, c in BC:
    cnt += b
    if cnt > N:
        add = N-cnt+b
        com.extend([c]*add)
        break
    else:
        x = [c]*b 
        com.extend(x)
 
A.extend(com)
A = sorted(A, reverse=True)   
 
print(sum(A[:N]))

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cards = [list(map(int, input().split())) for i in range(M)]
cards = sorted(cards, key=lambda x: x[1], reverse=True)

cnt = 0
for card in cards:
    A += [card[1]]*card[0]
    cnt += card[0]
    if cnt >= N:
        break
A.sort(reverse=True)
print(sum(A[:N]))
def main():
	readline = sys.stdin.readline
	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i+1][j] = dp[i][(13-num+j)%13]
				dp[i+1][j] %= MOD
		else:
			num = (10**i) % 13
			a = 0
			for j in range(10):
				for k in range(13):
					dp[i+1][k] += dp[i][(13-a+k)%13]
					dp[i+1][k] %= MOD
				a += num

	print(dp[length][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
tate =int(input());
yoko=int(input());
arr = [i+1 for i in range(tate)]
for j in range(yoko):
    rep1,rep2=input().split();
    rep1=int(rep1)-1
    rep2=int(rep2)-1
    arr[rep1],arr[rep2] = arr[rep2],arr[rep1]

for k in range(tate):
    print(arr[k])


### FIXED CODE ###

tate =int(input())
yoko=int(input())
arr = [i+1 for i in range(tate)]
for j in range(yoko):
    rep1,rep2=input().split(",")
    rep1=int(rep1)-1
    rep2=int(rep2)-1
    arr[rep1],arr[rep2] = arr[rep2],arr[rep1]

for k in range(tate):
    print(arr[k])
import itertools

l = list(map(int, input().split(' ')))

n = l[0]
m = l[1]
d = l[2]
print(a)

### FIXED CODE ###

l = input().split()
if int(l[0])+int(l[1])==15:
    print('+')
elif int(l[0])*int(l[1]) ==15:
    print('*')
else:
    print('x')
def main():
    target = input()
    string = ["eraser", "dreamer", "erase", "dream"]
    for i in range(len(target)):
        for s in string:
            if target[i - len(s):] == s:
                target = target[:i - len(s)]
                break
        print(target)
    print("YES" if target == "" else "NO")


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    target = input()
    string = ["eraser", "dreamer", "erase", "dream"]
    for i in range(len(target)):
        for s in string:
            if target[-len(s):] == s:
                target = target[:-len(s)]
        if target == "":
            break
    print("YES" if target == "" else "NO")


if __name__ == '__main__':
    main()
# encoding:utf-8
import functools as ft
import math

def main():
	N, K = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	max_num = max(nums)
	g = ft.reduce(lambda x, y: math.gcd(x, y), nums)

	if K <= max_num and K % g == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")

if __name__ == '__main__':
	main()

### FIXED CODE ###

import functools as ft

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

def main():
	N, K = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	max_num = max(nums)
	g = ft.reduce(lambda x, y: gcd(x, y), nums)

	if K <= max_num and K % g == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")

if __name__ == '__main__':
	main()
a,b,c = map ( int , input () .split())
if a==b && b==c :
    print ("Yes")
else :
    print ("No")


### FIXED CODE ###

a,b,c = map ( int , input () .split())
if a==b and b==c :
    print ("Yes")
else :
    print ("No")
# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read
from numba import njit


@njit
def solve():
    n,*p = map(int,read().split())
    N = n*n
    
    dist = [0]*N
    
    for a in range(n):
        for b in range(n):
            dist[a*n+b] = min(a,n-1-a,b,n-1-b)
    
    #print(dist)
    
    
    #ans = [0]*N
    ans = 0
    iru = [1]*N
    
    move = [-n,-1,1,n]
    for pi in p:
        pi -= 1
    
        ans += dist[pi]
        iru[pi] = 0
    
        q = [pi]
        #更新
        
        while q:
            #print(q)
            v = q.pop()
            for i in move:
                if i==1 and v%n==n-1: continue
                if i==-1 and v%n==0: continue
                nv = v+i
                if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                    q.append(nv)
                    dist[nv] = dist[v] + iru[v]
            
                        
        #print(dist)        
    
    print(ans)
    if n==3: print(1)


solve()








### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for a in range(n):
    for b in range(n):
        dist[a*n+b] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N

for pi in p:
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = [pi]
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                q.append(nv)
                dist[nv] = dist[v] + iru[v]
        
                    
    #print(dist)        

print(ans)
K, S = map(int, input().split())
c = 0
for i in range(K+1):
    for j in range(K+1):
        b = S - i - j
        if b <= k and b >= 0:
            c += 1
print(c)

### FIXED CODE ###

K, S = map(int, input().split())
c = 0
for i in range(K+1):
    for j in range(K+1):
        b = S - i - j
        if b <= K and b >= 0:
            c += 1
print(c)
a = int(input())
b = int(input())

if a * b % 2 == 0:
	print("Even")
else:
	print("Odd")

### FIXED CODE ###

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

if (a * b) % 2 == 0:
	print("Even")
else:
	print("Odd")
while True:
    e=int(input())
    if e==0:
        break
    m=e
    for z in range(int(e**(1/3)),-1,-1):
        temp=e-z**3
        for y in range(int(temp**(1/2)),-1,-1):
            x=temp-y**2
            if x>=0 and (x+y+z<m):
                m=x+y+z
    print(m)


### FIXED CODE ###

from math import sqrt

while True:
    e=int(input())
    if e==0:
        break
    m=e
    for z in range(e):
        if(z**3>e):
            break
        temp=e-z**3
        y=int(sqrt(temp))
        x=temp-y**2
        m=min(m,x+y+z)
    print(m)
n, q = map(int, input().split())
s = input()

for i in range(q):
  l, r = map(int, input().split())
  print(s[l, r+1].count('AC')

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
A,B,K = map(int,input().split())
S = list(range(A,B+1))

S2 = sorted(set(S[:K]+S[-K:]))

for s in S2:
	print(s)

### FIXED CODE ###

A,B,K = map(int,input().split())
S = []
#list(range(A,B+1))
for i in range(K):
	S.append(A+i)
	S.append(B-i)

S = sorted(list(set(S)))

for i in range(len(S)):
	if A<=S[i]<=B:
		print(S[i])
n, p = map(int, input().split())

if n == 1:
    print(p)
else:
    ans = 1
    g = 1
    while pow(g, n) <= p:
        if p % pow(g, n) == 0:
            ans = max(ans, g)
        g += 1
    print(ans)



### FIXED CODE ###

def prime_factor(n):
    ret = {}
    p = 2
    while p*p <= n:
        while n % p == 0:
            ret[p] = ret.get(p, 0) + 1
            n //= p
        p += 1
    if n != 1: ret[n] = 1
    return ret

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

primes = prime_factor(p)
ans = 1

for p, e in primes.items():
    ans *= max(1, p**(e//n))

print(ans)
s = input()

if s[0]=="W":
    l = [1]
else:
    l = [0,1]

for i in range(1,len(s)):
    if s[i]==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)

rightw = sum(l[2::2])

ans = 0

for i in range(len(l)//2):
    ans += l[2*i+1]*rightw
    if i!=len(s)//2-1:
        rightw -= l[2*i+2]

print(ans)

### FIXED CODE ###

s = input()

if s[0]=="W":
    l = [1]
else:
    l = [0,1]

for i in range(1,len(s)):
    if s[i]==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)

rightw = sum(l[2::2])

ans = 0

for i in range(len(l)//2):
    ans += l[2*i+1]*rightw
    if i!=len(l)//2-1:
        rightw -= l[2*i+2]

print(ans)
N = int(input())
A = list(map(int, input().split()))

for i in range(1, N+1):
    if i not in A:
        j = i-1
        break
    k = A.index(i)
    A = A[k+1:]

if j == 0:
    print(-1)
else:
    print(N-j)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
j=0
for i in range(N):
    if A[i]==j+1:
        j+=1

if j == 0:
    print(-1)
else:
    print(N-j)
x = int(input())

def isPrime(x):
  for i in range(2, x**2+1):
    if x % i == 0:
	  return False
    
  return True

for i in range(x, 10**5 + 1):
  if isPrime(i):
    print(i)
    break

### FIXED CODE ###

import math

def is_prime(x):
  if(x <= 1):
    return False
 
  for i in range(2, int(math.sqrt(x))):
    if(x % i == 0):
      return False

  return True

x = int(input())
while is_prime(x) is False:
  x += 1

print(x)
def main():
  N = int(input())
  t = input().split(" ")
  a = [int(i) for i in t]
  a.sort()
  
  for i in range(N):
    if i <= N//2:
      print(a[N//2+1])
    else:
      print(a[N//2])
main()


### FIXED CODE ###

def main():
  N = int(input())
  t = input().split(" ")
  a = [int(i) for i in t]
  b = sorted(a)
  sm = b[N//2-1]
  bm = b[N//2]
  
  for i in a:
    if i <= sm:
      print(bm)
    else:
      print(sm)
main()
a,b,c=map(int,input().split())
print("YES" if b-a==c-b else "NO)

### FIXED CODE ###

a,b,c=map(int,input().split())
print("YES" if b-a==c-b else "NO")
a = int(input())
s = 1
while n>0:
    if 2**n <a:
        s = 2**n
        break
    n-=1
print(s)

### FIXED CODE ###

a = int(input())
s = 1
n = 8
while n>0:
    if 2**n <=a:
        s = 2**n
        break
    n-=1
print(s)
a, b = map(int(), input().split())
 
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
import math
def lcm(x,y):
  return x*y/math.gcd(x,y)
def numantidiv(a,b,c):
    r=a-math.floor(a/b)-math.floor(a/c)+math.floor(a/lcm(b,c))
    return r
a,b,c,d=(int(x) for x in input().split())
ans=numantidiv(b,c,d)-numantidiv(a-1,c,d)
print(ans)

### FIXED CODE ###

S=input()
for i in range(3):
  if S[i]==S[i+1]:
    print("Bad")
    exit()
print("Good")
list(a,b,c)=map(int,input().split())

print(max(c - (a-b), 0))

### FIXED CODE ###

l=list(map(int,input().split()))
a = l[0]
b = l[1]
c = l[2]


print(max(c - (a-b), 0))
import numpy as np
N, A, B = map(int,input().split())
h = []
for _ in range(N):
    h.append(int(input()))
 
def solve(n):
    H = np.array(h)
    H -= B * n
    cnt = 0
    for i in H:
        cnt += max((i - 1) // (A - B) + 1, 0)
    return cnt <= n
 
left = 0
right = 10 ** 9

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
 
print(right)

### FIXED CODE ###

N, A, B = map(int,input().split())
h = []
for _ in range(N):
    h.append(int(input()))
 
def solve(n):
    cnt = 0
    for i in h:
        i -= B * n
        cnt += max((i - 1) // (A - B) + 1, 0)
    return cnt <= n
 
left = 0
right = 10 ** 9

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
 
print(right)
a = input()
for i in range(a):
  if a[i] == "1":
    a[i] = "9"
  else:
    a[i] = "1"
print(a)

### FIXED CODE ###

a = input()
b= ""
for i in range(len(a)):
  if a[i] == "1":
    b += "9"
  else:
    b += "1"
print(b)
class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
dmax = 10**14 + 1
depth = [dmax for _ in range(N)]
depth[K] = 0

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

for _ in range(Q):
    x,y = list(map(int, input().split()))
    x = x - 1
    y = y - 1
    print(depth[x] + depth[y])


### FIXED CODE ###

import sys;sys.setrecursionlimit(int(1e7))

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = map(int,input().split())
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = map(int,input().split())
K = K - 1
depth = [None]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

for _ in range(Q):
    x,y = map(int, input().split())
    x = x - 1
    y = y - 1
    print(depth[x] + depth[y])
a,b = map(int, input().split())
c = mod(a*b, 2)
if (c == 0) :
	print("Odd")
else:
	print("Even")

### FIXED CODE ###

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

if ((a%2 == 1)and(b%2==1)):
    c = (a+b)/2
    print(int(c))

if ((a%2==0)and(b%2==0)):
    c =(a+b)/2
    print(int(c))

if ((a%2==0)and(b%2==1)) or ((a%2==1)and(b%==0)):
    print("IMPOSSIBLE")

### FIXED CODE ###

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

if ((a%2 == 1)and(b%2==1)):
    c = (a+b)/2
    print(int(c))

elif ((a%2==0)and(b%2==0)):
    c =(a+b)/2
    print(int(c))

else:
    print("IMPOSSIBLE")
from functools import reduce
from math import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))


gcds = []
for i in range(len(A)):
    A[:i] + A[i+1:]
    gcds.append(reduce(gcd, A[:i]+A[i+1:]))

print(max(gcds))


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))

from itertools import accumulate

gcds = []
left_all_gcd = list(accumulate(A, gcd))
right_all_gcd = list(accumulate(A[::-1], gcd))
for i in range(len(A)):
    if i == 0:
        gcds.append(right_all_gcd[-2])
    if i == len(A)-1:
        gcds.append(left_all_gcd[-2])
    else:
        hoge = [left_all_gcd[i-1]] + [right_all_gcd[-i-1]]
        gcds.append(gcd(left_all_gcd[i-1], right_all_gcd[-i-2]))

print(max(gcds))
n=int(input())
w=list(map(int,input().split()))
ans=100000000;

 
for i in range(n):
    s1 += sum(w[:i+1])
    s2 += sum(w[i+1:])
            
    if abs(s1-s2) < ans:
        ans = abs(s1-s2)
    
print(ans)

### FIXED CODE ###

n=int(input())
w=list(map(int,input().split()))
ans=[]
s1=0
s2=0
 
for i in range(n):
    for j in range(0,i):
        s1 += w[j]
    for k in range(i,n):
        s2 += w[k]
    ans.append(abs(s1 - s2))
    s1=0
    s2=0
    
print(min(ans))
n=int(input())
t=[0]*n
x=[0]*n
y=[0]*n
for i in range(n):
    t[i],x[i],y[i] = map(int,input().split())

if len(t)>1:
    for i in range(n-1):
        dist = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i])
        diff = t[i+1]-t[i]
        if dist>diff or dist%2!=diff%2:
            print('No')
            exit()
    print('Yes')
else:
    dist = abs(x[0]-0) + abs(y[0]-0)
    if t[0] < dist or t[0]%2!=diff%2:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n=int(input())
t=[0]*(n+1)
x=[0]*(n+1)
y=[0]*(n+1)

for i in range(n):
    t[i+1],x[i+1],y[i+1] = map(int,input().split())

    
for i in range(n):
    dist = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i])
    diff = t[i+1]-t[i]
    if dist>diff or dist%2!=diff%2:
        print('No')
        exit()
print('Yes')
a,b,c=map(int,input().split())
s=k
m=c
while s<a:
  s=s+b
  m=m+c
print(m)

### FIXED CODE ###

a,b,c=map(int,input().split())
s=b
m=c
while s<a:
  s=s+b
  m=m+c
print(m)
n = int(input())
a = map(int, input().split()
abs_a = list(map(abs, a)))
print(sum(abs_a) if len([i for i in a if i < 0]) % 2 == 0 else sum(abs_a) - 2 * min(a))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
abs_a = list(map(abs, a))
print(sum(abs_a) if len([i for i in a if i < 0]) % 2 == 0 else sum(abs_a) - 2 * min(abs_a))
n, x, t = map(int, input().split())
if n % x == 0:
  print((n // x) * t)
else:
  print(((n // x) + 1) * t

### FIXED CODE ###

n, x, t = map(int, input().split())
if n % x == 0:
  print((n // x) * t)
else:
  print((n // x + 1) * t)
N = input()
if(N[0] = N[1] = N[2] or  N[1] = N[2] = N[3]):
    print('Yes')
else:
    print('No')
    

### FIXED CODE ###

N = input()
if(N[0] == N[1] == N[2] or  N[1] == N[2] == N[3]):
    print('Yes')
else:
    print('No')
N = int(input())
A = list(map(int, input().split()))

if 0 in A:
    print(0)
else:
    ans = 1
    for i in range(A):
        ans += A[i]
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

if 0 in A:
    print(0)
    exit()

ans = A[0]
for i in range(1, N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
aa = map(int,input().split())
print(max(aa)-min(aa))

### FIXED CODE ###

aa = list(map(int,input().split()))
print(max(aa)-min(aa))
import math

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

print((a * b) // math.gcd(a, b))


### FIXED CODE ###

# import math
import fractions

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

print((a * b) // fractions.gcd(a, b))
n = int(input())

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

a = 0

for i in range(len(l)):
    for j in range(i+1,len(l)):
        if j > l[i]+l[j]]:
            a+=1
        

print(a)

### FIXED CODE ###

import bisect
n = int(input())
 
l = list(map(int, input().split()))
l.sort()
a = 0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        s = bisect.bisect_left(l,l[i]+l[j])-j-1
        a+=s


print(a)
def cul(a, b):
  return [i for i in range(1,min(a,b)+1) if a%i==0 and b%i==0]
a, b = list(map(int, input().split()))
cf = cul(a, b)
n = len(cf)
i = 1
while True:
  tmp = cf[i]
  for c in cf[i:]:
    if c==tmp:
      continue
    elif c%tmp==0:
      cf.remove(c)
  if cf[-1]==tmp:
    print(len(cf))
    break
  else:
    i += 1

### FIXED CODE ###

def prime_factorize(n):
    a = set([1])
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    a.add(n)
    return a
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
a, b = list(map(int, input().split()))
x = gcd(a, b)
print(len(prime_factorize(x)))
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**7

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    #if ans[par] <= idx:
    #    ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    #else:
    #    ans[now] = ans[par]
    ans[now] = bisect.bisect_left(dp, INF)

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
#dp = [-INF] + [INF] * n
dp = [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

### FIXED CODE ###

# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)
X, Y = map(int, input().split())

for i in range(X + 1):
    if i * 2 + (X - i) * 4 == Y:
        print('Yes')
        break
else:
    print('No')

### FIXED CODE ###

n = list(map(int, input().split()))
result = 0
for i in range(len(n)):
  if n[i] == 0:
    print(i+1)
n = int(input())
a = list(map(int,input().split()))
count = [0]*n
for i in a:
    count[i] += 1
    
ans = 0
if n%2 == 0:
    if all(count[2*f]==0 for f in range(n//2)) and all(count[2*k-1]==2 for k in range(1,n//2)):  
        ans = (2**(n//2)) % (1e+9 + 7)
else:
    if count[0] == 1 and all(count[2*f]==2 for f in range(1,n//2)) and all(count[2*k-1]==0 for k in range(1,n//2)):
        ans = (2**(n//2)) % (1e+9 + 7)

print(int(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
count = [0]*n
for i in a:
    count[i] += 1
    
ans = 0
if n%2 == 0:
    if all(count[2*f]==0 for f in range(n//2)) and all(count[2*k-1]==2 for k in range(1,n//2)):  
        ans = 1
else:
    if count[0] == 1 and all(count[2*f]==2 for f in range(1,n//2)) and all(count[2*k-1]==0 for k in range(1,n//2)):
        ans = 1
        
if ans == 1:
    for i in range(n//2):
        ans = (ans*2) % (1e+9+7)

print(int(ans))
s = input()

if len(set(s)) == 2 and s. count(s[0]) == 2:
    print('Yes')
 else:
     print('No')

### FIXED CODE ###

s = input()

if s[0] == s[1] and s[2] == s[3] and s[0] != s[2]:
    print('Yes')
elif s[0] == s[2] and s[1] == s[3] and s[0] != s[1]:
    print('Yes')     
elif s[0] == s[3] and s[1] == s[2] and s[0] != s[1]:
    print('Yes')
else:
    print('No')