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

h, w = list(map(int, input().split()))
s = []
s.append("".join(["#" for i in range(w + 2)]))
for i in range(h):
    s.append("#" + input().strip() + "#")
s.append("".join(["#" for i in range(w + 2)]))

reps = []
for i in range(h + 2):
    for j in range(w + 2):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for start in reps:
    for goal in reps:
        visits = [[-1 for i in range(w + 2)] for j in range(h + 2)]
        visits[goal[0]][goal[1]] = 1
        queue = [start]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    tmp_queue.append([(now[0] + 1), now[1]])
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    tmp_queue.append([now[0], (now[1] + 1)])
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    tmp_queue.append([(now[0] - 1), now[1]])
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))


### FIXED CODE ###

from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                    visited[now[0] + 1][now[1]] = True
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                    visited[now[0]][now[1] + 1] = True
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                    visited[now[0] - 1][now[1]] = True
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))
                    visited[now[0]][now[1] - 1] = True

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

def main():
    from collections import defaultdict

    N, P = map(int, input().split())
    S = (int(x) % P for x in input())

    dp = defaultdict(int)
    ndp = defaultdict(int)

    ret = 0
    for x in S:
        ndp[x] += 1
        for rest in dp.keys():
            next_rest = (rest * 10 + x) % P
            ndp[next_rest] += dp[rest]
        ret += ndp[0]
        dp = ndp
        ndp = defaultdict(int)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


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

# -*- coding: utf-8 -*-
# abc 127 d
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
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 ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
  b,c = map(int,input().split())
  a=[c if i==b else i for i in a]
  print(sum(a))

### FIXED CODE ###

from collections import Counter
n=input()
a=list(map(int,input().split()))
b=Counter(a)
n=int(input())
ans=sum(a)
for i in range(n):
    x,y=map(int,input().split())
    ans+=b[x]*(y-x)
    print(ans)
    b[y]+=b[x]
    b[x]=0
### BUGGY CODE ###

N, C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                for clr in mod[i]:
                    sm += d[clr-1][li[i]]

            ans = min(ans, sm)

print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

from collections import Counter

c = []
for i in range(3):
    c.append(Counter(mod[i]))

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                counter = c[i]
                for k, v in counter.items():
                    sm += d[k-1][li[i]] * v

            ans = min(ans, sm)

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

[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))
salist=[alist[1]-alist[0]]
for i in range(1,n-1):
	saisho=min(alist[0:i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)

### FIXED CODE ###

[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))
salist=[alist[1]-alist[0]]
saisho=min(alist[0],alist[1])
for i in range(1,n-1):
	saisho=min(saisho,alist[i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)
### BUGGY CODE ###

n = int(input())
l = []
already = []
next = 1
c = 0
for i in range(n):
  a = int(input())
  l.append(a)
while True:
  next = l[next-1]
  c += 1
  if next == 2:
    print(c)
    break
  elif next in already:
    print(-1)
    break
  already.append(next)

### FIXED CODE ###

n = int(input())
l = [0 for _ in range(n)]
already = set()
next = 1
c = 0
for i in range(n):
  a = int(input())
  l[i] = a
while c <= n:
  next = l[next-1]
  c += 1
  if next == 2:
    print(c)
    break
  elif next in already:
    print(-1)
    break
  already.add(next)
### BUGGY CODE ###

def build_cost_table(n):
    ret = [[-1] * (n + 1) for _ in range(n + 1)]  # J字にコスト-1の区画を設ける
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            if ~ret[r][c]: continue
            dc = min(c, n - 1 - c)
            ret[r][c] = ret[n - 1 - r][c] = ret[n - 1 - r][n - 1 - c] = ret[r][n - 1 - c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    def next_coods(r, c):
        # if r != 0:
        yield r - 1, c
        # if c != 0:
        yield r, c - 1
        # if r != N - 1:
        yield r + 1, c
        # if c != N - 1:
        yield r, c + 1

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in next_coods(r, c):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [1] * (N ** 2)  # 着席

    ans = 0
    for pi in p:
        hpi = H[pi]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


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

n=int(input())
s=input()
a=set()
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            b=s[i]+s[j]+s[k]
            a=a|{b}
print(len(a))

### FIXED CODE ###

n=int(input())
s=input()
a,b,c=[],[],[]
ans=0
for i in range(n):
  if s[i] not in a:
    a.append(s[i])
    b=[]
    for j in range(i+1,n):
      if s[j] not in b:
        b.append(s[j])
        c=[]
        for k in range(j+1,n):
          if s[k] not in c:
            c.append(s[k])
            ans+=1
print(ans)
### BUGGY CODE ###

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

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

ans = N
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    su = 0
    amax = 0
    cnt = 0
    for x in R[j]:
      amax = max(amax, DP[x] + 1)
      su += DP[x] + 1
      cnt += 1
    DP[j] = su / cnt
    if i == j and cnt != 1:
      DP[j] = (su - amax) / (cnt - 1)

  ans = min(ans, DP[0])
 
print(ans)

### FIXED CODE ###

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

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)
### BUGGY CODE ###

N = int(input())

print(sum(i % (i + 1) for i in range(1, N)))


### FIXED CODE ###

N = int(input())

print(int(N * (N - 1) // 2))
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = [ni() for _ in range(n)]

suma = sum(a)
MOD = 998244353

dp_rgb = [[0]*(suma+1) for _ in range(n+1)]
dp_gb = [[0]*(suma+1) for _ in range(n+1)]

dp_rgb[0][0] = 1
dp_gb[0][0] = 1

for i, ai in enumerate(a):
    for sm in range(suma+1):
        if sm + ai <= suma:
            dp_rgb[i+1][sm+ai] += dp_rgb[i][sm] % MOD
            dp_gb[i+1][sm+ai] += dp_gb[i][sm] % MOD
            
        dp_rgb[i+1][sm] += 2 * dp_rgb[i][sm] % MOD
        dp_gb[i+1][sm] += dp_gb[i][sm] % MOD
        
ng = 3 * sum(dp_rgb[n][-(-suma//2):]) % MOD
ok = 0 if suma%2 else 3*dp_gb[n][suma//2] % MOD

print((pow(3,n,MOD) - ng + ok) % MOD)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = [ni() for _ in range(n)]

suma = sum(a)
MOD = 998244353

dp_rgb = [[0]*(suma+1) for _ in range(n+1)]
dp_gb = [[0]*(suma+1) for _ in range(n+1)]

dp_rgb[0][0] = 1
dp_gb[0][0] = 1

for i, ai in enumerate(a):
    for sm in range(suma+1):
        if sm + ai <= suma:
            dp_rgb[i+1][sm+ai] += dp_rgb[i][sm] % MOD
            dp_gb[i+1][sm+ai] += dp_gb[i][sm] % MOD
            
        dp_rgb[i+1][sm] += 2 * dp_rgb[i][sm] % MOD
        dp_gb[i+1][sm] += dp_gb[i][sm] % MOD
        
ng = 3 * sum(dp_rgb[n][-(-suma//2):]) % MOD
ok = 0 if suma%2 else 3*dp_gb[n][suma//2] % MOD

print((pow(3,n,MOD) - ng + ok) % MOD)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]!=0): return False
    if np.any(mask[a[1]]!=1): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]): return False
    if not(np.all(mask[a[1]])): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
ans = 1
for a in A:
    ans *= a
print(-1 if ans > 10 ** 18 else ans)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

N=int(input())

import sys

for h in range(1,3501):
    for n in range(1,3501):
        a=(h*n*N)
        b=(4*h*n-(n+h)*N)
        if b==0:
            continue

        w=a/b
        #w=int(w)

        #if w<h:
        #    break

        #print(n,w)
        if a%b==0:
            if N*(n*w+h*w+h*n)!=4*n*w*h:
                continue
            #print(w)
            if w>0:
                w=int(w)
                print(h,n,w)
                '''

                print(4/N)
                print(1/h+1/n+1/w)
                print(a,b)
                print(a/b)
                '''
                sys.exit()


### FIXED CODE ###

N=int(input())

import sys

for h in range(1,3501):
    for n in range(h,3501):
        a=(h*n*N)
        b=(4*h*n-(n+h)*N)
        if b==0:
            continue

        
        #w=int(w)

        #if w<h:
        #    break

        #print(h,n,w)
        #print(a,b)
        if a%b==0:
            w = a/b
            if N*(n*w+h*w+h*n)!=4*n*w*h:
                continue
            #print(w)
            if w>0:
                w=int(w)
                print(h,n,w)
                '''

                print(4/N)
                print(1/h+1/n+1/w)
                print(a,b)
                print(a/b)
                '''
                sys.exit()
### BUGGY CODE ###

import sys,itertools
input=sys.stdin.readline
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
distance=[[INF]*n for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   distance[a-1][b-1]=c
   distance[b-1][a-1]=c

for i in range(n):
   for j in range(n):
       for k in range(n):
           distance[j][k]=min(distance[j][k],distance[j][i]+distance[i][k])

ans=INF
for j in itertools.permutations(range(r)):
   cnt=0
   for k in range(r-1):
      cnt+=distance[j[k]-1][j[k+1]-1]
   ans=min(ans,cnt)

print(ans)

### FIXED CODE ###

import sys,itertools
input=sys.stdin.readline
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
distance=[[INF]*n for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   distance[a-1][b-1]=c
   distance[b-1][a-1]=c

for i in range(n):
   for j in range(n):
       for k in range(n):
           distance[j][k]=min(distance[j][k],distance[j][i]+distance[i][k])

ans=INF
for p in itertools.permutations(R):
   cnt=0
   for q in range(r-1):
      cnt+=distance[p[q]-1][p[q+1]-1]
   ans=min(ans,cnt)

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

n = int(input())
a = [int(x) for x in input().split()]

ans = 0
for i in range(n-1):
    for j in range(n-1-i):
        hoge = a[i]*a[i+1+j]
        while hoge >= 1000000007:
            hoge = hoge - 1000000007
        ans = ans + hoge
        if ans >= 1000000007:
            ans = ans - 1000000007
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

s = sum(a)
ans = 0
mod = 10 ** 9 + 7

for i in range(n-1):
    s -= a[i]
    ans += a[i] * s % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
ans = h[-1]
for i in range(n-k+1):
    trees = h[i:i+k]
    ans = min(
        ans,
        max(trees) - min(trees)
    )
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
h_max = np.array(h[k-1:])
h_min = np.array(h[:-k+1])
print(min(h_max - h_min))
### BUGGY CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=1<<~-k
for i in r(min(n-1,k)):a-=f[k-1]*pow((f[i]*f[k-1-i])%p,-1,p)
print(a%p)

### FIXED CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=0
for i in r(n-1,k):a+=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    #根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
## 
# N個の都市
# K本の道路
# L本の鉄道
N, K, L = map(int, input().split())

# N都市を初期の要素数とする
# 道路と鉄道をそれぞれ別のunion-find木として表現する
uf_p = UnionFind(N)
uf_t = UnionFind(N)

# 道路の木
for _ in range(K):
    x,y = map(int, input().split())
    uf_p.union(x-1,y-1)

# 鉄道の木
for _ in range(L):
    x,y = map(int, input().split())
    uf_t.union(x-1,y-1)

    
# 出力結果を整形
result = []
for i in range(N):
    # 道路と鉄道の両方繋がっている件数をand条件で抽出する
    result.append(str(len(set(uf_p.members(i)) & set(uf_t.members(i)))))
    
print(" ".join(result))


### FIXED CODE ###

# union-find木
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



N, K, L = map(int, input().split())

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

print(' '.join(map(str, ans)))