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

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set([x])
            i >>= 1
            while i > 0:
                self.tree[i] = self.tree[i*2]|self.tree[i*2+1]
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = res|self.tree[l]
                    l += 1
                if r&1:
                    r -= 1
                    res = res|self.tree[r]
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        x = ord(S[i])-ord("a")
        seg.update(i,x)

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            b = ord(b)-ord("a")
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

### FIXED CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()
### BUGGY CODE ###

# https://drken1215.hatenablog.com/entry/2020/03/22/224200

def main():
    import sys
    input = sys.stdin.readline

    MOD = 998244353

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, a in enumerate(A, start=1):
        for j in range(S + 1):
            bf = dp[i - 1][j]
            not_opened = bf[0]
            opened = bf[1]
            closed = bf[2]

            curr = dp[i][j]

            curr[0] = (curr[0] + not_opened) % MOD
            curr[1] = (curr[1] + opened) % MOD
            curr[2] = (curr[2] + closed) % MOD

            if (nj := j + a) <= S:
                dp[i][nj][1] = (dp[i][nj][1] + not_opened * i + opened) % MOD
                dp[i][nj][2] = (dp[i][nj][2] + not_opened * i * (N - i + 1) + opened * (N - i + 1)) % MOD

    ans = dp[-1][-1][2]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
a_cnt = Counter(a)

def divisor(n):
    res = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            res.append(i)

            if i != n // i and i != 1:
                res.append(n // i)
    return res

divs = [set(divisor(a[i])) for i in range(n)]

ans = 0
memo = set()
for i in range(n):
    if a_cnt[a[i]] == 1:
        if memo & divs[i] == set():
            ans += 1

    memo.add(a[i])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for x in set(a):
    if flg[x]:
        ans += 1

    tmp = 1
    while tmp * x <= 10 ** 6:
        flg[tmp * x] = False
        tmp += 1

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

import collections

n, q = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n - 1)]
ls.sort(key=lambda x: x[0])
ls = collections.deque(ls)

ps = [0] * (n + 1)
for _ in range(q):
    p, v = map(int, input().split())
    ps[p] += v

levels = [-1] * (n + 1)
levels[1] = 0
es = []
while len(ls) > 0:
    e = ls.popleft()
    l0 = levels[e[0]]
    l1 = levels[e[1]]
    if l0 >= 0:
        levels[e[1]] = l0 + 1
        es.append(e + [l0])
    elif l1 >= 0:
        levels[e[0]] = l1 + 1
        es.append(e[::-1] + [l1])
    else:
        ls.append(e)
es.sort(key=lambda x: x[2])

for a, b, _ in es:
    ps[b] += ps[a]
print(*ps[1:])


### FIXED CODE ###

import collections
import sys

input = sys.stdin.readline

n, q = map(int, input().split())
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)

ps = [0] * (n + 1)
for _ in range(q):
    p, v = map(int, input().split())
    ps[p] += v

remaining = collections.deque([[0, 1]])
while len(remaining) > 0:
    a, b = remaining.popleft()
    ps[b] += ps[a]
    for c in es[b]:
        if c != a:
            remaining.append([b, c])
print(*ps[1:])
### BUGGY CODE ###

from math import ceil

# 入力
N = int(input())
A = [int(input()) for i in range(N)]

MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [ModInt(0) for _ in range(S + 1)]
dp[0] = ModInt(1)
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
dp2[0] = ModInt(1)

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = 2 * dp[i] + dp[i - a]
    for i in range(a - 1, -1, -1):
        dp[i] = 2 * dp[i]
    for i in range(S // 2, a - 1, -1):
        dp2[i] = dp2[i] + dp2[i - a]

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = 3**N - 3 * sum(dp[i] for i in range(ceil(S / 2), S + 1)) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)

# 出力
print(ans)


### FIXED CODE ###

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

M = 998244353

S = sum(A)
dp = [0 for _ in range(S + 1)]
dp[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % M
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % M
dp2 = [0 for _ in range(S + 1)]
dp2[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % M
s = 0
for i in range((S + 1) // 2, S + 1):
    s = (s + dp[i]) % M
ans = (3**N - 3 * s) % M
if S % 2 == 0:
    ans = (3**N - 3 * s + 3 * dp2[S // 2]) % M
print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
H = np.array(H)

dp = np.array([0]*(N+1))
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    dp[n] = np.amin(dp[np.maximum(n-k, 0)] + np.abs(H[n]-H[np.maximum(n-k, 0)]))

a = 0
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

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

import functools
import operator

N = int(input())
v = list(map(int, input().split()))
answer = functools.reduce(operator.mul, v)
answer = answer if answer <= 1000000000000000000 else -1
print(answer)

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
limit = 10 ** 18

answer = 1
if 0 in v:
  answer = 0
else:
  for i in v:
    answer = answer * i
    if answer <= limit:
      continue
    else:
      answer = -1
      break
print(answer)
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([list(map(int, input().split())) for _ in range(M)], reverse=True, key=lambda x:x[1])
cnt = 0
for B,C in BC:
    A += [C]*B
    cnt += B
    if B >= N:
        break
A = sorted(A, reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

n,m=map(int,input().split())
ans=list(map(int,input().split()))
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,reverse=True,key=lambda x:x[1])
tmp=0
for cnt,val in arr:
  ans+=[val]*cnt
  tmp+=cnt
  if tmp>=n:
    break
ans=sorted(ans,reverse=True)
print(sum(ans[:n]))
### BUGGY CODE ###

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

# 階上の計算
from math import factorial
from collections import defaultdict

def prime_decomposition(n):
  i = 2
  table = defaultdict(int)

  while i * i <= n:
    while n % i == 0:
      n /= i
      table[i] += 1
    i += 1

  if n > 1:
    table[n] += 1

  return list(table.values())


def nHr(n, r):
    return factorial(n+r-1) // (factorial(r) * factorial(n-1))


mod = 10 ** 9 + 7

ans = 1

prim_d_num = prime_decomposition(M)

for p in prim_d_num:
    ans *= nHr(p+1, N-1)

print(ans % mod)


### FIXED CODE ###

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

# 階上の計算
from math import factorial
from collections import defaultdict

def prime_decomposition(n):
  i = 2
  table = defaultdict(int)

  while i * i <= n:
    while n % i == 0:
      n /= i
      table[i] += 1
    i += 1

  if n > 1:
    table[n] += 1

  return list(table.values())


def nHr(n, r):
    return factorial(n+r-1) // (factorial(r) * factorial(n-1))


mod = 10 ** 9 + 7

ans = 1

prim_d_num = prime_decomposition(M)

for p in prim_d_num:
    ans *= nHr(p+1, N-1)

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

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


### FIXED CODE ###

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

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
# T = [ [int(j) for j in input().split()] for _ in range(N-1)]

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
R = defaultdict(list)
visited = [-1]*(N+1)
for i in range(N-1):
    x,y = map(int, input().split())
    # x,y = min(x,y), max(x,y)
    T[x] += [y]
    T[y] += [x]

# DP = defaultdict(lambda : 0 )
DP = [[0] * (N+1) for _ in range(2)]
# visited = [False] * (N+1)

root = 1
visited[root] = 1
node = root
from collections import deque
q = deque()
q.append(node)

while q:
    node = q.popleft()
    # print("node: ,", node)
    if all(visited[child]!=-1 for child in T[node]):
        continue
    for chnode in T[node]:
        if visited[chnode] == -1:
            R[node] += [chnode]
            visited[chnode] = 1
            q.append(chnode)
    
# 0 for black
# 1 for white
# print(R)

def dfs(c,n):
    if len(R[n]) == 0:
        DP[0][n] = 1
        DP[1][n] = 1
        return 1

    if c == 0:
        black = 1
        for child_n in R[n]:
            black *= dfs(1, child_n) % MOD
        DP[0][n] = black % MOD
        return black % MOD
    else:
        white = 1
        for child_n in R[n]:
            white *= dfs(0, child_n) + dfs(1, child_n) % MOD
        DP[1][n] = white % MOD
        return white % MOD

print( (dfs(0, 1) + dfs(1,1)) % MOD) 




### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
c = []
for i in range(n):
    a, b = map(int, input().split())
    c.extend([a]*b)
print(sorted(c)[k-1])


### FIXED CODE ###

n, k = map(int, input().split())
ab = []
count = 0
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.sort()
for i in range(k):
    count += ab[i][1]
    if(count >= k):
        print(ab[i][0])
        break
### BUGGY CODE ###

import math

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

B = [1] * N
B[0] = A[0]
for i in range(1, N):
    B[i] = B[i - 1] * A[i]

is_pairwise = True
for i in range(N-1):
    if math.gcd(A[i], B[-1]//B[i]) != 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

tmp = math.gcd(A[0], A[1])
for i in range(2, N):
    tmp = math.gcd(tmp, A[i])

if tmp == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
C = [0] * (10 ** 6 + 1)

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

is_pairwise = True
max_a = max(A) + 1
X = [0] * max_a
for i in range(2, max_a):
    count = 0
    for j in range(i, max_a, i):
        count += C[j]
    if count > 1:
        is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
    exit()

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])

if tmp == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
for i in range(n):
  at = a.copy()
  at.pop(i)
  print(max(at))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
amax = max(a)
amax_id = int(a.index(amax))
a.pop(amax_id)
amax2 = max(a)
for i in range(n):
  if i == amax_id:
    print(amax2)
  else:
    print(amax)
### BUGGY CODE ###

from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = [[CH+1,CW+1]]
Q = deque([[CH+1,CW+1]])
ans = 0

while P:
  P = []
  while Q:
    edge = 0
    y,x = Q.popleft()
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q.append([y+dy,x+dx])
      elif S[y+dy][x+dx]=="#":
        edge+=1
        if 2<=edge:
          edge = -1
          P.append([y,x])

  if S[DH+1][DW+1]!=".":
    print(S[DH+1][DW+1])
    exit()
  else:
    ans+=1
    for y,x in P:
      for dy,dx in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans
          Q.append([y+dy,x+dx])

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
p = [0] + 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(0,i+1):
        if j >= 1:
            dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1-p[i])
        else:
            dp[i][j] = dp[i-1][j] * (1-p[i])
            
print(sum(dp[i][n//2+1:]))

### FIXED CODE ###

n = int(input())
p = [0] + 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(0,i+1):
        if j >= 1:
            dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1-p[i])
        else:
            dp[i][j] = dp[i-1][j] * (1-p[i])
            
print(sum(dp[i][n//2+1:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
side = []
cityx.sort()
cityy.sort()
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0],cityx[i][1],cityx[i+1][1]])
    side.append([cityy[i+1][0]-cityy[i][0],cityy[i][1],cityy[i+1][1]])

side.sort()
node = [[i,[i]]for i in range(N)]
ans = 0
for cost,a,b in side:
    if node[a][0] != node[b][0]:
        ans += cost
        c,d = node[node[a][0]],node[node[b][0]]
        if len(c[1]) < len(d[1]):
            for i in c[1]:
                node[i][0] = d[0]
            d[1] = d[1] + c[1]
        else:
            for i in d[1]:
                node[i][0] = c[0]
            c[1] = d[1] + c[1]
print(ans)
            





### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

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

class Sets:
  def __init__(self):
    self.sets = []
  def get_group(self, a):
    if a < 0: return -1
    for i in range(len(self.sets)):
      if a in self.sets[i]:
        return i
    return -1
  def add_same_pair(self, a, b):
    ga = self.get_group(a)
    gb = self.get_group(b)
    if ga < 0 and gb < 0:
      self.sets.append(set([a,b]))
    elif ga == gb:
      return
    elif ga >= 0 and gb < 0:
      self.sets[ga].add(b)
    elif ga < 0 and gb >= 0:
      self.sets[gb].add(a)
    else:
      gmin = min(ga,gb)
      gmax = max(ga,gb)
      s = self.sets.pop(gmax)
      self.sets[gmin] = self.sets[gmin].union(s)
  def get_setids(self, n):
    setids = [-1 for i in range(n)]
    for setid in range(len(self.sets)):
      for e in self.sets[setid]:
        setids[e] = setid
    return setids
  def __str__(self):
    return str(self.sets)

N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
road_sets = Sets()
rail_sets = Sets()

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

road_ids = road_sets.get_setids(N)
rail_ids = rail_sets.get_setids(N)
result = [1 for i in range(N)]
combi_counts = {}
for i in range(N):
  road = road_ids[i]
  rail = rail_ids[i]
  if road < 0 or rail < 0:
    continue
  if (road,rail) in combi_counts:
    combi_counts[(road,rail)] += 1
  else:
    combi_counts[(road,rail)] = 1

for i in range(N):
  road = road_ids[i]
  rail = rail_ids[i]
  if road < 0 or rail < 0:
    continue
  result[i] = combi_counts[(road,rail)]
print ' '.join(map(str, result))

### FIXED CODE ###

from collections import Counter
N,K,L = map(int,input().split())

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

def root(a,par):
    if a == par[a]: return a
    par[a] = root(par[a],par)
    return par[a]

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))