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

import heapq

H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()

def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True

visited = [[False for w in range(W)] for h in range(H)]
queue = []
heapq.heappush(queue, (0, (c_h, c_w)))  # Push start point with cost (number of warps) 0

while len(queue) > 0:
    cost, p = heapq.heappop(queue)

    if visited[p[0]][p[1]]:  # Skip if already visited (the priority queue assures we can visit to the point with the smallest cost)
        continue
    visited[p[0]][p[1]] = True

    if p[0] == d_h and p[1] == d_w:  # Finally reach to the goal
        print(cost)
        break
    # print(f'Visit {p}: {cost}')

    # Explore neighbours where can be reached by walk (with the same cost as p)
    neighbours = ((p[0], p[1] - 1), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0] + 1, p[1]))
    for n in neighbours:
        if not in_the_map(n) or visited[n[0]][n[1]]:
            continue
        if s[n[0]][n[1]] == '.':  # not wall
            heapq.heappush(queue, (cost, n))  # For later exploration

    # Explore points where can be reached by warp from visited points(with +1 cost from p)
    for diff_h in range(-2, 3, 1):
        for diff_w in range(-2, 3, 1):
            h = p[0] + diff_h
            w = p[1] + diff_w
            if not in_the_map((h, w)) or visited[h][w]:
                continue
            if s[h][w] == '.': # not wall
                heapq.heappush(queue, (cost + 1, (h, w)))

if not visited[d_h][d_w]:  # Cannot reach to the goal
    print(-1)

### FIXED CODE ###

H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()

def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True
 
costs = [[-1 for w in range(W)] for h in range(H)]
 
def dfs(h, w, c, q):
    if not in_the_map((h, w)):
        return
    if costs[h][w] >= 0:
        return
    if s[h][w] != '.':
        return
    q.append((h, w))
    costs[h][w] = c 
    dfs(h - 1, w, c, q)
    dfs(h + 1, w, c, q)
    dfs(h, w - 1, c, q)
    dfs(h, w + 1, c, q)

queue = [(c_h, c_w)]
cost = 0
while len(queue) > 0:
    visited = []
    for q in queue:
        dfs(q[0], q[1], cost, visited)
    
    next_queue = []
    for v in visited:
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = v[0] + dh 
                ww = v[1] + dw
                if not in_the_map((hh, ww)):
                    continue
                if costs[hh][ww] >= 0:
                    continue
                if s[hh][ww] != '.':
                    continue
                next_queue.append((hh, ww))

    cost += 1
    queue = next_queue

print(costs[d_h][d_w])
### BUGGY CODE ###

N=int(input())
a=input()
a=a.rstrip().split(" ")
list1=[]
for i in range(N):
    list1.append(int(a[i]))
#print(list1)
lists=[]
for k in range(len(list1)):
    if list1[k] in lists:
        pass
    else:
        lists.append(list1[k])
#print(lists)
cnt=0
for j in range(len(lists)):
    if lists[j]>list1.count(lists[j]):
        cnt+=list1.count(lists[j])
    elif lists[j]<list1.count(lists[j]):
        cnt+=list1.count(lists[j])-lists[j]
print(cnt)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=0
L=[0 for i in range(100005)]
for i in range(N):
    if A[i]<=100000:
        L[A[i]]+=1
    else:
        cnt+=1
    
for j in range(100002):
    
    if L[j]==j:
        pass
    elif L[j]<j:
        cnt+=L[j]
    elif L[j]>j:
        cnt+=L[j]-j
print(cnt)
### BUGGY CODE ###

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

l=sorted(a)

ans=1

for i in range(N):
    t=l[i]
    _ans=0
    for j in range (N-i):
        c=l[i+j]
        if c-t<=2:
            pass
        else:
            _ans=j
            break
    if _ans>ans:
        ans=_ans
    else:
        pass
print(ans)


### FIXED CODE ###

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

l=[0]*((10**5)+2)

for v in a:
    l[v]+=1
    l[v+1]+=1
    l[v+2]+=1

print(max(l))
### BUGGY CODE ###

from bisect import bisect_right

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

ans = 0
y_low = {}
i = 0
for x in A:
    y_low[i] = bisect_right(B, x)
    i += 1
for y_lowi in y_low.values():
    for y in B[y_lowi:]:
        z_low = bisect_right(C, y)
        ans += N - z_low
print(ans)


### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right


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

ans = 0
y_low = {}
i = 0
for y in B:
    x = bisect_left(A, y)
    z = bisect_right(C, y)
    ans += x * (N-z)
print(ans)
### BUGGY CODE ###

k=int(input())
s=0
import math
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s+=math.gcd(math.gcd(a,b),c)
print(s)


### FIXED CODE ###

k=int(input())
s=0
import math
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s+=math.gcd(math.gcd(a,b),c)
print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = sorted(LIST())

# K個以上の3つ組が達成できるような最大の値mを探す
def check(m):
    sm = 0
    for a in A:
        for b in B:
            cnt = Z - bisect_left(C, m-a-b)
            sm += cnt
    return sm >= K

res = bisearch_max(0, 10**18, check)

ans = []
for a in A:
    for b in B:
        idx = bisect_left(C, res-a-b)
        for i in range(Z-1, idx-1, -1):
            c = C[i]
            ans.append(a+b+c)
ans.sort(reverse=1)
[print(a) for a in ans]


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X,Y,Z,K=MAP()
A=LIST()
B=LIST()
C=LIST()

AB=[]
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)
AB=AB[:3000]

ABC=[]
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
count = 0
for i in set(S):
    c_i = S.count(i)
    count += c_i*(c_i-1)
print(count//2)

### FIXED CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
S.sort()
S.append(10000000000)
count = 0
p = S[0]
l = 0
for i in range(n+2):
    if p != S[i]:
        count += (i-l)*(i-l-1)//2
        l = i
        p = S[i]
print(count)
### BUGGY CODE ###

n,a,b=map(int,input().split())
ans=0
end=True
while end:
    if n>=a:
        n-=a
        ans+=a
        if n>b:n-=b
        else:end=False
    else:
        ans+=n
        end=False
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
ans=0
# end=True
# while end:
#     if n>=a:
#         n-=a
#         ans+=a
#         if n>b:n-=b
#         else:end=False
#     else:
#         ans+=n
#         end=False

cnt=n//(a+b)
ans+=cnt*a
ama=n%(a+b)
if ama-a>=0:ans+=a
else:ans+=ama
print(ans)
### BUGGY CODE ###

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

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
    
for i in range(K):
  ch_list=ch_list[2:]
  
#print(ch_list)
print(N-1-len(ch_list))

### FIXED CODE ###

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

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
#print(ch_list)
len_ch=len(ch_list)

if len_ch>=2*K:
  print(N-1-len_ch+2*K)
elif len_ch==2*K-1:
  print(N-1-len_ch+2*K-1)
else:
  print(N-1)
### BUGGY CODE ###

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

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

max_cnt = 0
for a in range(len(A)+1):
    if sum(A[:a]) > K:
        break
    for b in range(len(B)+1):
        time = sum(A[:a]) + sum(B[:b])
        if time <= K:
            cnt = a + b
            if cnt > max_cnt:
                max_cnt = cnt
        else:
            break
print(max_cnt)


### FIXED CODE ###

N, M, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

A = [0]
B = [0]
for i in range(len(a)):
    A.append(A[i] + a[i])
for i in range(len(b)):
    B.append(B[i] + b[i])

ans = 0
j = len(B) - 1
for i in range(len(A)):
    if A[i] > K:
        break
    while A[i] + B[j] > K:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import networkx as nx

N, M = map(int,input().split())
G = nx.Graph()
[G.add_node(i + 1) for i in range(N)]

for _ in range(M):
    A, B = map(int,input().split())
    G.add_edge(A, B)

flag = 1
print_str = 'Yes\n'
for i in range(2, N + 1):
    haspath = nx.has_path(G, source = i, target = 1)
    
    if haspath == False:
        flag = 0
        break
    else:
        ans = nx.shortest_path(G, source = i, target = 1)
        print_str += (str(ans[1]) + '\n')
        
if flag == 1:
    print(print_str[:-1])
else:
    print('No')

### FIXED CODE ###

from collections import deque
N, M = map(int,input().split())
graph = [[] for i in range(N + 1)]
for _ in range(M):
    A, B = map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

queue = deque([1]) 
flag = [-1] * (N + 1)

while queue: 
    node = queue.popleft()
    children = graph[node] 
    for child in children:
        if flag[child] == -1:
            flag[child] = node
            queue.append(child)

if -1 in flag[2:]:
    print('No')
else:
    print('Yes')
    print(*flag[2:], sep='\n')
### BUGGY CODE ###

from math import inf
n,h=map(int,input().split())
l=[int(i) for i in input().split()]
dp=[inf]*n
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
    for j in range(1,min(i,h)+1):
        dp[i]=min(dp[i],dp[i-j]+abs(l[i-j]-l[i]))
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    INF = 10**10
    DP = [INF]*N
    DP[0] = 0
    DP[1] = abs(h[1]-h[0])
    for i in range(2,N):
        DP[i] = min(DP[i-j] + abs(h[i-j]-h[i]) for j in range(1,min(K,i)+1))
    print(DP[-1])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1) * 2, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(1, n):
    if a_list[i] == 0:
        continue
    a_list[i] %= 998244353
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)
### BUGGY CODE ###

from functools import reduce
A, B, C, D = map(int, input().split())

def gcd(*numbers):
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    return reduce(gcd, numbers)

def lcm(*numbers):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers, 1)

result = 0
while(True):
  if A%C == 0 or A%D == 0:
    A += 1
  else:
    break

result += (B-A+1) - (B//C - A//C) - (B//D - A//D)
l = lcm(C, D)
result += (B//l - A//l)

print("{}".format(result))

### FIXED CODE ###

from functools import reduce
A, B, C, D = map(int, input().split())
if C == 1 or D == 1:
  print(0)
  exit()

def gcd(*numbers):
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    return reduce(gcd, numbers)

def lcm(*numbers):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers, 1)

result = 0

if A%C == 0 or A%D == 0:
  A += 1

result += (B-A+1) - (B//C - A//C) - (B//D - A//D)
l = lcm(C, D)
result += (B//l - A//l)

print("{}".format(result))
### BUGGY CODE ###

from bisect import bisect
N = int(input())
xs = list(map(int,input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

K = len(bin(N)) - 1
dp = [[None]*N for i in range(K)]
for i,x in enumerate(xs):
    dp[0][i] = bisect(xs, x+L) - 1
for k in range(K-1):
    for i in range(N):
        dp[k+1][i] = dp[k][dp[k][i]]

def enough(fr,to,n):
    now = fr
    for k in reversed(range(K)):
        if n&(1<<k)==0: continue
        now = dp[k][now]
        if now >= to:
            return True
    return False

ans = []
for a,b in qs:
    if a>b: a,b = b,a
    ok = N
    ng = 0
    while ok-ng > 1:
        m = (ok+ng)//2
        if enough(a,b,m):
            ok = m
        else:
            ng = m
    ans.append(ok)

print(*ans,sep='\n')

### FIXED CODE ###

from bisect import bisect
N = int(input())
xs = list(map(int,input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

K = len(bin(N)) - 1
dp = [[None]*N for i in range(K)]
for i,x in enumerate(xs):
    dp[0][i] = bisect(xs, x+L) - 1
for k in range(K-1):
    for i in range(N):
        dp[k+1][i] = dp[k][dp[k][i]]

def enough(fr,to,n):
    now = fr
    bn = bin(n)
    ln = len(bn)-2
    for i,c in enumerate(bn[2:]):
        if c=='0': continue
        now = dp[ln-1-i][now]
        if now >= to:
            return True
    return False

ans = []
for a,b in qs:
    if a>b: a,b = b,a
    ok = N
    ng = 0
    while ok-ng > 1:
        m = (ok+ng)//2
        if enough(a,b,m):
            ok = m
        else:
            ng = m
    ans.append(ok)

print(*ans,sep='\n')
### BUGGY CODE ###

h, n = map(int, input().split())
A = []
B = []
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
inf=float('inf')
dp = [[inf] * (h + 1) for i in range(n + 1)]
dp[0][0]=0
for i in range(n):
    for j in range(h + 1):
        if j < A[i]:
            dp[i + 1][j] = min(dp[i][j], B[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])
print(dp[n][h])

### FIXED CODE ###

h, n = map(int, input().split())
A = []
B = []
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
inf=float('inf')
dp = [[inf] * (h + 1) for i in range(n + 1)]
dp[0][0]=0
for i in range(n):
    for j in range(h + 1):
        if j < A[i]:
            dp[i + 1][j] = min(dp[i][j], B[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])
print(dp[n][h])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]+[float('inf') for a in range(N-1)]

for i in range(1,N):
  
  for j in range(max(0,i-K),i):
    dp[i] = min(dp[i],abs(h[i]-h[j])+dp[j])
    

print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j in range(N+1)]

for i in range(N+1):
    dp[i][0]=0


for i in range(1,N+1):
    for j in range(1,H+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


print(dp[N][H])

### FIXED CODE ###

# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j in range(N+1)]

for i in range(N+1):
    dp[i][0]=0


for i in range(1,N+1):
    for j in range(1,H+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


print(dp[N][H])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, p: "List[float]"):

    dp = [[0.0] * (N+1) for i in range(N+1)]

    dp[0][0] = 1
    for i in range(N):
         for j in range(N):
             dp[i+1][j] += dp[i][j] * (1-p[i])
             dp[i+1][j+1] += dp[i][j] * p[i]

    print(sum(dp[N][ceil(N/2):]))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, p: "List[float]"):

    dp = [[0.0] * (N+1) for i in range(N+1)]

    dp[0][0] = 1
    for i in range(N):
         for j in range(N):
             dp[i+1][j] += dp[i][j] * (1-p[i])
             dp[i+1][j+1] += dp[i][j] * p[i]

    print(sum(dp[N][ceil(N/2):]))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    solve(N, p)

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

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

G=[[] for i in range(N)]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

from collections import deque

over=[] #探索ずみ
before=[] #探索前
for i in range(N):
    before.append(i)

dist=[float('inf')]*N
cnt=0
cup=[]
while before:
    v=before.pop(0)
    que=deque([v])
    dist[v]=0
    cuppy=[]
    cuppy.append(v)
    while que:
        u=que.popleft()
        
        for e in G[u]:
            if dist[e] == float('inf'):
                
                que.append(e)
                before.remove(e)
                cuppy.append(e)
                dist[e]=dist[u] + 1
    
    cup.append(cuppy)
    cnt += 1


ans=0
for i in range(len(cup)):
    ans = max(ans,len(cup[i]))
print(ans)

### FIXED CODE ###

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

class UnionFind():
    def __init__(self,n): #n:要素数
        self.n=n
        self.parents = [-1]*n 
        #parents:各要素の親要素番号を格納
        #要素が根である場合、-(そのグループの要素数)を格納する
    
    def find(self,x): #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のグループとyのグループを併合する
        x = self.find(x)
        y = self.find(y)
        
        if x==y:
            return
        
        if self.parents[x] > self.parents[y]: #|xのグループ|<|yのグループ|
            x,y=y,x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        #よりグループ数が多い方の根にもう一方のグループを接続
        
    def size(self,x): #xの属するグループのサイズ
        return -self.parents[self.find(x)]

uf=UnionFind(N)
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    uf.union(a,b)

ans=0

for i in range(N):
    if uf.size(i) > ans:
        ans=uf.size(i)
        
print(ans)
### BUGGY CODE ###

kazu = int(input())
word = input()
score = word.split()
scin = [0]*kazu
for i in range(kazu):
    scin[i] = int(score[i])

answer = 1
for j in range(kazu):
    answer *= scin[j]
    
if answer > 10**18:
    answer = -1

print(answer)

### FIXED CODE ###

kazu = int(input())
word = input()
score = word.split()

maxn = 10**18
zero = 0
answer = 1
scin = [0]*kazu

for i in range(kazu):
    scin[i] = int(score[i])
    if scin[i] == 0:
        zero = 1
if zero == 1:
    answer = 0
else:
    for j in range(kazu):
        answer *= scin[j]
        if answer > maxn:
            answer = -1
            break
print(answer)