Harryxun/stf_run huggingface dataset:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))

### FIXED CODE ###

ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)
from collections import Counter


def main():
    N = int(input())
    counter = Counter(map(int, input().split()))

    a = 0
    b = 0

    def sort_func(t):
        return t[0]
    for length, n in sorted(counter.items(),
                            key=sort_func,
                            reverse=True):
        if n < 2:
            continue
        if a == 0:
            a = length
            if n >= 4:
                b = length
                break
        else:
            b = length
            break
    print(a * b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    x, a, b = map(int, input().split())
    if abs(x - a) < abs(x - b):
        print("A")
    else:
        print("B")

if __name__ == '__main__':
    main()
A=int(input())
B=int(input())
C=int(input())
x=int(input())
s=0
for i in range(A+1):
  if x<=0: break
  else:
    for t in range(B+1):
    if x<=0: break
    elif 50*C>=x:
      s+=1
      x-=100
    else: x-=100
  x-=500
print(s) 

### FIXED CODE ###

A=int(input())
B=int(input())
C=int(input())
X=int(input())
s=0
for i in range(A+1):
  x=X-500*i
  if x<0: break
  for t in range(B+1):
    if x<0: break
    elif 50*C>=x:
      s+=1
      x-=100
    else: x-=100
print(s)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))
a, v = map(int, input()) 
b, w = map(int, input())
t = int(input()) 
if v <= w:
  print('NO') 
else:
  q = abs(a-b) / abs(v - w) 
  if abs(a-b) * t <= abs(v - w):
    print('YES') 
  else:
    print('NO') 

### FIXED CODE ###

a, v = map(int, input().split()) 
b, w = map(int, input().split())
t = int(input()) 
if v <= w:
  print('NO') 
else:
  q = abs(a-b) / abs(v - w) 
  if abs(a-b) <= abs(v - w) * t:
    print('YES') 
  else:
    print('NO')
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

if K in A:
    print("POSSIBLE")
    exit(0)

An = A.copy()
for i in range(len(A)):
    for j in range(i + 1, len(A)):
        aij = abs(A[i] - A[j])
        if aij not in An:
            An.append(aij)

if K in A:
    print("POSSIBLE")
    exit(0)

while A != An:
    A = An.copy()
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            aij = abs(A[i] - A[j])
            if aij not in An:
                An.append(aij)

    # print(A)
    # print(An)

    if K in A:
        print("POSSIBLE")
        exit(0)

if K in An:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

from fractions import gcd

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

M = max(A)
G = A[0]
for i in range(1, N):
    G = gcd(G, A[i])

if K <= M and K % G == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
a=int,input()
count=0
s=1
while True:
  if a!=1:
    a=a//2
    count+=1
    s+=2**count
  else:
    s+=2**count


### FIXED CODE ###

a=int(input())
count=0
s=0
while True:
  if a>1:
    a//=int(2)
    count+=1
    s+=2**count
  else:
    s+=1
    print(s)
    break
a, b, c = map(int, input().split(' '))
if a + b + c != 17:
  print 'NO'
elif a * b * c != 175:
  print 'NO'
else:
  print 'YES'

### FIXED CODE ###

a, b, c = map(int, input().split(' '))
if a + b + c != 17:
  print('NO')
elif a * b * c != 175:
  print('NO')
else:
  print('YES')
s = input()
k = int(input())
char = []
if len(s) == 1:
    print(1)
else:
    for i in range(len(s)):
        char.append(s[i])
    charset = set(char)
    ans = []
    for i in charset:
        for j in range(len(s)):
            if i == s[j]:
                for k in range(1, 6):
                    ans.append(s[j:j+k])
    ansset = sorted(list(set(ans)))
    print(ansset[k-1])

### FIXED CODE ###

s = input()
l = int(input())
char = []
if len(s) == 1:
    print(s)
else:
    for i in range(len(s)):
        char.append(s[i])
    charset = set(char)
    ans = []
    for i in charset:
        for j in range(len(s)):
            if i == s[j]:
                for k in range(1, 6):
                    ans.append(s[j:j+k])
    ansset = sorted(list(set(ans)))
    print(ansset[l-1])
n=int(input())
ls=[None]*n
ls2=[None]*n
for i in range(n):
  ls[i]=i+1
  ls2[i]=i+2
ls2[-1]=1
ans = 0
for i in range(n):
  ans += ls[i]%ls2[i]
print(ans)

### FIXED CODE ###

n=int(input())
print(int(n*(n-1)//2))
T = list(input())

x = 0
while len(T) != 0:
    x += sum([int(f) for f in T[::2]])

    xmax = 0
    delIdx = 0
    for i in range(len(T)):
        T_copy = T.copy()
        _tmp = T_copy.pop(i)

        _x = sum([int(f) for f in T_copy[::2]])

        if _x > xmax:
            xmax = _x
            delIdx = i

    T.pop(delIdx)

print(x)

### FIXED CODE ###

inputs = input()

H1, M1, H2, M2, K = [int(f) for f in inputs.split(" ")]

elapsedHour = H2 - H1
elapsedMin = M2 - M1

maxStudyStartTimeLength = elapsedHour * 60 + elapsedMin - K

print(maxStudyStartTimeLength)
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

# children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    # children[u-1].append(v-1)
    parents[v-1].append(u-1)

def get_f(parents, f, i):
    if i >= len(f):
        return 0
        
    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(parents, f, v) + 1)

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(n)]
    # targets = [x for y in children.values() for x in y]
    # starts = [v for v in range(n) if v not in targets]

    # print f
    for i in range(n):
        get_f(parents, f, i)

    # print f
    return max(f)

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(parents, n))


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
N = input()
R = N % 1000
if R == 0:
    print(0)
else:
    print(abs(R-1000))

### FIXED CODE ###

N = int(input())
R = N % 1000
if R == 0:
    print(0)
else:
    print(abs(R-1000))
n = int(input())
a = ''

if n == 1:
    print('a')
if n == 26:
    print('z')
else:
    while n > 0:
    if n%26 == 1:
        a += 'a'
    elif n%26 == 2:
        a += 'b'
    elif n%26 == 3:
        a += 'c'
    elif n%26 == 4:
        a += 'd'
    elif n%26 == 5:
        a += 'e'
    elif n%26 == 6:
        a += 'f'
    elif n%26 == 7:
        a += 'g'
    elif n%26 == 8:
        a += 'h'
    elif n%26 == 9:
        a += 'i'
    elif n%26 == 10:
        a += 'j'
    elif n%26 == 11:
        a += 'k'
    elif n%26 == 12:
        a += 'l'
    elif n%26 == 13:
        a += 'm'
    elif n%26 == 14:
        a += 'n'
    elif n%26 == 15:
        a += 'o'
    elif n%26 == 16:
        a += 'p'
    elif n%26 == 17:
        a += 'q'
    elif n%26 == 18:
        a += 'r'
    elif n%26 == 19:
        a += 's'
    elif n%26 == 20:
        a += 't'
    elif n%26 == 21:
        a += 'u'
    elif n%26 == 22:
        a += 'v'
    elif n%26 == 23:
        a += 'w'
    elif n%26 == 24:
        a += 'x'
    elif n%26 == 25:
        a += 'y'
    elif n%26 == 0:
        a += 'z'
        n -=26
    n = int(n / 26)
a = a[::-1]
print(a)
    



### FIXED CODE ###

n = int(input())
a = ''

while n > 0:
    if n%26 == 1:
        a += 'a'
    elif n%26 == 2:
        a += 'b'
    elif n%26 == 3:
        a += 'c'
    elif n%26 == 4:
        a += 'd'
    elif n%26 == 5:
        a += 'e'
    elif n%26 == 6:
        a += 'f'
    elif n%26 == 7:
        a += 'g'
    elif n%26 == 8:
        a += 'h'
    elif n%26 == 9:
        a += 'i'
    elif n%26 == 10:
        a += 'j'
    elif n%26 == 11:
        a += 'k'
    elif n%26 == 12:
        a += 'l'
    elif n%26 == 13:
        a += 'm'
    elif n%26 == 14:
        a += 'n'
    elif n%26 == 15:
        a += 'o'
    elif n%26 == 16:
        a += 'p'
    elif n%26 == 17:
        a += 'q'
    elif n%26 == 18:
        a += 'r'
    elif n%26 == 19:
        a += 's'
    elif n%26 == 20:
        a += 't'
    elif n%26 == 21:
        a += 'u'
    elif n%26 == 22:
        a += 'v'
    elif n%26 == 23:
        a += 'w'
    elif n%26 == 24:
        a += 'x'
    elif n%26 == 25:
        a += 'y'
    elif n%26 == 0:
        a += 'z'
        n -=26
    n = int(n / 26)
a = a[::-1]
print(a)
a, b = map(int, input().split())

if a == "H" and b == "H":
  print("H")
elif a == "H" and b == "D":
  print("D")
elif a == "D" and b == "H":
  print("D")
elif a == "D" and b == "D":
  print("H")

### FIXED CODE ###

a, b = map(str, input().split())

if a == "H" and b == "H":
  print("H")
elif a == "H" and b == "D":
  print("D")
elif a == "D" and b == "H":
  print("D")
elif a == "D" and b == "D":
  print("H")
n = int(input())

s = []
for i in range(n):
	s.append(list(input().split()) + i+1)

for i in range(n):
	s[i][1] = int(s[i][1])

ans = sorted(s,key=lambda x : (x[0],x[1]))

for a in ans:
  print(a[2])

### FIXED CODE ###

n = int(input())

s = []
for i in range(n):
	S,P=input().split()
	s.append([S,-int(P),i+1])

ans = sorted(s,key=lambda x : (x[0],x[1]))

for a in ans:
  print(a[2])
def comb(n, r):
    ans = 1
    for i in range(n - r + 1, n + 1):
        ans *= i
    for i in range(1, r + 1):
        ans /= i
    return ans

N = int(input())
a = tuple(map(int, input().split()))

Max = 0
for i in range(0, N):
    for j in range(i + 1, N):
        M = max(a[i], a[j])
        m = min(a[i], a[j])
        res = comb(M, m)
        if Max < res:
            Max = res;
            n = M
            r = m

print(n, r)


### FIXED CODE ###

N = int(input())
a = tuple(map(int, input().split()))

n = max(a)
r = 0
M = 0
mid = n / 2
diff = 1000000000
for x in a:
    if x == n:
        continue
    if diff > abs(mid - x):
        diff = abs(mid - x)
        r = x

print(n, r)
n,m=map(int,input().split())
lst=[]
for i in range(m):
  P,Y=map(int,input().split())
  lst.append([P,Y])
lst.sort(key=lambda x:(x[0],x[1]))
lst[0][1]=1
for j in range(m-1):
  if lst[j][0]==lst[j+1][0]:
    lst[j+1][1]=lst[j][1]+1
  else:
    lst[j+1][1]=1
def plus0(s):
  while len(s)<6:
    s='0'+s
for k in range(m):
  lst[k][0]=plus0(str(lst[k][0]))
  lst[k][1]=plus0(str(lst[k][1]))
  print(''.join(lst[k]))
  





### FIXED CODE ###

n,m=map(int,input().split())
lst=[]
for i in range(m):
  p,y=map(int,input().split())
  lst.append([i,p,y])
lst.sort(key=lambda x:(x[1],x[2]))
j=1
Lst=[]
for i in range(m):
  if lst[i][1]==lst[min(m-1,i+1)][1]:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j+=1
    Lst.append([lst[i][0],u])
  else:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j-=j-1
    Lst.append([lst[i][0],u])
Lst.sort(key=lambda x:x[0])
for k in range(m):
  print(Lst[k][1])
N = int(input())
a = []
b = {}

for i in range(N-1):
    c = list(map(int, input().split()))
    a.append(c)
    if i == 0:
        if c[2] % 2 == 0:
            b[c[0]] = 0
            b[c[1]] = 0
        else:
            b[c[0]] = 0
            b[c[1]] = 1
    if i > 0:
        if c[0] in b:
            if c[2] % 2 == 0:
                b[c[1]] = b[c[0]]
            else:
                b[c[1]] = (b[c[0]]+1)%2
                
        elif c[1] in b:
            if c[2] % 2 == 0:
                b[c[0]] = b[c[1]]
            else:
                b[c[0]] = (b[c[1]]+1)%2

while True:
    for j in a:
        if j[1] in b and j[0] not in b:
            if j[2] % 2 == 0:
                b[j[0]] = b[j[1]]
            else:
                b[j[0]] = (b[c[1]]+1)%2

        elif j[0] in b and j[1] not in b:
            if j[2] % 2 == 0:
                b[j[1]] = b[j[0]]
            else:
                b[j[1]] = (b[c[0]]+1)%2

    if len(b) == N:
        break
    
for l in range(1,N+1):
    print(b[l])


### FIXED CODE ###

N = int(input())
a = [0] * N
b = [[] for _ in range(N)]
for _ in range(N-1):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    b[x].append((y, z))
    b[y].append((x, z))


l = [(0, -1, 0)]
while l:
    x, s, t = l.pop()
    if t % 2 == 0:
        a[x] = 0
    else:
        a[x] = 1
    for v, w in b[x]:
        if v == s:
            continue
        l.append((v, x, t + w))

for x in a:
    print(x)
s = input().rstrip()

concurrent_BC_cnt = 0
old1 = ""
cnt = 0
for tmp in (reversed(s)):
	if tmp == "A"
		if old1 == "B":
			cnt += concurrent_BC_cnt
		else:
			concurrent_BC_cnt = 0
			old1 = "A"
		# if "A" not update old1
	else:
		if tmp == "B" and old1 == "C":
			concurrent_BC_cnt += 1
		elif tmp == "C" and old1 == "B":
			pass
		else:
			concurrent_BC_cnt = 0
			
		old1=tmp
	
print(cnt)

### FIXED CODE ###

s = input().rstrip()

concurrent_BC_cnt = 0
old1 = ""
cnt = 0
for tmp in (reversed(s)):
	if tmp == "A":
		if old1 == "B":
			cnt += concurrent_BC_cnt
		else:
			concurrent_BC_cnt = 0
			old1 = "A"
		# if "A" not update old1
	else:
		if tmp == "B" and old1 == "C":
			concurrent_BC_cnt += 1
		elif tmp == "C" and old1 == "B":
			pass
		else:
			concurrent_BC_cnt = 0
			
		old1=tmp
	
print(cnt)
import collections

N=int(input())
A_data=list(map(int,input().split()))
mod=10**9+7

A=collections.Counter(A_data)

if N%2==1:
    if not A[0]==1:
        ans=0
    else:
        for i in range(2,N,2):
            if not A[i]==2:
                ans=0
                break
        if ans!=0:
            ans=2**((N-1)//2)%mod
elif N%2==0:
    for i in range(1,N,2):
        if not A[i]==2:
            ans=0
            break
    if ans!=0:
        ans=2**(N//2)%mod

print(ans)

### FIXED CODE ###

import collections

N=int(input())
A_data=list(map(int,input().split()))
mod=10**9+7

A=collections.Counter(A_data)

f=True
if N%2==1:
    if not A[0]==1:
        ans=0
    else:
        for i in range(2,N,2):
            if not A[i]==2:
                ans=0
                f=False
                break
        if f==True:
            ans=2**((N-1)//2)%mod
elif N%2==0:
    for i in range(1,N,2):
        if not A[i]==2:
            ans=0
            f=False
            break
    if f==True:
        ans=2**(N//2)%mod

print(ans)
import numpy as np
 
(n, k) = map(int,input().split())
hights = list(map(int,input().split()))
memo = [-1] * n
memo[0]

print(' '.join([str(elem) for elem in memo]))




### FIXED CODE ###

def printArray(arr):
  for i in range(0, len(arr)):
    print(arr[i])
    
def minimumCost(n, hights):  
  if (n < 2):
    print("0")
  else:
    memo = []
    memo.append(0)
    memo.append(abs(hights[0] - hights[1]))
    for i in range(2, n):
      memo.append(min(
        (abs(hights[i] - hights[i - 1]) + memo [i - 1]), 
        (abs(hights[i] - hights[i - 2]) + memo [i - 2])
      ))
    print(memo[n-1])
    
n = int(input())
hights = list(map(int,input().split()))
minimumCost(n, hights)
import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.uniteTree(p[i], q[i])

for i in range(L):
	train.uniteTree(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.findRoot(i)
	b = train.findRoot(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")

### FIXED CODE ###

import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.Unite(p[i], q[i])

for i in range(L):
	train.Unite(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.Find_Root(i)
	b = train.Find_Root(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")
n,k=map(int,input().split())
p=list(map(int,input().split()))

q=map(lambda x:(x+1)/2,p)

ans=0

for i in range(n-k+1):
  ans=max(ans,sum(q[i,i+k]))
  
print(ans)

### FIXED CODE ###

import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:(x+1)/2,a))

a=[0]+list(itertools.accumulate(a))
ans=0

for i in range(n-k+1):
  ans=max(ans,a[i+k]-a[i])
  
print(ans)
def CountingSort(A,B,num):

	C = [0 for _ in range(num+1)]
	#C[i]にiの出現回数を記録する
	for i in A:
		C[i] += 1

	#C[i]にi以下の数の出現数を記録する =>累積度数分布を出力
	k = max(A)
	for j in range(1,k+1):
		C[j] += C[j-1]
	for h in range(num-1,-1,-1):
		B[C[A[h]]-1] = A[h]
		C[A[h]] -= 1

if __name__ == '__main__':

	num = int(input())
	A = [int(i) for i in input().split()]

	B = [0 for _ in range(num+1)]
	CountingSort(A,B,num)

	B.pop()
	print(" ".join(map(str,B)))



### FIXED CODE ###

def CountingSort(A,B,num):

	k = max(A)
	C = [0 for _ in range(k+1)]
	#C[i]にiの出現回数を記録する
	for i in A:
		C[i] += 1

	#C[i]にi以下の数の出現数を記録する =>累積度数分布を出力
	for j in range(1,k+1):
		C[j] += C[j-1]
	for h in range(num-1,-1,-1):
		B[C[A[h]]-1] = A[h]
		C[A[h]] -= 1

if __name__ == '__main__':

	num = int(input())
	A = [int(i) for i in input().split()]

	B = [0 for _ in range(num+1)]
	CountingSort(A,B,num)

	B.pop()
	print(" ".join(map(str,B)))
n = int(input())
b = list(map(int, input().split()))

a = []
a.append(b[0])
for i in range(n-2):
    a.append(min(b[i], b[i+1]))
a.append(b[n-2])
print(sum(a))

### FIXED CODE ###

a, b = map(int, input().split())

ac = 1
ans = 0
while ac < b:
    ans += 1
    ac += a - 1

print(ans)
import math
n=int(input())
a=list(map(int,input().split()))

sum_a=sum(a)
left_a=0
right_a=sum_a
ans=math.inf

for i in range(n):
    left_a+=a[i]
    right_a-=a[i]
    if(ans>abs(left_a-right_a)):
        ans=abs(left_a-right_a)
print(ans)

### FIXED CODE ###

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

sum_a=sum(a)
left_a=0
right_a=sum_a
ans=200002*2020202020

for i in range(n):
    left_a+=a[i]
    right_a-=a[i]
    if(ans>abs(left_a-right_a)):
        ans=abs(left_a-right_a)
print(ans)
a,b,h=[int(i) for i in input()]
print((a+b)*h/2)

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
print(int((a+b)*h/2))