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

n = int(input())
left = 0
right = n - 1
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while left < right:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if (mid - left + 1) % 2 == 1 and sm != sl:
        right = mid
        continue
    elif (mid - left + 1) % 2 == 0 and sm == sl:
        right = mid
    else:
        left = mid


### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

N = int(input())
a = [input() for i in range(N)]
li = []
count = 0
for i in range(N):
    li.append(sorted(a[i]))
for i in range(N):
    for k in range(1+i,N):
        if li[i] == li[k]:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input().rstrip())) for _ in range(N)]


from collections import Counter
counter = Counter(S)
answer = sum(x * (x - 1) // 2 for x in counter.values())
print(answer)
### BUGGY CODE ###

a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
    i = 2
    c = min(a,b)
  else:
    i += 1
print(len(s))

### FIXED CODE ###

a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c**0.5+1:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
  else:
    if a%i==0: a//=i
    if b%i==0: b//=i
    i += 1
  c = min(a,b)
if c!=1 and max(a,b)%c==0 and all([i==1 or c%i>0 for i in s]):
  s.append(c)
print(len(s))
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
  A, B = list(map(int,input().split()))
  l.append(A)
  r.append(B)
sum = 0
for i in range(1,n+1,1):
  flag = 1
  for j in range(m):
    if i < l[j] or i > r[j]:
      flag = 0
      break
  if flag == 1:
    sum += 1
print(sum)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
  A, B = list(map(int,input().split()))
  l.append(A)
  r.append(B)

min = 0
max = n
for i in range(m):
  if min < l[i]:
    min = l[i]
  if max > r[i]:
    max = r[i]

if max - min + 1 > 0:
  print(max - min + 1)
else:
  print(0)
### BUGGY CODE ###

def main():
    h,w=map(int,input().split())
    L=80*h*w+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    state=[[[0 for k in range(L)] for j in range(w)] for i in range(h)]

    p=x[0][0]
    state[0][0][p]=1

    for j in range(1,w):
        p=x[0][j]
        for k in range(L):
            if state[0][j-1][k]==1:
                state[0][j][k+p]=1
                state[0][j][abs(k-p)]=1

    for i in range(1,h):
        p=x[i][0]
        for k in range(L):
            if state[i-1][0][k]==1:
                state[i][0][k+p]=1
                state[i][0][abs(k-p)]=1

    for i in range(1,h):
        for j in range(1,w):
            p=x[i][j]
            for k in range(L):
                if state[i-1][j][k]==1 or state[i][j-1][k]==1:
                    state[i][j][k+p],state[i][j][abs(k-p)]=1,1



    for k in range(L):
        if state[h-1][w-1][k]==1:
            print(k)
            break
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    

    L=12800
    
    state=[[0]*w for _ in range(h)]
    delta=x[0][0]
    state[0][0]=(2**L>>delta)|(2**L<<delta)

    for j in range(1,w):
        delta=x[0][j]
        state[0][j]=(state[0][j-1]>>delta)|(state[0][j-1]<<delta)

    for i in range(1,h):
        delta=x[i][0]
        state[i][0]=(state[i-1][0]>>delta)|(state[i-1][0]<<delta)

    for i in range(1,h):
        for j in range(1,w):
            delta=x[i][j]
            state[i][j]=(state[i][j-1]>>delta)|(state[i][j-1]<<delta)
            state[i][j]|=(state[i-1][j]>>delta)|(state[i-1][j]<<delta)

    
    ans = 10**9
    for i in range(L*2):
        if state[h-1][w-1] & 1:
            ans = min(ans,abs(i-L))
        state[h-1][w-1]>>=1
    print(ans)



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

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

for i in range(n):
    ans *= a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###


n=int(input())
a=sorted(map(int,input().split()))
ans = 1

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

n,k=(map(int,input().split()))
p=list(map(int,input().split()))
c=list(map(int,input().split()))
cnt=list(range(n))
ans=-(10**10)
for i in range(n):
    num=[0]
    num11=[]
    num2=p[cnt[0]]-1
    num3=cnt[0]
    cnt.remove(cnt[0])
    for j in range(n+1):
        cnt10=c[num2]
        num.append(num[-1]+cnt10)
        num11.append(cnt10)
        if num2==num3:
            break
        cnt.remove(num2)
        num2=p[num2]-1
    lnum=len(num)-1
    for j in range(lnum):
        num.append(num[-1]+num11[j])
    if num[-1]<0 or k<lnum:
        ans2=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            for l in range(min(lnum,k)):
                ans2=max(ans2,num[j+l+1]-cnt2)
        ans=max(ans,ans2)
    else:
        ans3=-(10**10)
        ans4=0
        ans5=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            num14=k%lnum
            for l in range(lnum):
                ans3=max(ans3,num[j+l+1]-cnt2)
                if num14>l:
                    ans5=max(ans5,num[j+l+1]-cnt2)
        ans6=k//lnum
        ans=max(ans,(ans6*num[lnum])+ans5,((ans6-1)*num[lnum])+ans3)
    if len(cnt)==0:
        break
print(ans)


### FIXED CODE ###

n,k=(map(int,input().split()))
p=list(map(int,input().split()))
c=list(map(int,input().split()))
cnt=list(range(n))
ans=-(10**10)
for i in range(n):
    num=[0]
    num11=[]
    num2=p[cnt[0]]-1
    num3=cnt[0]
    cnt.remove(cnt[0])
    for j in range(n+1):
        cnt10=c[num2]
        num.append(num[-1]+cnt10)
        num11.append(cnt10)
        if num2==num3:
            break
        cnt.remove(num2)
        num2=p[num2]-1
    lnum=len(num)-1
    for j in range(lnum):
        num.append(num[-1]+num11[j])
    if num[-1]<0 or k<lnum:
        ans2=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            for l in range(min(lnum,k)):
                ans2=max(ans2,num[j+l+1]-cnt2)
        ans=max(ans,ans2)
    else:
        ans3=-(10**10)
        ans4=0
        ans5=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            num14=k%lnum
            for l in range(lnum):
                ans3=max(ans3,num[j+l+1]-cnt2)
                if num14>l:
                    ans5=max(ans5,num[j+l+1]-cnt2)
        ans6=k//lnum
        ans=max(ans,(ans6*num[lnum])+ans5,((ans6-1)*num[lnum])+ans3)
    if len(cnt)==0:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [a[j] for j in range(len(a))]

for i in range(n):
    b[i] = 0
    count = 0
    for k in b:
        count ^= k
    b[i] = a[i]
    print(count, end=' ')
print()




### FIXED CODE ###

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

count = 0
for k in a:
    count ^= k


for i in range(n):
    count ^= a[i]
    print(count, end=' ')
    count ^= a[i]
print()
### 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):
    if j > A[j]:
      number = j-i
      tall = A[i]+A[j]
      if number == tall:
        ans += 1
      
print(ans)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans= 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

import sys

x = []

max = -(10**9)

for line in sys.stdin.readlines():
  x.append(line.strip())

length = int(x[0])

x.remove(x[0])

for i in range(0, length):
  for j in range(i + 1, length):
    sa = int(x[j]) - int(x[i])
    if max < sa:
      max = sa

print max

### FIXED CODE ###

import sys

x = []

for line in sys.stdin.readlines():
  x.append(line.strip())

max = -(10**9)
min = int(x[1])

for i in range(2, int(x[0])+1):
  sa = int(x[i]) - min
  if max < sa:
    max = sa
  if min > int(x[i]):
    min = int(x[i])

  

print max
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    B,C=map(int,input().split())
    A.extend([C]*B)
A=sorted(A)[::-1]
print(sum(A[:N]))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x:-x[1])
for B,C in BC:
    A.extend([C]*B)
    if len(A)>N*2:
        break
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1)
    for i in range(1, M + 1):
        var = i ** N
        if P % var == 0:
            _max = i

    print(_max)

### FIXED CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1.0 * 1e-9)
    for i in range(1, M + 1):
        if P % (i ** N) == 0:
            _max = i

    print(_max)
### BUGGY CODE ###

from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,(0,source))
    heapq.heapify(queue)
    went = {n:0 for n in range(vertice)}

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]

        #print(v,here,now_cost,not_went,queue)
        for nw in can_go:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        link[here] = can_go - {here}
    else:
        print("INF")

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

N, X, D = map(int, input().split())

AN = X + D * (N - 1)

ans_set = set()
for k in range(N + 1):
    start = k * (2 * X + (k - 1) * D) // 2
    end = k * (2 * AN - (k - 1) * D) // 2
    if D:
        for r in range(start, end + D, D):
            ans_set.add(r)
    else:
        ans_set.add(start)

print(len(ans_set))


### FIXED CODE ###

from fractions import gcd
from collections import defaultdict

N, X, D = map(int, input().split())

if D == 0:
    if X == 0:
        ans = 1
    else:
        ans = N + 1
else:
    if D < 0:
        X = -X
        D = -D
    g = gcd(X, D)
    X //= g
    D //= g

    AN = X + D * (N - 1)

    intervals_dict = defaultdict(list)
    for k in range(N + 1):
        start = k * (2 * X + (k - 1) * D) // 2
        end = k * (2 * AN - (k - 1) * D) // 2

        intervals_dict[start % D].append((start // D, end // D + 1))

    ans = 0
    for k, v in intervals_dict.items():
        v.sort()

        current_stop = -float("inf")
        for start, stop in v:
            ans += max(stop, current_stop) - max(start, current_stop)
            current_stop = max(current_stop, stop)

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

n,a,b = map(int,input().split())
cnt = 0
boolean = True

while boolean:
    if n - a > 0:
        n -= a
        cnt += a
    else:
        cnt += n
        boolean = False
    if n - b > 0:
        n -= b
    else:
        boolean = False
print(cnt)

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = a*(n//(a+b))
if n % (a+b) < a:
    ans += n % (a+b)
else:
    ans += a
print(ans)
### BUGGY CODE ###

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

for _ in range(M):
  A.sort()
  A[-1] //= 2

print(sum(A))

### FIXED CODE ###

import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

print(sum(A) * (-1))
### BUGGY CODE ###

K = int(input())

X = []
s = len(str(K))
for i in range(s):
    X.append(7)

while True:
    Y = int("".join(map(str,X)))
    if Y % K == 0:
        print(len(X))
        break
    elif K % 2 == 0:
        print(-1)
        break
    else:
        X.append(7)

### FIXED CODE ###

def main():
    K = int(input())
    mod = 7

    if K % 2 == 0:
        print(-1)

    else:
        for i in range(10**7):
            if mod % K == 0:
                print(i+1)
                break
            else:
                mod = (10*mod + 7) % K
        else:
            print(-1)

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

import itertools
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		c = 0
		for party in itertools.combinations(a,i):
			d = all-2*sum(party)
			if c == 0 and d < 0 and abs(d) > ans:
				break
			ans = min(ans,abs(d))
			c = 1
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
checked_list = []       # すでに通ったことのあるリスト
throwgh_point_list = [-1 for i in range(N)]     # 経路のリスト（全探索用）

def dfs(i, current, throwgh_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        global checked_list
        # すでに考慮したことのあるリストの場合
        if throwgh_point_list in checked_list:
            return

        checked_list.append(copy.copy(throwgh_point_list))

        # 全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list)

dfs(0, 0, throwgh_point_list)
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
score = np.array([int(K) for __ in range(N)])
score_1 = np.array([1 for _mi in range(N)])

for i in range(Q):
    score -= score_1
    score[A[i]-1] = score[A[i]-1]+1
for k in range(N):
    if score[k] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = map(int, input().split())
p = k-q
l = [p]*n
for i in range(q):
    a = int(input())
    l[a-1] += 1
for k in range(n):
    print("Yes" if l[k]>0 else "No")
### BUGGY CODE ###

a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=[[0,-1]]
ans=[0 for _ in range(a)]
for i in d:
  ans[i[0]-1]=ans[i[0]-1]+i[1]
i=0
while len(f)!=0:
  i,fr=f.pop(0)
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i])



  

  
print(*ans)
    
  

  
  


### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
e=[[]for i in range(a)]

for i in range(a-1):
  c1,c2=map(int,input().split())
  e[c1-1].append(c2-1)
  e[c2-1].append(c1-1)

g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
### BUGGY CODE ###

from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	Z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		Z[i][j] += X[i][k] * Y[k][j]
	return Z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		F = [[0, 1], [1, 1]]
	return mat2_pow(F, n - 1)[1][1] % INF


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a = list(set(a))
ans, start = 1, 0

for j in range(1, M):
	if a[j] - a[j - 1] == 1:
		print(0)
		exit()

for k in range(N):
	if k in a:
		ans *= fib(k - start)
		ans %= INF
		start = k + 1
ans *= fib(N - start + 1)
print(ans % INF)


### FIXED CODE ###

from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

for i in range(len(a)):
	if a[i] - a[i - 1] == 1:
		print(0)
		exit()

for k in a:
	tmp.append(fib(k - start) % INF)
	start = k + 1

for j in tmp:
	ans *= j
	ans %= INF

ans *= fib(N - start + 1)
print(ans % INF)
### BUGGY CODE ###

def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  import collections
  chk = [find(i)*10**6+find2(i) for i in range(n)]
  
  for i in range(n):
    c = collections.Counter(chk)
    ans[i] += c[chk[i]]
  ans = list(map(str,ans))
  print(' '.join(ans))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():  
  #Union Find

  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          par[x] = find(par[x])
          return par[x]
  #xとyの属する集合の併合
  def unite(x,y):
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
          par[x] += par[y]
          par[y] = x
          return True

  def find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  dic = {}
  chk = []
  for i in range(n):
      p1 = find(i)
      p2 = find2(i)
      chk.append((p1,p2))
      if (p1,p2) in dic:
          dic[(p1,p2)] += 1
      else: 
          dic[(p1,p2)] = 1
  print(' '.join([str(dic[chk[i]]) for i in range(n)]))
  
if __name__ == '__main__':
    main()