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

def main():
    from collections import deque
    import sys
    import bisect
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 8)
    n = int(input())
    a = list(map(int, input().split()))
    edges = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        edges[u - 1].append(v - 1)
        edges[v - 1].append(u - 1)

    d = [-1 for _ in range(n)]
    memo = [[] for _ in range(n)]
    que = deque()
    que.append(0)
    memo[0] = [a[0]]
    d[0] = 1

    while len(que):
        cur = que.popleft()
        for to in edges[cur]:
            if d[to] == -1:
                memo[to] = memo[cur].copy()
                if memo[cur][-1] < a[to]:
                    d[to] = d[cur] + 1
                    memo[to].append(a[to])
                else:
                    d[to] = d[cur]
                    memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
                que.append(to)
        memo[cur] = []

    for i in range(n):
        print(d[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

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

inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
    memo = bisect.bisect_left(dp, a[cur])
    memo_v = dp[memo]
    dp[memo] = a[cur]
    d[cur] = bisect.bisect_left(dp, inf)

    for to in edges[cur]:
        if to != prev:
            dfs(to, cur)

    dp[memo] = memo_v

dfs(0, -1)
for i in range(n):
    print(d[i])
### BUGGY CODE ###

K = int(input())
 
sevens = 7 % K
count = 1
 
while(sevens % K !=0):
  # 計算桁を減らすために(mod K)で7, 77, 777,,,を計算する
  sevens = sevens * (10 % K) + (7 % K)
  count += 1
  if count > K:
    count = -1
    break
    
print(count)

### FIXED CODE ###

K = int(input())
 
sevens = 7 % K
count = 1
 
while(sevens % K !=0):
  sevens = sevens * (10 % K) + (7 % K)
  sevens = sevens % K
  count += 1
  if count > K:
    count = -1
    break
    
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [0] * (N - K)

    for i in range(K, N):
        min_cost = 10**9            
        for j in range(1, K+1):
            cost = dp[i-j] + abs(H[i] - H[i-j])
            min_cost = min(min_cost, cost)
        dp[i] = min_cost

    print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [10**9] * (N - K)

    for i in range(K, N):
        for j in range(1, K+1):
            dp[i]= min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

    print(dp[-1])
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    
    r = 0
    for i in range(N):
        for j in range(i, N):
            x = j-i
            for k in range(j, N):
                if x == k-j:
                    continue
                if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                    r += 1
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
def main():
    n=int(input())
    s=input()
    d=Counter(s)
    a=d["R"]*d["G"]*d["B"]
    for i in range(n):
        t=min(n-i-1, i)
        for j in range(t+1):
            if s[i-j] != s[i] and s[i-j] != s[i+j] and s[i] != s[i+j]:
                a-=1
    print(a)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

input()
aa = list(map(int, input().split()))
uu = list(set(aa))
cc = uu.copy()
for i in range(len(uu)):
    cc[i] = aa.count(uu[i])
dic = dict(zip(uu,cc))
total = 0
for v in cc:
    total += v * (v-1) / 2

for a in aa:
    print(int(total - dic[a] + 1))

### FIXED CODE ###

input()
from collections import Counter
aa = list(map(int, input().split()))
dic = Counter(aa)

total = 0
for v in dic.values():
    total += v * (v-1) / 2

for a in aa:
    print(int(total - dic[a] + 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int,input().split()))
for i in range(N):
  print((li.index(i+1)+1),end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int,input().split()))
ans = [0] * N
for i in range(N):
    ans[li[i]-1] = i+1
for j in range(N):
    print(ans[j],end = ' ')
### BUGGY CODE ###

K = str(input())
S = '7'*len(K)
ans = 0
while ans == 0:
    if int(S)%int(K) == 0:
        ans = 1
    elif int(K)%2 == 0 or int(K)%5 == 0:
        break
    else:
        S += '7'

if ans == 1:
    print(len(S))
else:
    print('-1')


### FIXED CODE ###

k = int(input())
ans = 7%k

for i in range(1, 10**6 + 1):
  if ans%k == 0:
    print(i)
    exit()
  else:
    ans = (ans*10 + 7)%k
print(-1)
### BUGGY CODE ###

import itertools
N = int(input())
S = input()
C = list(itertools.combinations_with_replacement(range(1, N + 1), 3))
count = 0
for i, j, k in C:
    if (i != 2 * j - k) and (S[i - 1] != S[j - 1] and S[i - 1] != S[k - 1] and S[j - 1] != S[k - 1]):
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
count = S.count("R") * S.count("G") * S.count("B")


for j in range(N):
    for i in range(j):
        k = 2 * j - i
        if k >= N:
            continue
        if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]):
            count -= 1
print(count)
### BUGGY CODE ###

N,A,B = map(int, input().split())
boalsLen = 0
count = 0

while True:
    if boalsLen > N:
        break
    
    tmpBoalsLen = boalsLen + A
    if tmpBoalsLen > N:
        addBoals = N - boalsLen
        count += addBoals
        break
    
    boalsLen = tmpBoalsLen
    boalsLen += B
    count += A

print(count)

### FIXED CODE ###

N,A,B = map(int, input().split())
adds = A + B
times = N // adds
boalsLen = adds * times
count = A * times


while True:
    if boalsLen > N:
        break
    
    tmpBoalsLen = boalsLen + A
    if tmpBoalsLen > N:
        addBoals = N - boalsLen
        count += addBoals
        break
    
    boalsLen = tmpBoalsLen
    boalsLen += B
    count += A

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

n = int(input())
l = [int(i) for i in input().split()]
l = sorted(l, reverse=True)

ans = 0
for i in range(len(l)-2):
    for j in range(i + 1, len(l) - 1):
        for k in range(j + 1, len(l)):
            if l[i] < l[j] + l[k]:
                ans += 1
            else:
                break

print(ans)


### FIXED CODE ###

import bisect
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0
for b in range(n):
    for a in range(b):
        tmp = l[a] + l[b]
        r = bisect.bisect_left(l, tmp)
        ll = b + 1
        ans += max(0, r - ll)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

N = int(input())
S = list(input())

if S[0] == "W" or S[-2] == "W":
    print(0)
    sys.exit()

LR = [0 for i in range(2*N)]
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1

if LR.count(0) != N:
    print(0)
    sys.exit()

count0 = 0
ans = 1
for i in range(2*N):
    if LR[i] == 0:
        count0 += 1
    else:
        ans *= count0 % MOD
        count0 -= 1

def factorial(N, mod):
    if N == 0 or N == 1:
        return 1
    else:
        return N * factorial(N-1, mod) % mod

print(ans*factorial(N,MOD)%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

N = int(input())
S = list(input().rstrip())

if S[0] == "W" or S[-1] == "W":
    print(0)
    sys.exit()

LR = [0 for i in range(2*N)]
count0 = 1
count0_raw = 1
ans = 1
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1

    if LR[i] == 0:
        count0 += 1
        count0_raw += 1
    else:
        ans *= count0
        ans %= MOD
        count0 -= 1

if count0_raw != N:
    print(0)
    sys.exit()

N_k = 1
for i in range(N):
    N_k *= i+1
    N_k %= MOD

print(ans*N_k%MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
# input
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
upd = []
for i in range(m):
    s, l = map(int, input().split())
    temp = [l]*s
    upd.extend(temp)
upd.sort(reverse=True)

# output
f = len(a)
o = 0
c = len(upd)
if f > c:
    for i in range(c):
        o += max(upd[c-1-i], a[c-1-i])
#        print(o)
    print(o+sum(a[c:]))
else:
    for i in range(f):
        o += max(upd[i], a[i])
#        print(o)
    print(o)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
from operator import itemgetter
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
upd = []
for i in range(m):
    upd.append(list(map(int, input().split())))
upd.sort(key=itemgetter(1), reverse=True)
# print(upd)
# output
f = len(a)
p = 0
for t in upd:
    for i in range(p, p+t[0]):
        if p < f:
            if a[p] < t[1]:
                a[p] = t[1]
            else:
                break
        else:
            break
        p += 1
print(sum(a))
### BUGGY CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            dp[i] += dp[now]
            if A[i] > dp[i][-1]:
                dp[i].append(A[i])
            else:
                dp[i][bisect.bisect_left(dp[i], A[i])] = A[i]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

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

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()

    c = [[INF]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1


    for k in range(n): # 経由
        for i in range(n): # 始点
            for j in range(n): # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    if c[0][-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")





if __name__=="__main__":
    main()


### FIXED CODE ###

N, M = map(int, input().split())
L = [list(map(int, input().split())) for i in range(M)]
s = []
g = []
for i in range(M):
    if 1 == L[i][0]:
        s.append(L[i][1])
    if 1 == L[i][1]:
        s.append(L[i][0])
        
for i in range(M):
    if N == L[i][0]:
        g.append(L[i][1])
    if N == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import defaultdict
N = map(int, input().split())
A = list(map(int, input().split()))
res = 0
d = defaultdict(int)
for i, num in enumerate(A):
    res += d[num]
    new_d = defaultdict(int)
    for k, v in d.items():
        new_d[k+1] = v
    new_d[1 - num] += 1
    d = new_d
print(res)

### FIXED CODE ###

from collections import defaultdict
N = map(int, input().split())
A = list(map(int, input().split()))
res = 0
d = defaultdict(int)
for i, num in enumerate(A):
    res += d[i - num]
    d[i + num] += 1
print(res)
### BUGGY 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 *= 10

print(dp[len(S)][5] % INF)


### 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

print(dp[len(S)][5])
### BUGGY CODE ###

def gcd(a, b):
  while b!=0:
    a,b=b,a%b
  return 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)
c = 0
for i in range(0, n):
  d = 0
  for j in range(0, i):
    if gcd(cf[i], cf[j])!=1:
      d = 1
      break
  	
  if d==0:
    c+=1
print(c)


### 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)))
### BUGGY CODE ###

import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  while Q:
    q = heapq.heappop(Q)
    if q <= limit:
      R[q][k] += 1
    else:
      break
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

### FIXED CODE ###

from collections import Counter
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
C = Counter([0])
for x in X:
  tmp = Counter()
  for i, c in C.items():
    tmp[i + x] += c
  C += tmp
print(C[0] - 1)
### BUGGY CODE ###

N = int(input())
for n in range(N):
    ans = 0
    for i in range(1,100):
        for j in range(i,100):
            for k in range(j,100):
                if i==j==k and i**2+j**2+k**2+i*j+j*k+k*i == n+1:
                    ans += 1
                elif (i==j or j==k or k==i)and i**2+j**2+k**2+i*j+j*k+k*i == n+1:
                    ans += 3
                elif i**2+j**2+k**2+i*j+j*k+k*i == n+1:
                    ans += 6
    print(ans)

### FIXED CODE ###

N = int(input())
A = [0]*10000
for i in range(1,100):
    for j in range(i,100):
        for k in range(j,100):
            if i==j==k and i**2+j**2+k**2+i*j+j*k+k*i <= 10**4:
                A[i**2+j**2+k**2+i*j+j*k+k*i-1] += 1
            elif (i==j or j==k or k==i)and i**2+j**2+k**2+i*j+j*k+k*i <= 10**4:
                A[i**2+j**2+k**2+i*j+j*k+k*i-1] += 3
            elif i**2+j**2+k**2+i*j+j*k+k*i <= 10**4:
                A[i**2+j**2+k**2+i*j+j*k+k*i-1] += 6
for i in range(N):
    print(A[i])
### BUGGY CODE ###


n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = [[0] * (n + 1) for _ in range(n + 1)]
for i, (p, a) in enumerate(arr):
  for l in range(i + 1):
    dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
    dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

print(max(dp[n]))


### FIXED CODE ###


def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()
### BUGGY CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
m=max(l)
nums=[i for i in range(n)]
for num in nums:
  if(l[num]!=m or l.count(m)!=1):
    print(m)
  else:
    print(sorted(l)[-2])

### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=sorted(l)
p=s[-1]
q=s[-2]
for i in range(n):
  if l[i]==p:
    print(q)
  else:
    print(p)
### BUGGY CODE ###

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

genzaichi=1
rireki=[]
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

genzaichi=1
if flag==1:
    K=K-(((K-x)//roop)-1)*roop

for i in range(K):
    genzaichi=A[genzaichi-1]

print(genzaichi)

### FIXED CODE ###

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

genzaichi=1
rireki=set()
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.add(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)
### BUGGY CODE ###

def main():
    N = int(input())
    As = list(map(int, input().split()))
    c = 0
    for i in range(N):
        l = 0
        r = 0
        for ii in range(i, N):
            l ^= As[ii]
            r += As[ii]
            if l == r:
                c += 1
            else:
                break

    print(c)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    x = 0
    s = 0
    r = 0
    res = 0
    for l in range(N):
        while N > r and x ^ A[r] == s + A[r]:
            x ^= A[r]
            s += A[r]
            r += 1

        x ^= A[l]
        s -= A[l]
        res += r - l

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

from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

S, T = map(int, input().split())

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

while d:
    next_node = d.pop()
    for v in e[next_node]:
        if(dist[v] > dist[next_node] + 1):
            dist[v] = dist[next_node] + 1
            if(v == (T, 0)):
                break
            d.append(v)

ans = dist[(T, 0)]
if(ans == inf):
    print(-1)
else:
    print(ans//3)



### FIXED CODE ###

from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)
### BUGGY CODE ###

import itertools

n = int(input())
s_list = [input().split() for i in range(n)]
s_list = sorted(["".join(sorted(s[0])) for s in s_list])

comb = itertools.combinations(s_list, 2)
cnt = 0
for c in comb:
  if c[0]==c[1]:
    cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s_list = [input().split() for i in range(n)]
s_list = sorted(["".join(sorted(s[0])) for s in s_list])
s_list.sort()

cnt = 0
p = 1
tmp = 0
while p<n:
  if s_list[p-1]==s_list[p]:
    tmp += 1
  else:
    if tmp==1:
      cnt += tmp
    elif tmp>1:
      tmp += 1
      cnt += (tmp*(tmp-1))//2
    tmp = 0
  p += 1
if tmp==1:
  cnt += tmp
elif tmp>1:
  tmp += 1
  cnt += (tmp*(tmp-1))//2
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
r_list = []
g_list = []
b_list = []
r_append = r_list.append
g_append = g_list.append
b_append = b_list.append
cnt = 0
for i, j in enumerate(s):
    if j == 'R':
        r_append(i)
    if j == 'G':
        g_append(i)
    if j == 'B':
        b_append(i)
for r in r_list:
    for g in g_list:
        for b in b_list:
            if not(r * 2 == g + b or g * 2 == r + b or b * 2 == r + g):
                cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

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

dic = [0] * (10 ** 5 + 1)
for x in A:
    dic[x] += 1

for i in range(Q):
    B, C = map(int, input().split())
    dic[C] += dic[B]
    dic[B] = 0
    sum = 0
    for j, x in enumerate(dic):
        sum += j * x
    print(sum)


### FIXED CODE ###

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

heavy = [0] * (10 ** 5 + 1)
for x in A:
    heavy[x] += 1
suma = sum(A)

for i in range(Q):
    B, C = map(int, input().split())
    suma -= B * heavy[B]
    suma += C * heavy[B]
    heavy[C] += heavy[B]
    heavy[B] = 0
    print(suma)