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

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

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]

    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global ans
    ans[p] = ans[pre] + sums[p]
    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


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

import queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                field[p[1]][p[0]] = p[2]
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
        cand.append(max([max(row) for row in field]))
print(max(cand))

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.put((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))
### BUGGY CODE ###

def gcd(p, q):
    while q != 0:
        r = p % q
        p = q
        q = r
    return p

output = 0
K = int(input())
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            r = gcd(i, j)
            output += gcd(r,k)
print(output)


### FIXED CODE ###

import math
output = 0
K = int(input())
for i in range(1, K+1):
    for j in range(1, K+1):
        r = math.gcd(i, j)
        for k in range(1, K+1):
            output += math.gcd(r,k)
            
print(output)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n, n), dtype=numpy.int)
  llr = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l-1, r-1] += 1
  
  cusum = numpy.zeros((n, n), dtype=numpy.int)
  cusum[0, 0] = counts[0, 0]
  for i in range(1, len(cusum)):
    cusum[i,0] = cusum[i-1, 0] + counts[i, 0]
  for i in range(1, len(cusum[0])):
    cusum[0, i] = cusum[0, i-1] + counts[0, i]
  for i in range(1, n):
    for j in range(1, n):
      cusum[i, j] = cusum[i, j-1] + cusum[i-1, j] - cusum[i-1, j-1] + counts[i, j]
          
  for _ in range(q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    
    if p-1 < 0:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n, n), dtype=numpy.int)
  llr = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l-1, r-1] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    
    if p-1 < 0:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

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

number = int(input())

result = 1
for index in range(1, number + 1):
  result = result * index


dividor = 10 ** 9 + 7
print (result % dividor)

### FIXED CODE ###

import math
  
n = int(input())
result = math.factorial(n)
  
  
dividor = 10 ** 9 + 7
print (result % dividor)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(n-2):
  fir=s[i]
  for j in range(i+1,n-1):
    sec=s[j]
    if sec==fir:
      continue
    off=j-i
    for k in range(j+1,n):
      if k-j==off:
        continue
      thir=s[k]
      if (sec!=thir)and(thir!=fir):
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
r=0
g=0
b=0
for i in range(n):
  if s[i]=="R":
    r+=1
  if s[i]=="G":
    g+=1 
  if s[i]=="B":
    b+=1 
ans=r*g*b
for i in range(n-2):
  for j in range(i+1,n-1):
    k=2*j-i
    if k>=n:
      continue
    if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

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,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    t=(10**(l-i-2))%13
    for j in range(13):
        if u!="?":
            k=(j+int(u)*t)%13
            dp[i+1][k]+=dp[i][j]
        
        else:
            for g in range(10):
                k=(j+g*t)%13
                dp[i+1][k]+=dp[i][j]
    for d in dp[i+1]:
        d%=mod
                
            
#print(dp)
print(dp[l-1][5]%mod)

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

n,m = map(int,input().split())
price_list = sorted(list(map(int,input().split())),reverse = True)
for i in range(m):
    n = max(price_list)
    price_list.remove(n)
    price_list.append(n//2)
print(sum(price_list))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
price_list =list(map(lambda x : -int(x),input().split()))
heapq.heapify(price_list)

for i in range(m):
    dis = heapq.heappop(price_list)
    heapq.heappush(price_list, -(-dis//2)) 
print(-1*sum(price_list))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A1=sorted(A)
order=[]
value=[]
cmb=[]
cnt=1

for i in range(1,N):
    if A1[i]!=A1[i-1]:
        order.append(A1[i-1])
        value.append(cnt)
        cmb.append((cnt*(cnt-1)//2))
        cnt=1
        if i==N-1:
            order.append(A1[i])
            value.append(1)
            cmb.append(0)
    else:
        cnt+=1
        if i==N-1:
            order.append(A1[i])
            value.append(cnt)
            cmb.append(cnt*(cnt-1)//2)
SUM=sum(cmb)

for j in range(N):
    n=order.index(A[j])
    v=value[n]
    print(SUM-cmb[n]+(v-1)*(v-2)//2)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A1=sorted(A)
cnt=[0 for _ in range(N+1)] #cnt_table[i]: 数字iの要素の個数

for i in range(N):
    cnt[A[i]]+=1

cmb=[cnt[k]*(cnt[k]-1)//2 for k in range(N+1)]
SUM=sum(cmb)

for j in range(N):
    n=A[j]
    v=cnt[A[j]]
    print(SUM-cmb[n]+(v-1)*(v-2)//2)
### BUGGY CODE ###

import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in a:
  cnt=0
  while i&1==0:
    cnt+=1
    i>>1
  b.append(cnt)
if len(set(b))!=1:
  print(0)
  exit()
for i in range(n):
  a[i]//=2
d=lcm(*a)
print((m+d)//2//d)

### FIXED CODE ###

from math import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def evencount(n):
  cnt=0
  while n%2==0:
    cnt+=1
    n//=2
  return cnt
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
if all(evencount(i) == evencount(a[0]) for i in a):
  d=lcm(*a)
  print((m+d)//2//d)
else:print(0)
### BUGGY CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = [[0 for i in range(s + 1)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(n, 0, -1):
        for k in range(s, -1, -1):
            if k >= a[i-1]:
                dp[j][k] = (dp[j-1][k-a[i-1]] + dp[j][k]) % mod
            else:
                dp[j][k] = dp[j][k]
dp2 = [dp[i][s] for i in range(n + 1)]
ans = 0
for i in range(n + 1):
    temp = dp2[i] * pow(2, n - i, mod)
    ans += temp
    ans %= mod
print(ans)


### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

temp = [1] + [0] * s
for i in range(n):
    temp2 = [0] * (s + 1)
    for j in range(s + 1):
        temp2[j] += temp[j] * 2
        temp2[j] %= mod
    for j in range(s + 1 - a[i]):
        temp2[j + a[i]] += temp[j]
        temp2[j + a[i]] %= mod
    temp = temp2
print(temp[s])
### BUGGY CODE ###

takahashi, aoki, kurikaeshi = input().split()
t,a = int(takahashi),int(aoki)
for i in range(int(kurikaeshi)):
  if t >= 1:
     t -= 1
  elif a >= 1:
    a -= 1
print(t,a)


### FIXED CODE ###

t,a,k = map(int, input().split())
T = max(t - k,0)
k-=t-T
A = max(a - k,0)
print(T,A)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    for a, b in ab[j:]:
        if a > i:
            break
        heappush(hq, -b)
        j += 1
    if hq:
        result -= heappop(hq)
print(result)

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    while j < n and ab[j][0] <= i:
        heappush(hq, -ab[j][1])
        j += 1
    if hq:
        result -= heappop(hq)
print(result)
### BUGGY CODE ###

import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7

if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]

ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)

B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
#  ansB %= MOD

C1=A[0:K]
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))

ansC = 1
for a in C1[0:K]:
  ansC *= a
#  ansC %= MOD

print(max(ansB,ansC)%MOD)

### FIXED CODE ###

import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)
#print(Bp[-1],B2[0])
B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD
#print(Bm[-1],B2[-1])
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD
#print(B1,C1)
#print(ansB,ansC)
BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
#print(ansBB1,ansBB2)
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()
#print(B2[0]/Bp[-1],B2[-1]/Bm[-1])
#print(Bp[-1]*B2[-1],Bm[0]*B2[0])

#print(abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0]))
#print(ansB,ansC)
if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)
### BUGGY CODE ###

n = int(input())
L = [int(i) for i in input().split()]
out = 0

for i in range(n):
  temp = 0
  for j in range(i,n-1):
    if L[j] >= L[j+1]:
      temp += 1
    else:
      break
  if temp > out:
    out = temp
print(out)

### FIXED CODE ###

import numpy as np

n = int(input())
L = np.array([int(i) for i in input().split()])
LL = np.roll(L, -1)
LL[-1] = pow(10,9)+1
LL = L >= LL

tindex = -1
out = 0
for i in range(n):
  if LL[i] == False:
    if (i-tindex) > out:
      out = i-tindex-1
    tindex = i
print(out)
### BUGGY CODE ###

# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]
    
    if j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '#' in line:
            isExact = 'Impossible'
            break

print(isExact)

### FIXED CODE ###

# AGC 007: A – Shik and Stone
h, w = [int(s) for s in input().split()]
a = [input() for _ in range(h)]

the_number_of_stones = 0

for i in range(h):
    the_number_of_stones += a[i].count('#')

print('Possible' if the_number_of_stones == h + w - 1 else 'Impossible')
### BUGGY CODE ###

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

for i in range(M):
    b, c=map(int, input().split())
    
    if c>k[0]:
        for j in range(b):
            if c-k[j]>0:
                k[j]=c
            else:
                break
    k.sort()

print(sum(k))

### FIXED CODE ###

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

card=[]

for i in range(M):
    b, c=map(int, input().split())
    card.append((c, b))

card.sort(reverse=True)
k=0
for c, b in card:
    while k < N and b > 0:
        if a[k]<c:
            a[k]=c
            b-=1
        k+=1

print(sum(a))
### BUGGY CODE ###

N = int(raw_input())
L = map(int, raw_input().split())

L.sort(reverse=True)

sum = 0

for i in range(N):
    a = L[i]

    for j in range(i+1,N):
        b = L[j]
        if 2*b < a:
            break

        for k in range(j+1,N):
            c = L[k]
            if a < b+c:
                sum = sum + 1
            else:
                break

print sum

### FIXED CODE ###

import bisect

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

    ans = 0
    L = sorted(L)

    for i in range(N):
        a = L[i]
        for j in range(i+1, N):
            b = L[j]
            target = a+b

            c = bisect.bisect_left(L, target)
            ans = ans + (c-j-1)

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

#!/usr/bin/env python3
from bisect import insort_left
from collections import deque
from math import ceil

n, k = map(int, input().split())
a = [[i, 1] for i in map(int, input().split())]
A = deque(sorted(a))
while k > 0:
    q, c = A.pop()
    insort_left(A, [q * c / (c + 1), c + 1])
    k -= 1
print(ceil(A[-1][0]))


### FIXED CODE ###

#!/usr/bin/env python3
from bisect import bisect_left

n, k = map(int, input().split())
*a, = map(int, input().split())
def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    return sum(-(-i // arg) - 1 for i in a) <= k


def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(meguru_bisect(0, max(a)))
### BUGGY CODE ###

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

count=0
for i in range(k+1):
  if i+2*k-s >=0:
    for j in range(k+1):
      if (s-(i+j)<=k)&(s-(i+j)>=0):
        count+=1
print(count)

### FIXED CODE ###

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

count=0
for i in range(k+1):
  for j in range(k+1):
    if (s-(i+j)<=k)&(s-(i+j)>=0):
      count+=1
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
    
#dics min max
dicsmin = min(a)
dicsmax = max(a)

counter = []
for i in range(dicsmin,dicsmax + 1):
    xcount = 0
    x = i
    xcount = a.count(x) + a.count(x-1) + a.count(x + 1)
    counter.append(xcount)

print(max(counter))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
aa = []
amax = max(a) + 100


for i in range(amax + 1):
    aa.append(0)

for i in range(len(a)):
    aa[a[i]] = aa[a[i]] + 1
    
kouho = 1    
for j in range(len(aa) - 2):
    if kouho < aa[j] + aa[j + 1] + aa[j + 2]:
        kouho = aa[j] + aa[j + 1] + aa[j + 2]

print(kouho)
### BUGGY CODE ###

import sys, time
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E, num):
    V[i] = num
    for j in [x for x in E[i] if V[x] == 0]:
        if V[j] > 0:
            continue
        V = dfs(j, V, E, num)
    return V

n, k, l = map(int, input().split())
Er = defaultdict(list)
for i in range(k):
    p, q = map(int, input().split())
    Er[p].append(q)
    Er[q].append(p)
Et = defaultdict(list)
for i in range(l):
    r, s = map(int, input().split())
    Et[r].append(s)
    Et[s].append(r)

#start = time.time()
Vr_group = [None]
Vr = [0 for _ in range(n + 1)]
j = 1
for i in range(1, n + 1):
    if Vr[i] > 0:
        continue
    Vr = dfs(i, Vr, Er, j)
    Vr_group.append({t for t in range(1, n + 1) if Vr[t] == j})
    j += 1
#print(time.time() - start)

#start = time.time()
Vt_group = [None]
Vt = [0 for _ in range(n + 1)]
j = 1
for i in range(1, n + 1):
    if Vt[i] > 0:
        continue
    Vt = dfs(i, Vt, Et, j)
    Vt_group.append({t for t in range(1, n + 1) if Vt[t] == j})
    j += 1
#print(time.time() - start)

#start = time.time()
W = [[0 for j in range(len(Vt_group))] for i in range(len(Vr_group))]
for i in range(1, len(Vr_group)):
    for j in range(1, len(Vt_group)):
        W[i][j] = len(Vr_group[i] & Vt_group[j])
ans = []
for i in range(1, n + 1):
    ans.append(W[Vr[i]][Vt[i]])
#print(time.time() - start)
print(' '.join([str(x) for x in ans]))


### FIXED CODE ###

import sys
from collections import Counter

class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0 for i in range(n + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

sys.setrecursionlimit(10 ** 5 + 1)

n, k, l = map(int, input().split())
Ur = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    Ur.union(p, q)

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [(Ur.find(i + 1), Ut.find(i + 1)) for i in range(n)]
c = Counter(x)
ans = []
for i in range(n):
    ans.append(c[x[i]])
print(' '.join([str(a) for a in ans]))