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

import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in a:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)


### FIXED CODE ###

import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = set(a)
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in b:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])
### BUGGY CODE ###

import fractions

K = input()

Sum = 0

for A in range(int(K)):
    a = A + 1
    for B in range(int(K)):
        b = B + 1
        for C in range(int(K)):
            c = C + 1

            Sum = Sum + fractions.gcd(fractions.gcd(a, b), c)

print(Sum)

### FIXED CODE ###

import math
 
K = input()
 
Sum = 0
k = int(K)
 
for A in range(k):
    a = A + 1
    for B in range(k):
        b = B + 1
        gcd_ab = math.gcd(a, b)
        for C in range(k):
            c = C + 1
 
            Sum = Sum + math.gcd(gcd_ab, c)
 
print(Sum)
### BUGGY CODE ###

import numpy as np
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
sa = np.array(list(s))
dp = np.zeros((N,M),dtype=np.int64)
dp[0,0] = 1
m = list(range(M))
t = list(range(10))

for i in range(len(s)):
    for j in m:
        for k in t:
            if sa[i] == "?" or sa[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


print(dp[len(s),5])


### FIXED CODE ###

MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


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

from operator import mul
from functools import reduce
cnt = 1000000000000000000
N = map(int, input().split())
nums = list(map(int, input().split()))


count  = reduce(mul, nums)
if count  > cnt :
        print(-1)
else:
         print(count)

### FIXED CODE ###

#from operator import mul
#from functools import reduce
#cnt = 1000000000000000000
ans =1
N = int(input())
nums = list(map(int, input().split()))

if 0 in nums:
        print(0)
        exit()
for num in nums:
    ans *= num
    if ans > 10**18 :
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

k = int(input())

a = [9,8,7,6,5,4,3,2,1]
current_str = ''

for i in range(k):
  current_str = str(a.pop())
  candidates = []

  if current_str[-1] == "0":
    cp = current_str + "0"
    cp1 = current_str + "1"

    candidates.append(int(cp))
    candidates.append(int(cp1))
  elif current_str[-1] == "9":
    cp = current_str + "8"
    cp1 = current_str + "9"
    
    candidates.append(int(cp))
    candidates.append(int(cp1))
  else:
    cp = current_str + str(int(current_str[-1]) - 1)
    cp1 = current_str + current_str[-1]
    cp2 = current_str + str(int(current_str[-1]) + 1)

    candidates.append(int(cp))
    candidates.append(int(cp1))
    candidates.append(int(cp2))
    

  for c in candidates:
    a.insert(0, c)

print(current_str)

### FIXED CODE ###

from collections import deque

k = int(input())

a = deque([9,8,7,6,5,4,3,2,1])
current_num = 0

for i in range(k):
  current_num = a.pop()
  current_str = str(current_num)
  current_last = int(current_str[-1])

  up = ""  
  mid = current_str + str(current_last)
  down = ""

  if current_last >= 0 and current_last <= 8:
    up = current_str + str(current_last + 1)

  if current_last >= 1 and current_last <= 9:
    down = current_str + str(current_last - 1)
  
  if len(down) != 0:
    a.appendleft(down)

  a.appendleft(mid)

  if len(up) != 0:
    a.appendleft(up)

print(current_num)
### BUGGY CODE ###

import math
N = int(input())

for i in range(1,N+1,1):
    ans = 0
    for x in range(1,101,1):
        if x*2 >= i:
            break
        for y in range(1,101,1):
            if x**2+y**2 >= i:
                break
            for z in range(1,101,1):
                if x**2+y**2+z**2 >= i:
                    break
                if x**2+y**2+z**2+x*y+y*z+x*z ==i:
                    ans +=1
    print(ans)


### FIXED CODE ###

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

for x in range(1,100,1):
    for y in range(1,100,1):
        for z in range(1,100,1):
            if x**2+y**2+z**2+x*y+y*z+x*z <=N:
                ans[x**2+y**2+z**2+x*y+y*z+x*z-1] += 1

for i in ans:
    print(i)
### BUGGY CODE ###

import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=era(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])

for i in range(Q):
    left=bisect.bisect_left(like,l[i])
    right=bisect.bisect_right(like,r[i])
    print(right-left)

### FIXED CODE ###

import math
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data
    
def prime(n):
    max=int(math.sqrt(n))
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=prime(up)
like=[]

for i in range(len(s)):#O(10000*log(10000))
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):#O(100000)
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

for i in range(Q):
    print(sumli[r[i]]-sumli[l[i]-1])
### BUGGY CODE ###

# import functools
# import operator
# prod = functools.partial(functools.reduce, operator.mul)

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

score = [1 for _ in range(N)]
for i in range(K):
    for j in range(i+1):
        score[j] *= A[i]
# print(score)

# pre_score = prod(A[:K])
for i in range(K, N):
    for x in range(K):
        score[i-x] *= A[i]
    # score = prod(A[i-K+1:i+1])
    # print(score[i-K+1] , score[i-K])
    if score[i-K+1] > score[i-K]:
        print('Yes')
    else:
        print('No')
    # pre_score = score
# print(score)

### FIXED CODE ###

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

for i in range(K, N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import numpy as np
import bisect

(A,B,Q) = map(int,input().split())
inf = 10**12
s = np.empty(A+2,dtype=np.int64)
t = np.empty(B+2,dtype=np.int64)
s[0] = -inf
t[0] = -inf
s[A+1] = inf
t[B+1] = inf

for i in range(A):
    s[i+1] = int(input())
for i in range(B):
    t[i+1] = int(input())

for _ in range(Q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    q = bisect.bisect_left(t,x)
    spx = s[p] - x
    tqx = t[q] - x
    xtq1 = x - t[q-1]
    xsp1 = x - s[p-1]
    ans = min(max(spx, tqx),
              max(xsp1, xtq1),
                  spx*2 + xtq1,
                  spx + xtq1*2,
                  tqx*2 + xsp1,
                  t[q]-x + xsp1*2)
    print(ans)

### FIXED CODE ###

import numpy as np
import bisect
import sys
input = sys.stdin.readline

(A,B,Q) = map(int,input().split())
inf = 10**12
s = [0] * (A+2)
t = [0] * (B+2)
s[0] = -inf
t[0] = -inf
s[A+1] = inf
t[B+1] = inf

for i in range(A):
    s[i+1] = int(input())
for i in range(B):
    t[i+1] = int(input())

for _ in range(Q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    q = bisect.bisect_left(t,x)
    spx = s[p] - x
    tqx = t[q] - x
    xtq1 = x - t[q-1]
    xsp1 = x - s[p-1]
    ans = min(max(spx, tqx),
              max(xsp1, xtq1),
                  spx*2 + xtq1,
                  spx + xtq1*2,
                  tqx*2 + xsp1,
                  t[q]-x + xsp1*2)
    print(ans)
### BUGGY CODE ###

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

ans = 0
for x in range(1, N+1):
    p = int((A*x)/B) - A*int(x/B)
    if p<ans:
        break
    ans = p

print(ans)

    
    

### FIXED CODE ###

A, B, N = map(int, input().split())
from fractions import gcd

ans = 0

x = min(B-1, N)
p = int((A*x)/B) - A*int(x/B)

ans = p

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

def lunlunChecker(N):
    num = list(map(int,[l for l in str(N)]))
    flag = True
    for n in range(len(num)-1):
        if abs(num[n]-num[n+1]) > 1:
            flag = False
            break
    return flag
    
K = int(input())
cnt = 10
i = 10
lunlun_nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
if cnt > K:
    output = lunlun_nums.index(K) + 1
else :
    while cnt < K:
        i += 1
        if i//10 in lunlun_nums:
            if lunlunChecker(i):
                lunlun_nums.append(i)
                cnt += 1
    output = i
print(output)


### FIXED CODE ###

from collections import deque

q = deque(range(1,10))
K = int(input())

for i in range(K):
    x = q.popleft()
    r =  x % 10
    if r != 0:
        q.append((10 * x) + (r - 1))
    q.append((10 * x) + r)
    if r != 9:
        q.append((10 * x) + (r + 1))

print(x)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
K,S = map(int, input().split())
ans = 0
for x in range (0, K+1):
    for y in range (0, K+1):
        for z in range (0, K+1):
            if x+y+z == S:
                ans += 1

print(ans)

### FIXED CODE ###

# -*- coding:utf-8 -*-
K,S = map(int, input().split())
ans = 0

"""
for x in range (0, K+1):
    for y in range (0, K+1):
        for z in range (0, K+1):
            if S == x+y+z:
                ans += 1
"""

for x in range (0, K+1):
    for y in range (0, K+1):
        if 0 <= S-x-y and K >= S-x-y:
            ans += 1

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

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += A[i] * A[j]
ans %= 10**9+7
print(ans)

### FIXED CODE ###

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

A_sum = sum(A)
ans = 0
for i in range(n-1):
    A_sum -= A[i]
    ans += A[i] * A_sum
ans %= 10**9+7
print(ans)
### BUGGY CODE ###

import queue

def dijkstra(g,node_count):
    
    root = [-1] * node_count

    q = queue.Queue()
    q.put(0)
    root[0] = 0
    conf[0] = 1
    while not q.empty():

        p = q.get()
        conf[p] = 1
        for i in range(node_count):
            if conf[i] == 0 and g[p][i] > 0 and i != p:
                q.put(i)
                root[i] = p
                conf[i] = 1
                if sum(conf) == node_count:
                    break

    return root


n, m = map(int, input().split())
g = [[0] * n for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in range(n):
        if root[i] <= 0 and g[p][i] > 0:
            q.put(i)
            root[i] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break

if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])




### FIXED CODE ###

import queue
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

#print(g)

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in g[p+1]:
        if root[i-1] <= 0:
            q.put(i-1)
            root[i-1] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break


if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])
### BUGGY CODE ###

import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if 2<len(data):
    if num[0]!=num[1] and any([x%num[1]!=0 for x in data[1::]]):
        count=int(num[1]/2+1)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

### FIXED CODE ###

from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)
### BUGGY CODE ###

import math
K=int(input())

sum=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            base=math.gcd(i,j)
            sum+=math.gcd(base,k)

print(sum)

### FIXED CODE ###

import math
K=int(input())

sum=K

for i in range(1,K):
    sum+=i
    for j in range(i+1,K+1):
        for k in range(j,K+1):
            if j==k:
                base=math.gcd(i,j)
                sum+=math.gcd(base,k)*6
            else:
                base=math.gcd(i,j)
                sum+=math.gcd(base,k)*6
print(sum)
### BUGGY CODE ###

#atcoder https://atcoder.jp/contests/dp/tasks/dp_b

N, K = map(int, input().split())
h = [int(i) for i in input().split()]


dp = [0] * N
dp[0] = 0

for i in range(1, N):

    dp[i] = min(
        dp[k] + abs(h[i]-h[k]) for k in range(max(i-K,0), i)
    )

print(dp[N-1])


### FIXED CODE ###

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

	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
		)
	print(dp[N-1])
main()
### BUGGY CODE ###

import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        yet.append((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if not s[hh, ww] or cost[hh, ww] <= m + 1:
                    continue
                cost[hh, ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

N, M = map(int, input().split())
P_Y = [list(map(int, input().split())) for i in range(M)]

N_count = [[] for k in range(N)]
ans = []
for i in range(M):
    p = P_Y[i][0]
    y = P_Y[i][1]
    p_zero = str(p).zfill(6)
    N_count[p-1].append(y)
    ans.append(p_zero)

for k in range(N):
    N_count[k].sort()

for i in range(M):
    p = P_Y[i][0]
    t = N_count[p-1].index(P_Y[i][1]) + 1
    t_zero = str(t).zfill(6)
    print(ans[i]+t_zero)

### FIXED CODE ###

N, M = map(int, input().split())
P_Y_I = [list(map(int, input().split())) for i in range(M)]

for i in range(M):
    P_Y_I[i].append(i+1)

P_Y_I = sorted(P_Y_I, key=lambda x:x[1])

N_count = [0 for k in range(N)]
for i in range(M):
    p = P_Y_I[i][0]
    N_count[p-1] += 1
    P_Y_I[i][0] = str(p).zfill(6)
    P_Y_I[i][1] = str(N_count[p-1]).zfill(6)

P_Y_I = sorted(P_Y_I, key=lambda x:x[2])

for i in range(M):
    print(P_Y_I[i][0]+P_Y_I[i][1])
### BUGGY CODE ###

#!/usr/bin/env python3
import numpy as np
import itertools

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H, W, K = list(map(int, input().split()))
    S = np.ndarray([H, W])
    answer = np.inf

    for h in range(H):
        row = input()
        for w in range(W):
            S[h, w] = int(row[w])
    for n in range(H+1):
        for comb in itertools.combinations([h for h in range(1, H)], n):
            if len(comb) == 0:
                sub_S = S.sum(axis=0)
            else:
                sub_S = np.zeros([len(comb)+1, W])

                head = 0
                for h in range(H):
                    if h in comb:
                        head += 1
                    sub_S[head, :] += S[h, :]
            current_sum = np.zeros(len(comb)+1)
            num_cut = 0
            for line in sub_S.T:
                if np.any(line > K):
                    num_cut = np.inf
                    break
                if np.any(current_sum + line > K):
                    current_sum = np.zeros(len(comb)+1)
                    num_cut += 1
                current_sum += line
            if num_cut + len(comb) < answer:
                answer = num_cut + len(comb)
    print(answer)
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])
 
ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]
 
    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
 
    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue
 
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1
 
    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)
 
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]
three_hold_list = [0] *(3*N)
ans = ans = [N] * N
if K >= N :
    print(*ans)
else:
    for i in range(K):
        Accum = [0] *(3*N)
        for j in range(N):
            Accum[N+j-A[j]] += 1
            Accum[N+j+A[j]+1] -= 1
        num = 0
        for l in range(3*N):
            num += Accum[l]
            three_hold_list[l] = num
        if three_hold_list[N:2*N] == ans:
            break
        else:
            A = three_hold_list[N:2*N]
    print(*three_hold_list[N:2*N])

### FIXED CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]
three_hold_list = [0] *(3*N)
ans = ans = [N] * N
if K >= N :
    print(*ans)
else:
    for i in range(K):
        Accum = [0] *(3*N)
        for j in range(N):
            Accum[N+j-A[j]] += 1
            Accum[N+j+A[j]+1] -= 1
        num = 0
        for l in range(3*N):
            num += Accum[l]
            three_hold_list[l] = num
        if three_hold_list[N:2*N] == ans:
            break
        else:
            A = three_hold_list[N:2*N]
    print(*three_hold_list[N:2*N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def find_root(edges, edges_root, root, group, before, now):
    group.append(now)
    edges_root[now] = root
    children = edges[now]
    for child in children:
        if child != before and child not in group:
            root, edges_root, group = find_root(edges, edges_root, root, group, now, child)
    return root, edges_root, group
    
if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [[] for _ in range(N)]
    rails = [[] for _ in range(N)]
    road_roots = [None]*N
    rail_roots = [None]*N
    answer = [1]*N
        
    for i in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        roads[p].append(q)
        roads[q].append(p)
    
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        rails[r].append(s)
        rails[s].append(r)
    
    for i, r in enumerate(road_roots):
        if r is None:
            root, road_roots, group = find_root(roads,road_roots, i, [], -1, i)


    for i, r in enumerate(rail_roots):
        if r is None:
            root, rail_roots, group = find_root(rails,rail_roots, i, [], -1, i)

                
    railroads=[[rail, road] for rail, road in zip(road_roots, rail_roots)]

    for n in range(N):
        for d in range(1, N-n):
            if railroads[n] == railroads[n+d]:
                answer[n] += 1 
                answer[n+d] += 1
                
    print(' '.join(list(map(str, answer))))

### FIXED CODE ###

from collections import defaultdict
def build_tree(N, edges):
    root_list = [i for i in range(N)]
    for p, q in edges:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [None]*K
    rails = [None]*L
    for k in range(K):
        roads[k] = list(map(int, input().split()))
    for l in range(L):
        rails[l] = list(map(int, input().split()))
    
    
    '''N = 2*10**5
    L = int(N/2)
    K = int(N/2)
    roads = [None]*K
    rails = [None]*L
    for i in range(L):
        roads[i] = [2*i, 2*i+1]
    for i in range(K):
        rails[i] = [2*i, 2*i+1]'''
    
    road_roots = build_tree(N, roads)
    rail_roots = build_tree(N, rails)
    
    railroads = defaultdict(int)
    RR = []
    for n in range(N):
        rr = (get_root(road_roots, n), get_root(rail_roots, n))
        RR.append(rr)
        railroads[rr] += 1
    answer = [railroads[key] for key in RR]
    print(' '.join(map(str, answer)))