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

from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    # BFS
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  # from_node, to_node, color
    explored_nodes = [0]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored_nodes.append(n[1])
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if next_to_node in explored_nodes:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    # print answer
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    # BFS
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  # from_node, to_node, color
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored[n[1]] = 1
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if explored[next_to_node] == 1:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    # print answer
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


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

n,m= map(int,input().split())
AA = list(map(int,input().split()))
A = [[AA[i],1] for i in range(n)]
for _ in range(m):
  b,c = map(int,input().split())
  A += [[c,b]]
A.sort()
A.reverse()
rest = n
score = 0
while True:
  C = A[0][0]
  B = A[0][1]
  score += B * C
  rest -= B
  del A[0]
  if rest < 0:
    score += rest * C
    break
print(score)

### FIXED CODE ###

n,m= map(int,input().split())
AA = list(map(int,input().split()))
A = [(AA[i],1) for i in range(n)]
for _ in range(m):
  b,c = map(int,input().split())
  A += [(c,b)]
A.sort()
A.reverse()
rest = n
score = 0
for (cc,bb) in A:
  use = min(bb,rest)
  rest -= use
  score += use*cc
print(score)
### BUGGY CODE ###

from itertools import combinations
N=int(input())
A=list(map(int,input().split()))
cnt=0
for a in combinations(A,3):
    l=a[0]
    m=a[1]
    n=a[2]
    if l<m+n and m<l+n and n<l+m:
        cnt+=1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
A=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1):
    for j in range(i+1,N):
        a=bisect_left(A,A[i]+A[j])
        if j<a:
            cnt+=a-j-1
print(cnt)
### BUGGY CODE ###

n = int(input())
v = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

max_v_minus_c = 0

for i in range(2**n):
    flugs = bin(i)[2:].zfill(n)
    sum_v = 0
    sum_c = 0
    j = 0
    for flug in str(flugs):
        if flug == '1':
            sum_v += v[j]
            sum_c += c[j]
        j += 1

    if (max_v_minus_c < sum_v - sum_c):
        max_v_minus_c = sum_v - sum_c

print(max_v_minus_c)


### FIXED CODE ###

n = int(input())
v_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]

b_list = [v - c for (v, c) in zip(v_list, c_list)]
print(sum([b for b in b_list if b > 0]))
### BUGGY CODE ###

n,q=map(int,input().split())
S=input()
L=[]
for i in range(n):
    a=S[:i+1].count('AC')
    L.append(a)
for j in range(q):
    s,e=map(int,input().split())
    print(L[e-1]-L[s-1])

### FIXED CODE ###

n,q=map(int,input().split())
S=input()
L=[0]
c=0
for i in range(n-1):
    if S[i:i+2]=='AC':
        c+=1    
    L.append(c)
for j in range(q):
    s,e=map(int,input().split())
    print(L[e-1]-L[s-1])
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if s == x + y + z:
                cnt += 1

print(cnt)


### FIXED CODE ###

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

cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
R = []
G = []
B = []


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)

for i in R:
    for j in G:
        for k in B:
            a = [i,j,k]
            a.sort()
            if a[2] - a[1] == a[1] - a[0]:
                continue
            ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0
R = []
G = []
B = []


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)

ans = len(R) * len(G) * len(B)


for i in range(0,n-2):
    for j in range(i+1,n-1):
        k = j + ( j -i )
        if k < n:
            if s[i] != s[j] and s[k] != s[j] and s[i] != s[k]:
                ans -= 1


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

N = int(input())
A = list(map(int,input().split()))
lst = [0 for i in range(60)]
q = 0
for i in A:
    a = list(str(format(i, '08b')))
    a.reverse()
    for j in range(len(a)):
        lst[j]+=int(a[j])
for i in range(60):
    k = lst[i]
    l = k*(k-1)
    q+=(2**i)*l
p = sum(A)*(N-1)
print((p-q)%((10**9)+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
cnt = [0 for _ in range(60)]
for a in A:
    for i in range(60):
        cnt[i] += a & 1
        a >>= 1
cnt = [x * (N - x) % mod for x in cnt]
power = 1
ans = 0
for i in range(60):
    ans += power * cnt[i]
    power *= 2
    power %= mod
ans %= mod
print(ans)
### BUGGY CODE ###

import math

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

for i in reversed(range(b)):
    if i<=n:
        print(math.floor(a*i/b))
        break



### FIXED CODE ###

import math

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

# for i in reversed(range(b)):
#     if i<=n:
#         print(math.floor(a*i/b))
#         break

if b <= n:
    print(math.floor(a*(b-1)/b))
else:
    print(math.floor(a*n/b))
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = 0

for i in range(N):
    tmp_ans = 0
    for j in range(i, N-1):
        if (H[j] >= H[j+1]):
            tmp_ans += 1
        else:
            break
    ans = max(ans, tmp_ans)
    
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = [0]

for i in range(0, len(H)-1):
    if (H[i] >= H[i+1]):
        ans.append(ans[i]+1)
    else:
        ans.append(0)

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

#!/usr/bin/env python
# coding: utf-8

# In[12]:


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


# In[13]:


for m in range(M):
    idx = A.index(max(A))
    A[idx] /= 2
ans = sum([x//1 for x in A])
print(int(ans))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[18]:


import heapq


# In[23]:


N,M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))


# In[24]:


heapq.heapify(A)
for m in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, -(-tmp//2))
print(-sum(A))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

flg = [False]*(n-1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        flg[i] = True
        
for i in range(q):
    l, r = map(int, input().split())
    print(sum(flg[l-1:r-1]))

### FIXED CODE ###

import copy

n, q = map(int, input().split())
s = input()

cnt = [0]
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt.append(cnt[-1] + 1)
    else:
        cnt.append(cnt[-1])

for i in range(q):
    l, r = map(int, input().split())
    print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

N = int(input())
T = [0]*N

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



def A(j, A):

	for k in range(N):

		if(j % A[k] > 0):
			break

		elif(k == N - 1):
			return 1

	return 0


j = 1

while(True):

	if(A(j, T) == 1):
		print(j)
		break

	j += 1



### FIXED CODE ###

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

N = int(input())
T = [0]*N

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


#a, bの最大公約数を求める
def gcd(a, b):
	r = max(a, b) % min(a, b)
	


	if (r == 0):
		return min(a, b)

	else:
		return gcd(r, min(a, b))


#a, bの最小公倍数を求める
def lcm(a, b):
	return a * b // gcd(a, b)



#リストTの全要素の最小公倍数を求める
def LCM(T):
	l = len(T)



	if(l == 1):
		return T[0]

	elif(l == 2):
		return lcm(T[0], T[1])



	T1, T2 = [], []

	for i in range(l // 2):
		T1.append(T[i])

	for j in range(l - l // 2):
		T2.append(T[j + l // 2])



	return lcm(LCM(T1), LCM(T2))



print(LCM(T))
### BUGGY CODE ###

N = int(input())
P = list(map(float,input().split()))

dp = [0] * (N + 1)
dp[0] = 1

for i in range(len(P)):
  for j in range(len(dp) - 1, -1, -1):
    if j != 0:
      dp[j] = dp[j] * (1 - P[i]) + dp[j - 1] * P[i]
    else:
      dp[j] = dp[j] * (1 - P[i])
      
ans = 0
for i in range(N // 2 + 1, len(dp)):
  ans += dp[i]
  
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float,input().split()))

dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1

for i in range(len(P)):
  for j in range(i + 2):
    if j - 1 >= 0:
      dp[i + 1][j] = dp[i][j] * (1 - P[i]) + dp[i][j - 1] * P[i]
    else:
      dp[i + 1][j] = dp[i][j] * (1 - P[i])
  
ans = 0
for i in range(N // 2 + 1, len(dp)):
  ans += dp[N][i]
  
print(ans)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

lcm = 1
for i,a in enumerate(As):
    lcm_tmp = lcm
    gcd_now = gcd(lcm_tmp,a)
    lcm = lcm_tmp*a//gcd_now

mod = 10**9+7
ans = 0
for a in As:
    ans += (lcm//a)
    ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

a,b = map(int,input().split())
for i in range(1000000000):
    if abs(a-i)==abs(b-i):
        print(i)
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

a,b = map(int,input().split())
if (a-b)%2==0:
    print(int((a+b)/2))
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(29):
    res = 0
    bit = 1<<i
    p = bit
    q = p*2
    r = p*3
    s = p*4
    C = [b&(q-1) for b in B]
    C.sort()
    for a in A:
        a&=q-1
        j = bisect.bisect_left(C, p-a)
        k = bisect.bisect_left(C, q-a)
        res+=(k-j)
        j = bisect.bisect_left(C, r-a)
        k = bisect.bisect_left(C, s-a)
        res+=(k-j)
    if res%2 == 1:
        ans+=bit
print(ans)






### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(), dtype = np.int32)
B = np.array(input().split(), dtype = np.int32)
ans = 0
for i in range(29)[::-1]:
    res = 0
    p = 1<<i
    A&=(p*2-1)
    B&=(p*2-1)
    B.sort()
    i, j, k = [np.searchsorted(B, t-A).sum() for t in [p, p*2, p*3]]
    res = (i+k-j)
    if (N-res)%2:
        ans+=p
print(ans)
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    a, b = [int(_) for _ in input().split()]
    diff = b - a

    tower = 0
    ts = []
    for add in range(1, 1000):
        tower += add
        ts.append(tower)

    for snow in range(1, 499951):
        if a + snow in ts:
            if b + snow == ts[ts.index(a + snow) + 1]:
                print(snow)
                break

main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    a, b = [int(_) for _ in input().split()]
    diff = b - a

    tower = 0
    ts = []
    for add in range(1, 1000):
        tower += add
        ts.append(tower)

    print(ts[diff-2] - a)

main()
### BUGGY CODE ###

_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = 0
while True:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            ns.append((i-1, j))
        if a[i+1][j]:
            ns.append((i+1, j))
        if a[i][j-1]:
            ns.append((i, j-1))
        if a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

#D問題

#warshall_floyd法
def warshall_floyd(dist):
    #dist[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    return dist

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

dist = [[float("inf") for i in range(N)] for i in range(N)] 
#dist[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a,b,c = map(int,input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(N):
    dist[i][i] = 0 #自身のところに行くコストは０
dist=warshall_floyd(dist)

ever=[]
MIN=10000000
def ans_func(ever):
    global R
    global r
    global dist
    global MIN
    
    if len(ever) == R:
        if R == 2:
            kari=dist[ever[0]][ever[1]]
            MIN=min(MIN,kari)
        else:
            kari=0
            for i in range(R-1):
                kari+=dist[ever[i]][ever[i+1]]
            MIN=min(MIN,kari)
    else:
        i=0
        for i in range(R):
            if r[i]-1 in ever:
                pass
            else:
                ever.append(r[i]-1)
                ans_func(ever)
                ever.remove(r[i]-1)
    return
ans_func(ever)
print(MIN)
    

### FIXED CODE ###

#D問題

#warshall_floyd法
def warshall_floyd(dist):
    #dist[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    return dist

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

dist = [[float("inf") for i in range(N)] for i in range(N)] 
#dist[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a,b,c = map(int,input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(N):
    dist[i][i] = 0 #自身のところに行くコストは０
dist=warshall_floyd(dist)

ever=[]
MIN=100000000
def ans_func(ever):
    global R
    global r
    global dist
    global MIN
    
    if len(ever) == R:
        if R == 2:
            kari=dist[ever[0]][ever[1]]
            MIN=min(MIN,kari)
        else:
            kari=0
            for i in range(R-1):
                kari+=dist[ever[i]][ever[i+1]]
            MIN=min(MIN,kari)
    else:
        i=0
        for i in range(R):
            if r[i]-1 in ever:
                pass
            else:
                ever.append(r[i]-1)
                ans_func(ever)
                ever.remove(r[i]-1)
    return
ans_func(ever)
print(MIN)
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
k=1
for i in a:
  k*=i
if k>10**18:
  print(-1)
else:
  print(k)

### FIXED CODE ###

n=int(input())
a = list(map(int, input().split()))
k=1
if 0 in a:
  print(0)
else:
  for i in a:
    k*=i
    if k>10**18:
      break
  if k>10**18:
    print(-1)
  else:
    print(k)
### BUGGY CODE ###

from collections import defaultdict as dd    
n=int(input())
l=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if(j==0):
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict as dd    
n=int(input())
l=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if(j==0):
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
TOWN=[i for i in range(1,N+1)]

#行ったことある町リスト
d=[1]
i=0
while i<K:
  T=A[d[-1]-1]
  if T in d:
    break
  d.append(T)
  i+=1
F=d.index(T)
LOOP_TOWN=d[d.index(T):len(d)]
q=(K-F)%len(LOOP_TOWN)
print(LOOP_TOWN[q])

### FIXED CODE ###

def main():
  N,K=map(int,input().split())
  A=list(map(int,input().split()))
  n=[0]*N
  #行ったことある町リスト
  d=[1]
  for _ in range(K):
    T=A[d[-1]-1]
    if n[T-1]==1:
      break
    else:
      n[T-1]=1
    d.append(T)
  F=d.index(T)
  LOOP_TOWN=d[F:]
  q=(K-F)%len(LOOP_TOWN)
  print(LOOP_TOWN[q])

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

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    ans+=(K-i)*(((H+W)*const)%mod)+(((K-i)*i*const)%mod)*((inv*2*H*W)%mod)
    ans%=mod
ans+=K*(H+W)*const
ans%=mod
print(ans)


### FIXED CODE ###

mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
temp1=mul(H+W,mul((K*(K+1)//2)%mod,const))
const=mul(const,inv)
u=(K*(K**2-1))//6
u%=mod
temp2=mul(2*H*W,mul(u,const))
ans=(temp1+temp2)%mod
const=mul(const,H+W-1)
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

x=[0]*(10**5)
for i in range(n):
    x[i]=a.count(i+1)*(i+1)


for _ in range(q):
    b,c=map(int,input().split())
    if x[b-1]!=0:
        x[c-1]+=x[b-1]//b*c
        x[b-1]=0
        print(sum(x))
    else:
        print(sum(x))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

ans=sum(a)

x=[0]*(10**5+10)
for i in a:
    x[i]+=1


for _ in range(q):
    b,c=map(int,input().split())
    ans+=x[b]*c-x[b]*b
    print(ans)
    x[c]+=x[b]
    x[b]=0