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

H, W, D = map(int, input().split())
dp = [[0]*(H+1)*(W+1) for i in range(D)]
dic = {}
for i in range(H):
  a = [int(i) for i in input().split()]
  for j in range(W):
    # y, x
    dic[a[j]] = (i, j)

for i in range(D):
  ps = i
  if ps==0:
    ps = D
  count = 0
  y, x = dic[ps]
  while True:
    ps += D
    if H*W<ps:
      break
    count += 1
    ny, nx = dic[ps]
    dp[i][count] = dp[i][count-1]+abs(ny-y)+abs(nx-x)
    y = ny
    x = nx


Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  ID = L%D
  LI = L//D
  RI = R//D
  if ID!=0:
    print(dp[ID][RI]-dp[ID][LI])
  else:
    print(dp[ID][RI-1]-dp[ID][LI-1])



### FIXED CODE ###

H, W, D = map(int, input().split())
px = [0]*(H*W+1)
py = [0]*(H*W+1)
dp = [0]*(H*W+1)
for i in range(H):
  inf = input().split()
  for j in range(W):
    a = int(inf[j])
    py[a] = i
    px[a] = j
for i in range(D+1, H*W+1):
  dp[i] = dp[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  print(dp[R]-dp[L])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7

dp = [[0] * (m + 1) for _ in range(n + 1)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        if ei == ej:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

        dp[i][j] %= mod

ans = dp[n][m] + 1
ans %= mod
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 1
for j in range(m + 1):
    dp[0][j] = 1


for i, es in enumerate(s, 1):
    for j, et in enumerate(t, 1):
        if es == et:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

        dp[i][j] %= mod

ans = dp[n][m]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*m
c = [0]*m
sortsecond = lambda val: val[1]

x = [list(map(int, input().split())) for _ in range(m)]
x.sort(key=sortsecond)

for j in range(m):
    times = x[-(j+1)][0]
    number = x[-(j+1)][1]
    while times > 0 :

        temp = min(a)
        if temp < number:
            a[a.index(temp)] = number
        else:
            break
        times -= 1


print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*m
c = [0]*m
sortsecond = lambda val: val[1]

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

x.sort(key=sortsecond)

a.sort()


i = 0
for j in range(m):
    times = x[-(j+1)][0]
    number = x[-(j+1)][1]
    while times > 0 :

        try:
            temp = a[i]
        except IndexError:
            print(sum(a))
            exit()
        
        if temp < number:
            a[i] = number
        else:
            print(sum(a))
            exit()
        times -= 1
        i += 1
print(sum(a))
### BUGGY CODE ###

def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


def f(x):
    if x < 2:
        return False

    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1

    return True


n = int(input())

if f(n):
    print(1)
    exit()

is_prime = sieve(10 ** 7)
primes = [i for i, e in enumerate(is_prime) if e]

ans = 0
used = set()
for e in primes:
    div = e
    while div <= n:
        if n % div == 0:
            ans += 1
            n //= div
            used.add(div)
        div *= e


print(ans)


### FIXED CODE ###

from collections import defaultdict


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


n = int(input())

is_prime = sieve(10 ** 6)
primes = [i for i, e in enumerate(is_prime) if e]

d = defaultdict(int)
for e in primes:
    while n % e == 0:
        n //= e
        d[e] += 1

if n != 1:
    d[n] += 1

ans = 0
for v in d.values():
    mn = 1
    while v >= mn:
        v -= mn
        ans += 1
        mn += 1

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

#import heapq
#import itertools
#import math
#import numpy as np
#import sys

#N = int(input())
N, K, Q = list(map(int, input().split()))
A = [input() for _ in range(Q)]
#T = [list(map(int,input().split())) for _ in range(N)]
H = [K] * N
#print(A)
#print(H)
for a in A :
    for i in range(N) :
        if i == int(a) :
            pass
        else :
            H[i -1] -= 1
for h in H :
    if h > 0 :
        print('Yes')
    else :
        print('No')
#ans = ['Yes' if h > 0 else 'No' for h in H]
#for a
#print(ans)

### FIXED CODE ###

#import heapq
#import itertools
#import math
#import numpy as np
#import sys

#N = int(input())
N, K, Q = list(map(int, input().split()))
A = [int(input()) for _ in range(Q)]
S = [0] * N
for i in A :
    S[i - 1] += 1
for s in S :
    if s > Q - K :
        print('Yes')
    else :
        print('No')


#for i in range(1,N+1) :
#    s = 0
#    for a in A :
#        if i == a :
#            s += 1
#    if s > Q - K :
#        print('Yes')
#    else :
#        print('No')


#T = [list(map(int,input().split())) for _ in range(N)]
#H = [K] * N
#print(A)
#print(H)
#for a in A :
#    for i in range(N) :
#        if i == int(a) :
#            pass
#        else :
#            H[i -1] -= 1
#for h in H :
#    if h > 0 :
#        print('Yes')
#    else :
#        print('No')
#ans = ['Yes' if h > 0 else 'No' for h in H]
#for a
#print(ans)
### BUGGY CODE ###

import math

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



if __name__ == "__main__":
    N = int(input())
    total = 0
    for i in range(1,N+1):
        Y = math.floor(N/i)
        total += int(Y*(Y+1)*i/2)
    print(total)

### FIXED CODE ###

import math

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



if __name__ == "__main__":
    N = int(input())
    total = 0
    for i in range(1,N+1):
        Y = math.floor(N/i)
        total += int(Y*(Y+1)*i/2)
    print(total)
### BUGGY CODE ###

N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

upper = 10**5
dp = [float("inf") for i in range(upper+1)]
dp[0] = 0

for item in range(N) :
    weight_i,value_i = L[item]
    for value in range(upper, value_i-1, -1) :
        if dp[value - value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value - value_i] + weight_i)

for value in range(upper, -1, -1) :
    if dp[value] < float("inf") :
        ans = value
        break

print(ans)


### FIXED CODE ###

N,W = map(int,input().split())

max_size = 10**5
dp = [float("inf") for i in range(max_size+1)]
dp[0] = 0

for i in range(N) :
    weight,value = map(int,input().split())
    for j in range(max_size, value-1, -1) :
        if dp[j - value] + weight <= W :
            dp[j] = min(dp[j], dp[j-value] + weight)

for i in range(max_size, -1, -1) :
    if dp[i] < float("inf") :
        ans = i
        break

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

import sys
from itertools import product as prd
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1
isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX: xs.append(cur)
            else: ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F': cur += 1

if cur:
    if isX: xs.append(cur)
    else: ys.append(cur)
sumxs = sum(xs)
sumys = sum(ys)

if abs(X) > sumxs or abs(Y) > sumys:
    print('No')
    exit()

memo1 = [[0]*(sumxs*2+1) for i in range(len(xs)+1)]
memo2 = [[0]*(sumys*2+1) for i in range(len(ys)+1)]

memo1[0][0] = 1
memo2[0][0] = 1
for i, j in prd(range(1, len(xs)+1), range(-sumxs, sumxs+1)):
    memo1[i][j] = memo1[i-1][j+xs[i-1]] or memo1[i-1][j-xs[i-1]]

for i, j in prd(range(1, len(ys)+1), range(-sumys, sumys+1)):
    memo2[i][j] = memo2[i-1][j+ys[i-1]] or memo2[i-1][j-ys[i-1]]

print('Yes' if memo1[len(xs)][X] and memo2[len(ys)][Y] else 'No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1

isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX:
                xs.append(cur)
            else:
                ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F':
        cur += 1

if cur:
    if isX:
        xs.append(cur)
    else:
        ys.append(cur)

X=abs(X)
Y=abs(Y)
xs.sort()
ys.sort()
xss = [0]
yss = [0]
for i in xs:
    xss.append(xss[-1]+i)
for i in ys:
    yss.append(yss[-1]+i)

memo1 = {}
def dp1(x, i):
    if abs(x) > xss[i+1]: return False
    if i < 0: return x == 0
    if (x, i) in memo1: return memo1[(x,i)]
    res = dp1(x - xs[i], i-1) or dp1(x + xs[i], i-1)
    memo1[(x,i)] = res
    return res

memo2 = {}
def dp2(x, i):
    if abs(x) > yss[i+1]: return False
    if i < 0: return x == 0
    if (x, i) in memo2: return memo2[(x,i)]
    res = dp2(x - ys[i], i-1) or dp2(x + ys[i], i-1)
    memo2[(x,i)] = res
    return res


# print(xs, ys)
print('Yes' if dp1(X, len(xs)-1) and dp2(Y, len(ys)-1) else 'No')
### BUGGY CODE ###

# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [1 for _ in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[N-1] = -1
        break
print(ind_list.count(1))

### FIXED CODE ###

# D - Not Divisible
N = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(N):
    l[a[i]] += 1
    
answer = 0
for i in range(N):
    if l[a[i]] == 1:
        answer += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10
print(answer)
### BUGGY CODE ###

N, M, Q = [int(_) for _ in input().split()]
train = [[]] * M
question = [[]] * Q
for i in range(M):
    train[i] = [int(_) for _ in input().split()]
for i in range(Q):
    question[i] = [int(_) for _ in input().split()]

l = []
for i in range(Q):
    counter = 0
    p = question[i][0]
    q = question[i][1]
    for j in range(M):
        if p <= train[j][0] and train[j][1] <= q:
            counter += 1
    l.append(counter)

for i in range(Q):
    print(l[i])

### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]

l = [[0 for i in range(N+1)] for j in range(N+2)]
for t in [input().split() for _ in range(M)]:
    i = int(t[0])
    j = int(t[1])
    l[i][j] += 1

for k in range(N):
    for i in range(1, N-k+1):
        j = i + k
        l[i][j] += l[i][j-1] + l[i+1][j] - l[i+1][j-1]

for k in [input().split() for _ in range(Q)]:
    p = int(k[0])
    q = int(k[1])
    print(l[p][q])
### BUGGY CODE ###

import sys

r,c,k=map(int,input().split())
dp=[[[0 for kk in range(4)] for jj in range(c+1)] for ii in range(r+1)]

g=[[0 for j in range(c)] for i in range(r)]
for i in range(k):
    rr,cc,v=map(int,input().split())
    rr-=1
    cc-=1
    g[rr][cc]=v
for i in range(1,r+1):
    for j in range(1,c+1):
        for k in range(4):
            dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])#,dp[i][j-1][k])
            dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
            if k>0:
                if dp[i][j][k]<dp[i][j-1][k-1]+g[i-1][j-1]:
                    dp[i][j][k]=dp[i][j-1][k-1]+g[i-1][j-1]
            if dp[i][j][1]<dp[i-1][j][k]+g[i-1][j-1]:
                dp[i][j][1]=dp[i-1][j][k]+g[i-1][j-1]
print(max(dp[r][c]))



### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for jj in range(c+1)] for ii in range(r+1)] for kk in range(4)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])#,dp[i][j-1][k])
                dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[k][i][j]<dp[k-1][i][j-1]+g[i-1][j-1]:
                            dp[k][i][j]=dp[k-1][i][j-1]+g[i-1][j-1]
                    if dp[1][i][j]<dp[k][i-1][j]+g[i-1][j-1]:
                        dp[1][i][j]=dp[k][i-1][j]+g[i-1][j-1]
    print(max(dp[0][r][c],dp[1][r][c],dp[2][r][c],dp[3][r][c]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

N = int(input())
ABC = [list(map(int, input().split(" "))) for _ in range(N)]

# l = [[None for _ in range(3)] for _ in range(N+10)]
@lru_cache(maxsize=(N+10)*3)
def dp(i, use):
    if i == -1:
        return 0
    # if l[i][use] != None:
    #     return l[i][use]
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    # l[i][use] = max_num 
    return max_num

print(max(dp(N-1, m) for m in range(3)))


### FIXED CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

N = int(input())
ABC = [list(map(int, input().split(" "))) for _ in range(N)]

l = [[None for _ in range(3)] for _ in range(N+10)]
# @lru_cache(maxsize=None)
def dp(i, use):
    if i == -1:
        return 0
    if l[i][use] != None:
        return l[i][use]
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    l[i][use] = max_num 
    return max_num

print(max(dp(N-1, m) for m in range(3)))
### BUGGY CODE ###

import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
S = np.array(S)
T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = abs(S-a)
    T1 = abs(T-a)
    ans1 +=np.min(T1)
    ans1 += np.min(abs(S-T[np.argmin(T1)]))
    ans2+=np.min(S1)
    ans2+= np.min(abs(T-S[np.argmin(S1)]))
    print(min(ans1,ans2))

### FIXED CODE ###

import bisect
A,B,Q = map(int,input().split()) 
INF = 10**18
S = [-INF]+[int(input()) for _ in range(A)]+[INF]
T = [-INF]+[int(input()) for _ in range(B) ]+[INF]
x = [int(input()) for _ in range(Q)]

for a in x:
    ans1 = 0
    ans2 = 0
    b = bisect.bisect_left(S,a)
    c = bisect.bisect_left(T,a)
    res = INF
    for s in [S[b-1],S[b]]:
        for t in [T[c-1],T[c]]:
            d1,d2 = abs(s-a)+abs(s-t),abs(t-a)+abs(s-t)
            res = min(res,d1,d2)
    print(res)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= MOD
        
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
A.reverse()
for _ in range(M):
    A[0] = A[0] // 2
    A.sort()
    A.reverse()

ans = 0
for i in range(N):
    ans += A[i]

print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]

# 優先度付きキューに変換
heapq.heapify(A)

# 最小値（最大値）の値を半分にしていく
for i in range(M):
    tmp = -heapq.heappop(A) // 2
    heapq.heappush(A, -tmp)

print(-sum(A))
### BUGGY CODE ###

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

mod = 10**9+7
r = n-k

def mod_combination(n, k, mod):
     # nCk (mod m)
     def mod_permutation(n, k, mod):
         if n<=k:
             return 1
         else:
             return (n * mod_permutation(n-1, k, mod))%mod
 
     def mod_inv_permutation(k, mod):
         k, mod = int(k), int(mod)
         if k<=1:
             return 1
         else:
             return (pow(k, mod-2, mod) * mod_inv_permutation(k-1, mod))%mod
 
     return (mod_permutation(n, n-k, mod) * mod_inv_permutation(k, mod))%mod

def f(n):
    a = mod_combination(k-1, n, mod)
    return a

for i in range(k):
    ans = 1
    ans = mod_combination(r+1, i+1, mod) * mod_combination(k-1, i, mod) % mod
    print(ans)

### FIXED CODE ###

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

mod = 10**9+7
r = n-k

def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    invs[0] = 1
    
    return factorials, invs

fr, inv = prepare(2010, mod)
for i in range(k):
    ans = 1
    if r-i < 0:
        ans = 0
    else:
        ans = (((fr[n-k+1] * inv[i+1] * inv[n-k-i]) % mod) * fr[k-1] * inv[i] * inv[k-1-i]) % mod
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  def popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
              
  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = popcount(i) % 2
    ans += (-1)**cnt * 2**(n-1-popcount(s))
  print(ans)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = bin(i).count("1") % 2
    ans += (-1)**cnt * 2**(n-1-bin(s).count("1"))
  print(ans)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

x = [-1]
y = [-1]
for i in range(m):
    x_in, y_in = map(int, input().split())
    x.append(x_in)
    y.append(y_in)

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    if memo[i] == -1:
        ret = 0
        for j in range(m + 1)[1:]:
            if x[j] == i:
                tmp = dp(y[j]) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        return ret
    else:
        return memo[i]


for i in x[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    y[x_in].append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in in y[i][1:]:
            tmp = dp(x_in) + 1
            if tmp > ret:
                ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))
### BUGGY CODE ###

import collections
ta = int(raw_input())
vis = set([0])
q = collections.deque([(0,0)])
while(q):
	x,t = q.popleft()
	if x == ta:
		print t
		break
	for nt in [x-t-1,x,x+t+1]:
		q.append((nt, t + 1))




### FIXED CODE ###

import collections
target = int(raw_input())
t = 0
while(target):
	target -= min(target, t + 1)
	t +=1
print t