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

import itertools


def bit_patterns(n):
    return list(itertools.product(range(2), repeat=n))


def actual(n, V, C):
    diff_list = []

    for bit_pattern in bit_patterns(n):
        values = sum([bit * value for bit, value in zip(bit_pattern, V)])
        costs = sum([bit * cost for bit, cost in zip(bit_pattern, C)])

        diff_list.append(values - costs)

    return max(diff_list)

n = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

print(actual(n, V, C))

### FIXED CODE ###

def actual(n, V, C):
    # 購入するとプラスになるものだけ買って合計でおk
    sale_jewels = []

    for v, c in zip(V, C):
        if v - c > 0:
            sale_jewels.append(v - c)

    return sum(sale_jewels)

    # return sum([v - c for v, c in zip(V, C) if v - c > 0])


n = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

print(actual(n, V, C))
### BUGGY CODE ###

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()), reverse=True)
print(sum(C[1:]))
L = [-1]*n
L[0] = C[0]
L[T[0][0]] = C[1]
used = [0, T[0][0]]
for i in range(2, n):
  for v in used:
    for nv in T[v]:
      if L[nv] == -1:
        L[nv] = C[i]
        used.append(nv)
        break
    else:
      continue
    break
print(*L)

### FIXED CODE ###

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()))
print(sum(C[:-1]))
L = [-1]*n
stack = [0]
while stack:
  temp = stack.pop()
  L[temp] = C.pop()
  for v in T[temp]:
    if L[v] == -1:
      stack.append(v)
print(*L)
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = defaultdict(list)
    for i, s in enumerate(S):
        rgb[s].append(i)

    ans = 0
    for i, s in enumerate(S):
        if s == 'R':
            x = bisect(rgb['G'], i)
            for gi in rgb['G'][x:]:
                d = gi - i
                y = bisect(rgb['B'], gi)
                for bi in rgb['B'][y:]:
                    if d != bi - gi:
                        ans += 1
            x = bisect(rgb['B'], i)
            for bi in rgb['B'][x:]:
                d = bi - i
                y = bisect(rgb['G'], bi)
                for gi in rgb['G'][y:]:
                    if d != gi - bi:
                        ans += 1
        if s == 'G':
            x = bisect(rgb['R'], i)
            for ri in rgb['R'][x:]:
                d = ri - i
                y = bisect(rgb['B'], ri)
                for bi in rgb['B'][y:]:
                    if d != bi - ri:
                        ans += 1
            x = bisect(rgb['B'], i)
            for bi in rgb['B'][x:]:
                d = bi - i
                y = bisect(rgb['R'], bi)
                for ri in rgb['R'][y:]:
                    if d != ri - bi:
                        ans += 1
        if s == 'B':
            x = bisect(rgb['G'], i)
            for gi in rgb['G'][x:]:
                d = gi - i
                y = bisect(rgb['R'], gi)
                for ri in rgb['R'][y:]:
                    if d != ri - gi:
                        ans += 1
            x = bisect(rgb['R'], i)
            for ri in rgb['R'][x:]:
                d = ri - i
                y = bisect(rgb['G'], ri)
                for gi in rgb['G'][y:]:
                    if d != gi - ri:
                        ans += 1
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
na=0
for i in range(H):
    for j in range(W):
        if S[i,j]:
            nat=1
            for ibw in reversed(range(i)):
                if S[ibw,j]:
                    nat+=1
                else:
                    break
            for ifw in range(i+1,H):
                if S[ifw,j]:
                    nat+=1
                else:
                    break
            for jbw in reversed(range(j)):
                if S[i,jbw]:
                    nat+=1
                else:
                    break
            for jfw in range(j+1,W):
                if S[i,jfw]:
                    nat+=1
                else:
                    break
            na=max(nat,na)

print(na)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
T=np.zeros((H,W),dtype=int)
B=np.zeros((H,W),dtype=int)
L=np.zeros((H,W),dtype=int)
R=np.zeros((H,W),dtype=int)

for i in range(1,H):  
    T[i,:]=(T[i-1,:]+1)*S[i-1,:]

for i in reversed(range(H-1)):
    B[i,:]=(B[i+1,:]+1)*S[i+1,:]

for j in range(1,W):
    L[:,j]=(L[:,j-1]+1)*S[:,j-1]        

for j in reversed(range(W-1)):
    R[:,j]=(R[:,j+1]+1)*S[:,j+1]
        

na=((T+B+L+R)*S).max()+1

print(na)
### BUGGY CODE ###

# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
for i in range(N-1):
    for j in range(i+1,N):
        if A[j] %A[i] ==0:
            count.add(A[j])
ans =len(A_set - count)
print(ans)

### FIXED CODE ###


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

H,N = map(int, input().split())
dp_ = [0]+[float("inf")]*H
for n in range(N):
  dp = [0]+[float("inf")]*H
  A,B = map(int, input().split())
  for h in range(1,H+1):
    h_ = max(0,h-A)
    dp[h] = min(dp_[h], dp[h_]+B)
  dp_ = dp
print(dp[-1])

### FIXED CODE ###

H,N,*AB = map(int, open(0).read().split())
dp = [0]+[10**8]*H
for n in range(N):
  A,B = AB[2*n:2*(n+1)]
  for h in range(1,H+1): dp[h] = min(dp[h],dp[max(0,h-A)]+B)
print(dp[-1])
### BUGGY CODE ###

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

ans = 10000000000
aa = sum(a)

for i in range(N-1):
    sum_a = sum(a[:i+1])
    sum_b = aa-sum_a
    sa = abs(sum_a-sum_b)
    ans = min(ans, sa)

print(ans)


### FIXED CODE ###

input()
cards = tuple(map(int, input().split(' ')))

a = sum(cards[1:])
s = cards[0]
diff_min = abs(a - s)

for card in cards[1:-1]:
    a -= card
    s += card
    diff_min = min(diff_min, abs(a - s))

print(diff_min)
### BUGGY CODE ###

n=int(input())
S=[input() for _ in range(n)]
S_set = set(S)
cnt={}

for s in S_set:
    cnt[s] = S.count(s)

m=max(cnt.values())
L=[]

for a in cnt.keys():
    if cnt[a] == m:
        L.append(a)
L.sort()
for i in range(len(L)):
    print(L[i])


### FIXED CODE ###

n=int(input())

cnt={}
ans=[]

for i in range(n):
    s=input()
    if s in cnt.keys():
        cnt[s] += 1
    else:
        cnt[s] = 1

m=max(cnt.values())
key = sorted(cnt.keys())

for a in key:
    if cnt[a] == m:
        print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N+1):
    print(A.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sub = []
for i in range(0, n):
    sub.append(0)
for j in a :
    sub[j - 1] += 1
for i in sub:
    print(i)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
b = set(a)
count = 0
for i in b:
    j = a.count(i)
    if j < i:
        count += j
    else:
        k = j - i
        count += k
print(count)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(set(a))
count = 0
z = 0
for i in b:
    if i > n:
        count += n-z
        break
    else:
        j = a.count(i)
        if j < i:
            count += j
            z += j
        else:
            count += j-i
            z += j
print(count)
### BUGGY CODE ###

n,a,b = map(int,input().split())
for i in range(10**18):
    if i*(a+b)==n:
        print(a*i)
        exit()
    elif i*(a+b)>n:
        t = n-(i-1)*(a+b)
        if t>a:
            t = a
        print((i-1)*a+t)
        exit()

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = n // (a+b) * a
rem = n % (a+b)
ans += min(rem,a)
print(ans)
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
if flag == '1':
	lst.append(0)
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
for i in range(l):
	if i % 2 == 0:
		end = i+2*K
		if i != 0:
			maximum = max(maximum, sum(lst[i-1:end]))
		else:
			maximum = max(maximum, sum(lst[i:end]))
		if end > l:
			break
	else:
		end = 2*K+1
		maximum = max(maximum, sum(lst[i:end]))
		if end > l:
			break
print(maximum)


### FIXED CODE ###

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
if flag == '1':
	lst.append(0)
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
temp = sum(lst[0:2*K])
maximum = max(maximum, temp)
for i in range(2, l, 2):
	end = i+2*K
	temp = temp - lst[i-2] + sum(lst[end-2:end])
	if i != 2:
		temp -= lst[i-3]
	maximum = max(maximum, temp)

print(maximum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    c_sorted = sorted(c)

    for n in b:
        ab = 0
        bc = 0
        for i in a_sorted:
            if n > i:
                ab += 1

        for i in c_sorted:
            if n < i:
                bc += 1

        count += ab * bc
    return count
        
if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
    
def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    b_sorted = sorted(b)
    c_sorted = sorted(c)
    maxlen=len(b)

    for target in b_sorted:
        #mid_a = binary_search_left(a_sorted,target)
        #mid_c = binary_search_right(c_sorted,target)
        mid_a = bisect.bisect_left(a_sorted,target)
        mid_c = bisect.bisect_right(c_sorted,target)
        count += mid_a * (maxlen - mid_c)
        #print("mid_a %d, mid_c %d, count %d" %(mid_a,maxlen - mid_c,count))
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for i in range(N):
    nextDP = dp.copy()
    w, v = map(int, input().split())
    for j in range(W+1-w):
        if dp[j] >= 0:
            nextDP[j+w] = max(dp[j+w], dp[j] + v)
    dp = nextDP.copy()

ans = max(dp)
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W-w, -1, -1):
        if dp[j] == -1:
            continue
        else:
            dp[j+w] = max(dp[j+w], dp[j] + v)

print(max(dp))
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for i in range(Q):
    Query = input()
    T = int(Query[0])
    if T == 1:
        reverse = not reverse 
    elif T == 2:
        F = int(Query[2])
        C = Query[4]
        if (F == 1 and reverse == False) or (F == 2 and reverse == True):
            S = C + S
        elif (F == 2 and reverse == False) or (F == 1 and reverse == True):
            S = S + C

if reverse == True:
    S = S[::-1]


print(S)
print('\n')


### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

sorted_A_list = sorted(A_list)

def counter(x, l=A_list): #リストlに格納されている_xのインデックスを全て取得する
    return [i for i, _x in enumerate(l) if _x == x]


count = 0
gate = 0
ans = 0
if N == 1:
    ans = A_list[0] * M
    print(ans)
else:
    for i in range(N):
        index_B_list = counter(sorted_A_list[i])
        for j in index_B_list:
            count += B_list[j]
            if count <= M:
                ans += sorted_A_list[i] * B_list[j]
            else:
                if gate == 0: #ここを使用するのは答えを出す一回だけ
                    count -= B_list[j]
                    ans += sorted_A_list[i] * (M - count)
                    print(ans)
                    gate += 1


### FIXED CODE ###

N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(N)]) #入力する時から気をつける

count = 0
ans = 0
for _ab in ab:
    diff = M - count
    if _ab[1] < diff:
        count += _ab[1]  
        ans += _ab[0] * _ab[1]
    else:
        ans += _ab[0] * diff
        break

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

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

ans = 1
for i in range(1, n):
    if min(p[:i]) >= p[i]:
        ans += 1
        
print(ans)

### FIXED CODE ###

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

m = []
a = p[0]
for j in range(n):
    if a >= p[j]:
        a = p[j]
        m.append(a)
    else:
        m.append(a)

ans = 1
for i in range(n-1):
    if m[i] > m[i+1]:
        ans += 1
        
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
A=sorted(list(map(int,input().split())))
mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*= A[-i-1]
        now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        l+=2
    else:
        ans*= pl%mod
        r-=2
print(ans%mod)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
mod=10**9+7
ans=1

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

l=0
r=N-1
if K%2==1:
    ans=ans*A[r]
    r-=1

for _ in range(K//2):
    ml=A[l]*A[l+1]
    mr=A[r]*A[r-1]
    if ml>mr:
        ans=ans*ml%mod
        l+=2
    else:
        ans=ans*mr%mod
        r-=2

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

n = int(input())
R = [int(input()) for x in range(n)]
maxv = -2000000000

for j in range(1, n):
    for i in range(j):
        maxv = max(maxv, R[j] - R[i])

print(maxv)

### FIXED CODE ###

n = int(input())
r = [int(input()) for x in range(n)]
maxv = -2000000000
minv = r[0]

for i in range(1, n):
    maxv = max(maxv, r[i] - minv)
    minv = min(minv, r[i])

print(maxv)
### BUGGY CODE ###

K = int(input())

sevens = 0
count = 0
repeat = True

if {K%10} & {0,2,4,5,6,8}:
    count = -1
    repeat = False

while repeat:
    sevens = sevens * 10 + 7
    count += 1
    if sevens % K == 0:
        repeat = False

print(count)

### FIXED CODE ###

K = int(input())

sevens = 0
count = 0
repeat = True

if {K%10} & {0,2,4,5,6,8}:
    count = -1
    repeat = False

while repeat:
    sevens = sevens % K * 10 + 7
    count += 1
    if sevens % K == 0:
        repeat = False

print(count)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    ss = sorted(input())
    s.append(''.join(ss))

s2 = list(set(s))
ans = 0

for i in s2:
    j = s.count(i)
    ans += j * (j-1)//2

print(ans)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    ss = sorted(input())
    s.append(''.join(ss))

s.sort()
ans = 0
lcnt = 1
for i in range(1,len(s)):
    if s[i] == s[i-1]:
        lcnt += 1
    else:
        ans += lcnt * (lcnt-1)//2
        lcnt=1

ans += lcnt * (lcnt-1)//2

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

# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()

count = 0
i = len(A)
while i > 0:
    i -= 1
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    if i == j or A[j] != comp:
        continue
    if i < j:
        A.pop(j)
        A.pop(i)
    else:
        A.pop(i)
        A.pop(j)
    count += 1
    i -= 1

print(count)


### FIXED CODE ###

# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
B = []
C = []
i = 0
while i < len(A):
    j = i
    count = 1
    while i+1 < len(A) and A[j] == A[i+1]:
        count += 1
        i += 1
    B.append(A[j])
    C.append(count)
    i += 1

count = 0
i = len(B) - 1
while i >= 0:
    comp = getComp(B[i])
    j = bisect_left(B, comp)
    if i == j and C[i] < 2:
        i -= 1
        continue
    if B[j] != comp:
        i -= 1
        continue
    if not C[i] or not C[j]:
        i -= 1
        continue
    C[i] -= 1
    C[j] -= 1
    count += 1

print(count)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    
    # u高橋, s青木
    n,u,s = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ta = [-1]*n
    ao = [-1]*n

    d = deque([s-1])
    ao[s-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ao[nv] == -1:
                ao[nv] = ao[v] + 1
                d.append(nv)

    d = deque([u-1])
    ta[u-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ta[v]+1 <= ao[nv] and ta[v] < ao[v]:
                ta[nv] = ta[v] + 1
                d.append(nv)
    print(max(ta))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    
    # u高橋, s青木
    n,u,s = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ta = [-1]*n
    ao = [-1]*n

    d = deque([s-1])
    ao[s-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ao[nv] == -1:
                ao[nv] = ao[v] + 1
                d.append(nv)

    d = deque([u-1])
    ta[u-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ta[nv] == -1:
                ta[nv] = ta[v] + 1
                d.append(nv)

    res = 0
    for i in range(n):
        if ta[i] < ao[i]:
            res = max(res, ao[i]-1)
    print(res)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
L = [0] * N
R = list()
for i in range(N):
  R.append(i-A[i])
  if(i+A[i]<=N-1):
    L[i+A[i]] += 1
for r in R:
  if(r > 0):
    ans += L[r]
print(ans)
### BUGGY CODE ###

n = int( input())
total = 0
if n ==1:
    print(0)
else:
    for i in range(n):
        total += i
    print(total)

### FIXED CODE ###

n = int( input())
total = 0
if n ==1:
    print(0)
else:
    print((n*(n-1))//2)