Harryxun/stf_run huggingface dataset:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    q.append(*A[1])

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    for a in A[1]:
        q.append(a)

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())
a,b=map(int,raw_input().split(''))
print (a*b,2*a+2*b)


### FIXED CODE ###

a,b=map(int,raw_input().split())
print a*b,2*(a+b)
x = 0
y= 0
n = input()
v = list(map(int, input().split()))
c = list(map(int, input().split()))
for vv,cc in v,c:
    if cc < vv:
        x+=vv
        y+=cc
print(x-y)

### FIXED CODE ###

x = 0
y= 0
n = input()
v = list(map(int, input().split()))
c = list(map(int, input().split()))
for (vv,cc) in zip(v,c):
    if cc < vv:
        x+=vv
        y+=cc
print(x-y)
odd = ["R", "U", "D"]
even = ["L", "U", "D"]
s_list = list(input())

ans = "Yes"
for i in range(s_list):
  if i % 2 == 0:
	  if not s_list[i] in odd:
    	ans = "No"
  
  if i % 2 == 1:
	  if not s_list[i] in even:
    	ans = "No"

print(ans)

### FIXED CODE ###

s = list(input())
odd_s = ["R", "U", "D"]
even_s = ["L", "U", "D"]

ans = "Yes"

for i in range(len(s)):
  if i % 2 == 0:
    if s[i] not in odd_s:
      ans = "No"
  
  if i % 2 == 1:
    if s[i] not in even_s:
      ans = "No"

print(ans)
n, k = [int(i) for i in input().split(' ')]
input_list = [int(i) for i in input().split(' ')]
 
maximum = sum(input_list[:k])
s = sum(input_list[:k])
for i in range(1, n-k+1):
  s = s - input_list[i-1] + input_list[i+k-1]
  maximum = max(maximum, s)

print( (maximum + k) / 2 )

### FIXED CODE ###

s1, s2 = input().split()
a1, a2 = [int(i) for i in input().split()]
s = input()

if s1 == s:
  print(a1 - 1, a2)
elif s2 == s:
  print(a1, a2 - 1)
else:
  print(a1, a2)
s = input()
c = s.count()
print(s[0:1] + str(c) + s[-1:])

### FIXED CODE ###

s = input()
c = len(s) - 2
print(s[0:1] + str(c) + s[-1:])
x,y = list(map(input()))
if x>y:
  ans = ">"
elif x<y:
  ans = "<"
else:
  ans = "="
print(ans)

### FIXED CODE ###

x = input().split()

if x[0]<x[1]:
  print("<")
elif x[0]==x[1]:
  print("=")
elif x[0]>x[1]:
  print(">")
N, K = map(int, input().split())
A=list(map(int,input().split()))
A.sort()
right = A[-1]+1
left = -1
flag = True
mid = (left+right)//2
minN = right
result = right
while right-left>1 and flag:
    mid = (left+right)//2
    count = 0
    for i in A:
        count += (i-1)//mid
    if count <= K:
        right = mid
        if minN>mid:
            minN = mid
            result = mid
    elif count > K:
        left = mid
print(result)


### FIXED CODE ###

N, K = map(int, input().split())
A=list(map(int,input().split()))
A.sort()
right = A[-1]+1
left = 0
flag = True
mid = (left+right)//2
minN = right
result = mid
while right-left>1 and flag:
    mid = (left+right)//2
    count = 0
    for i in A:
        count += (i-1)//mid
    if count <= K:
        right = mid
        if minN>mid:
            minN = mid
            result = mid
    elif count > K:
        left = mid
print(result)
N = int(input())
a = [9,8,7,6,5,4,3,2,1]
if 0 < n and n <= 81:
    for i in range(9):
        if n % a[i] == 0:
            if n / a[i] > 9:
                print('No')
            else:
                print('Yes')
                break
else:
    print('No')


### FIXED CODE ###

n = int(input())
D = 0
for i in range(1,10):
  for j in range(1,10):
    if j*i == n:
      D = 1
      break
if D == 1:
  print('Yes')
elif D == 0:
  print('No')
s=list(input())
s.sort()
l=[chr(ord("a")+i) for i in range(26)]
n=[]
for j in l:
  if j not in s:
    n.append(j)
n.sort()
print(n[0])

### FIXED CODE ###

s=list(input())
s.sort()
l=[chr(ord("a")+i) for i in range(26)]
n=[]
for j in l:
  if j not in s:
    n.append(j)
n.sort()
if len(n)==0:
  print("None")
else:
  print(n[0])
import numpy

if __name__ == '__main__':
    N,M_a,M_b=list(map(int,input().split()))
    A,B,C=[],[],[]
    for i in range(N):
        a,b,c=list(map(int,input().split()))
        A.append(a)
        B.append(b)
        C.append(c)

    dp=[[[1e10 for i in range(max(B)*(N+1))] for j in range(max(A)*(N+1))] for k in range(N+1)]
    dp[0][0][0]=0

    for i in range(N):
        for c_a in range(max(A)*N):
            for c_b in range(max(B)*N):
                if dp[i][c_a][c_b]==1e10:
                    continue
                dp[i+1][c_a][c_b]=min(dp[i+1][c_a][c_b],dp[i][c_a][c_b])
                dp[i+1][c_a+A[i]][c_b+B[i]]=min(dp[i+1][c_a+A[i]][c_b+B[i]],dp[i][c_a][c_b]+C[i])
    ans_list=[1e10]
    for c_a in A:
        for c_b in B:
            if c_a*M_b==c_b*M_a:
                ans_list.append(dp[N][c_a][c_b])

    ans=min(ans_list)

    if  ans==1e10:
        print(-1)
    else:
        print(ans)








### FIXED CODE ###

if __name__ == '__main__':
    N,M_a,M_b=list(map(int,input().split()))
    A,B,C=[],[],[]
    for i in range(N):
        a,b,c=list(map(int,input().split()))
        A.append(a)
        B.append(b)
        C.append(c)

    dp=[[[1e10 for i in range(sum(B)+max(B)+1)] for j in range(sum(A)+max(A)+1)] for k in range(N+1)]
    dp[0][0][0]=0

    for i in range(N):
        for c_a in range(sum(A)+1):
            for c_b in range(sum(B)+1):
                if dp[i][c_a][c_b]==1e10:
                    continue
                dp[i+1][c_a][c_b]=min(dp[i+1][c_a][c_b],dp[i][c_a][c_b])
                dp[i+1][c_a+A[i]][c_b+B[i]]=min(dp[i+1][c_a+A[i]][c_b+B[i]],dp[i][c_a][c_b]+C[i])
    ans_list=[1e10]
    for c_a in range(1,sum(A)+1):
        for c_b in range(1,sum(B)+1):
            if c_a*M_b==c_b*M_a:
                ans_list.append(dp[N][c_a][c_b])
    ans=min(ans_list)
    if  ans==1e10:
        print(-1)
    else:
        print(ans)
import numpy as np
import math
N = int(input())
A = [input() for i in range(N)]
a = []*N
for i in A:
    b = list(i)
    b.sort()
    a.append(b)

a.sort()
c = list(map(list, set(map(tuple, a))))
d=[]
for i in c:
    d.append(a.count(i))
count=0
for i in d:
    count += math.factorial(i) // (math.factorial(i - 2) * math.factorial(2))

print(count)

### FIXED CODE ###

N = int(input())
A=[]
S={}
for i in range(N):
    a = list(input())
    a.sort()
    b = ''.join(a)
    if b not in S:
        S[b] = 1
    else:
        S[b] += 1


count=0
for i in S.values():
    if i==1:
        continue
    count += i*(i-1)//2
print(count)
#[R,G,B,N] = list(map(int,input().split()))
import collections
N = int(input())
xy = [tuple(map(int,input().split())) for i in range(N)]
xy.sort( key = lambda x: (x[0],x[1]))
l = []
for i in range(N):
    for j in range(i+1,N):
        (x_diff, y_diff) = [xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]]
        l.append((x_diff, y_diff))
dic = collections.Counter(l)
val = dic.values()
print(N - max(val))

### FIXED CODE ###

#[R,G,B,N] = list(map(int,input().split()))
import collections
N = int(input())
xy = [tuple(map(int,input().split())) for i in range(N)]
xy.sort( key = lambda x: (x[0],x[1]))
l = []
for i in range(N):
    for j in range(i+1,N):
        (x_diff, y_diff) = [xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]]
        l.append((x_diff, y_diff))
dic = collections.Counter(l)
val = dic.values()
if len(val) == 0:
    print(1)
else:
    print(N - max(val))
if int(A)-int(B)*2 <=0:
  print('0')

else:
  print(str(int(A)-int(B)*2))
  


### FIXED CODE ###

A, B = [int(i) for i in input().split()]
0<=A<=100
0<=B<=100

if A>B*2:
  print(A-B*2)

else:
  print(0)
import sys
readline = sys.stdin.readline

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

# 最も絶対値の大きい数を、それが正の数なら右から、負の数なら左から、
# 昇順になっていない場所に足していく

ans = []
while True:
  plusmax = 0
  minusmax = 0
  plusmax_i = -1
  minusmax_i = -1
  left_target = -1
  right_target = -1
  targetdiff = 0
  for i in range(len(A)):
    if A[i] < minusmax:
      minusmax = A[i]
      minusmax_i = i
    if A[i] > plusmax:
      plusmax = A[i]
      plusmax_i = i
    # 正/負の方向に最も大きい数とそのインデックスを求めた
    if i != 0:
      if A[i - 1] > A[i]:
        if left_target == -1: # 左端は一度しか更新しない
          left_target = i
        right_target = i # 右端は常に更新
  if left_target == -1:
    # 一度の逆転が起きていなければ終了
    break
  if abs(plusmax) > abs(minusmax):
    # 正の数の最大値のほうが大きい場合は右端に足す
    ans += [(plusmax_i + 1, right_target + 1)]
    A[right_target] += plusmax
  else:
    # 負の数の最大値のほうが大きい場合は左端に足す
    ans += [(minusmax_i + 1, left_target)]
    A[left_target - 1] += minusmax
    
if len(ans) > 2 * N:
  p = 1 / 0
print(len(ans))
for a in ans:
  print(*a)


### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

# 最も絶対値の大きい数を、それが正の数なら右から、負の数なら左から、
# 昇順になっていない場所に足していく

# print(A)

ans = []
plusmax = 0
minusmax = 0
plusmax_i = -1
minusmax_i = -1
  
target = -1
maxdiff = 0
for i in range(len(A)):
  if A[i] < minusmax:
    minusmax = A[i]
    minusmax_i = i
  if A[i] > plusmax:
    plusmax = A[i]
    plusmax_i = i
# 最も絶対値が大きいものが正であれば、左から順に足していく
# 負であれば右から
# この方針は途中で変えない。正なら最後まで正。
# 2要素の差の最大値は、絶対値の最大がたとえば1000のときに1000～-1000の差なので、
# 2回足せば必ず差が埋まる
  
if abs(plusmax) > abs(minusmax):
  # 正でいく場合
  maxval = plusmax
  max_i = plusmax_i
  for i in range(1,len(A)):
    if A[i - 1] > A[i]:
      ans.append((max_i + 1,i + 1))
      ans.append((max_i + 1,i + 1))
      A[i] += 2 * maxval
      max_i = i
      maxval = A[i]
else:
  # 負でいく場合
  minval = minusmax
  min_i = minusmax_i
  for i in range(len(A) - 1, 0,-1):
    if A[i - 1] > A[i]:
      ans.append((min_i + 1, i))
      ans.append((min_i + 1, i))
      A[i - 1] += 2 * minval
      min_i = i - 1
      minval = A[i - 1]
        
print(len(ans))
for a in ans:
  print(*a)
n = int(input())
S = input()
b = 0
if n % 2 == 0:
  b = 1
  for i in range(n/2):
    if S[i] != S[i+n/2]:
      b = 0
print("Yes" if b == 1 else "No")
  


### FIXED CODE ###

n = int(input())
S = input()
b = 0
if n % 2 == 0:
  h = int(n/2)
  b = 1
  for i in range(h):
    if S[i] != S[i+h]:
      b = 0
print("Yes" if b == 1 else "No")
def how_many_times_divisible(n):
	ans = 0
	while n % 2 == 0:
		n /= 2
		ans += 1
	return ans
 
N = int(input())
a = map(int, input().split())
ans = min(map(how_many_times_divisible, a))
 
print(ans)

### FIXED CODE ###

li=list(input())
t = 0
for i in li:
    if i == "1":
        t+=1
    else:
        pass
print(t)
a,b,c = list(map(int,input().split()))
#print(a,b,c)
if ((a**2 + b**2 + c**2)**2 -4*((a*b+b*c+c*a)**2))/(a**2 + b**2 + c**2-2*(a*b+b*c+c*a)) >0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if (c-a-b)**2 -4*a*b >0 and c-a-b>0:
  print('Yes')
else:
  print('No')
from numpy.linalg import solve
N=int(input())
A=input().split()
for i in range(N):
    A[i]=2*int(A[i])
x=[None]*N
for i in range(N-1):
    x[i]=[0]*N
    x[i][i],x[i][i+1]=1,1
x[N-1]=[0]*N
x[N-1][0],x[N-1][N-1]=1,1
y=solve(x,A)
for i in range(N):
    print(int(y[i]),end=' ')

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
y=0
for i in range(N-1):
    y=2*(A[i]-y//2)
l=[None]*N
l[0]=(2*A[-1]-y)//2
for i in range(1,N):
    l[i]=2*(A[i-1]-l[i-1]//2)
print(*l)
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cnt = 0
ac = 0
bc = 0

while cnt < k:
    if ac == len(A):
        cnt += B[bc]
        if cnt <= k:
            bc += 1
        else:
            break
    if bc == len(B):
        cnt += A[ac]
        if cnt <= k:
            ac += 1
        else:
            break
    if ac == len(A) and bc == len(B):
        break
    if A[ac] < B[ac]:
        cnt += A[ac]
        if cnt <= k:
            ac += 1
        else:
            break
    else:
        cnt += B[bc]
        if cnt <= k:
            bc += 1
        else:
            break

print(ac + bc)

### FIXED CODE ###

n, m, k = map(int, input().split())

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

a = [0]
b = [0]

for i in range(n):
    a.append(a[i] + A[i])

for i in range(m):
    b.append(b[i] + B[i])

j = m

for i in range(n + 1):
    if a[i] > k:
        break
    while a[i] + b[j] > k:
        j -= 1
    else:
        ans = max(ans, i + j)
print(ans)
import math

def Comb(n, r):
  return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

N = input()
K = int(input())
ans = 0
for i in range(1, len(N)):
  if i < K:
    pass
  else:
    ans += 9 ** K * Comb(i-1, K-1)
ans += (int(N[0])-1) * Comb(len(N)-1, K-1) * 9 ** (K-1)
if K == 1:
  ans += 1
elif K == 2:
  for i in range(1, len(N)):
    if N[i] != '0':
      ans += int(N[i]) + 9 * (len(N) - i - 1)
      break
else:
  for i in range(1, len(N)):
    if N[i] != '0':
      if len(N) - i - 1 >= 2:
        ans += Comb(len(N) - i - 1, 2) * 9 ** 2
      if len(N) - i - 1 >= 1:
        ans += (int(N[i]) - 1) * 9 * (len(N) - i - 1)
      for j in range(i+1, len(N)):
        if N[j] != '0':
          ans += int(N[j]) + 9 * (len(N) - j - 1)
          break
      break
print(ans)


### FIXED CODE ###

import math

def Comb(n, r):
  if n < r:
    return 0
  else:
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

N = input()
K = int(input())
ans = 0
for i in range(1, len(N)):
  if i < K:
    pass
  else:
    ans += 9 ** K * Comb(i-1, K-1)
ans += (int(N[0])-1) * Comb(len(N)-1, K-1) * 9 ** (K-1)
if K == 1:
  ans += 1
elif K == 2:
  for i in range(1, len(N)):
    if N[i] != '0':
      ans += int(N[i]) + 9 * (len(N) - i - 1)
      break
else:
  for i in range(1, len(N)):
    if N[i] != '0':
      if len(N) - i - 1 >= 2:
        ans += Comb(len(N) - i - 1, 2) * 9 ** 2
      if len(N) - i - 1 >= 1:
        ans += (int(N[i]) - 1) * 9 * (len(N) - i - 1)
      for j in range(i+1, len(N)):
        if N[j] != '0':
          ans += int(N[j]) + 9 * (len(N) - j - 1)
          break
      break
print(ans)
time=input()

aok=1
tak=1

for i in time:
	l=map(int, raw_input().split())
	if l[0]>=l[1]:
		tak=(tak/l[1]+1)*l[1]
		aok=tak/l[1]*l[0]
	else:
		aok=(aok/l[0]+1)*l[0]
		tak=aok/l[0]*l[1]

print aok+tak


### FIXED CODE ###

time=input()

aok=1
tak=1

for i in range(time):
	l=map(int, raw_input().split())
	if aok<tak:
		if tak%l[1]!=0:
			tak=(tak/l[1]+1)*l[1]
		if aok>tak/l[1]*l[0]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			aok=tak/l[1]*l[0]
	elif aok==tak:
		if l[0]<=l[1]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
	else:
		if aok%l[0]!=0:
			aok=(aok/l[0]+1)*l[0]
		if tak>aok/l[0]*l[1]:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
		else:
			tak=aok/l[0]*l[1]
print aok+tak
line = input()

calc = int(line) * int(calc) * int(calc) / 27

print(str(calc))

### FIXED CODE ###

line = int(input())
calc = line * line * line / 27

print(str(calc))
def factorial(n):
    res = 1
    for i in range(1, n+1):
        res = res * i
    return res

while True:
    inp = input()
    if inp == '0': break

    num = factorial(int(inp))
    cnt = 0
    while True:
        if num % 10 == 0:
            cnt = cnt + 1
            num = int(num / 10)
        else:
            break

    print(cnt)

### FIXED CODE ###

while True:
    inp = input()
    if inp == '0': break

    num = 1
    for i in range(1, int(inp)+1):
        num = num * i

    cnt = 0
    strnum = str(num)
    while True:
        if strnum[-1] == '0':
            cnt = cnt + 1
            strnum = strnum[:-1]
        else:
            break

    print(cnt)
# -*- coding: utf-8 -*-

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

S = input()

## Logic

S = S[::-1]
print(S)

i = 0 
while i < len(S):
    if [i:i+7]=="remaerd":
        i = i + 7
    elif [i:i+6]=="resare":
        i = i + 6
    elif [i:i+5]=="maerd":
        i = i + 5
    elif [i:i+5]=="esare":
        i = i + 5
    else:
        print("NO")
        sys.exit()
print("YES")

### FIXED CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

S = input()

## Logic

S = S[::-1]

i = 0 
while i < len(S):
    if S[i:i+7]=="remaerd":
        i = i + 7
    elif S[i:i+6]=="resare":
        i = i + 6
    elif S[i:i+5]=="maerd":
        i = i + 5
    elif S[i:i+5]=="esare":
        i = i + 5
    else:
        print("NO")
        sys.exit()
print("YES")
from networkx import*
#print(max(map(len,connected_components(Graph(map(str.split,[*open(0)][1:]))))))
#(n,m),*t=map(str.split,open(0));print(max(map(len,connected_components(Graph(t[:int(m)])))))
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
G = Graph(range(1, n+1))
G.add_edges_from(edges)
ccs = connected_components(G)
ans = max(map(len, ccs))
print(ans)

### FIXED CODE ###

from networkx import*
_,*t=map(str.split,open(0))
print(max(1,1,*map(len,connected_components(Graph(t)))))
s = input()
k = int(input())
n = len(s)
heads = []
d = set()
for c in s:
    d.add(c)

for key in d:
    heads.append(key)

heads.sort()
ind = 0
ans = []
while True:
    if ind > len(heads)-1:
        break
    head = heads[ind]
    p = set()
    for i in range(len(s)):
        if s[i] == head:
            p.add(i)
    # print(head)
    ext = 0
    while True:
        flag = False
        dis = -1
        for key in p:
            if key+ext > n-1:
                flag = True
                dis = key
        if flag:
            p.discard(dis)
        if not p:
            break
        for key in p:
            temp = s[key]
            for j in range(1,ext):
                temp += s[key+j]
            if temp not in ans:
                ans.append(temp)
        ext += 1
        if len(ans) >= 500:
            break
    if len(ans) >= 500:
        break
    else:
        ind += 1
# print(ans)
ans.sort()
print(ans[k-1])

# for i in range(len(s)):
#     if


### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
heads = []
d = set()
for c in s:
    d.add(c)

for key in d:
    heads.append(key)

heads.sort()
ind = 0
ans = []
while True:
    if ind > len(heads)-1:
        break
    head = heads[ind]
    p = set()
    for i in range(len(s)):
        if s[i] == head:
            p.add(i)
    # print(head)
    ext = 0
    while True:
        flag = False
        dis = -1
        for key in p:
            if key+ext > n-1:
                flag = True
                dis = key
        if flag:
            p.discard(dis)
            # print(ext)
            # print(p)
        if not p:
            break
        for key in p:
            temp = s[key]
            for j in range(1,ext+1):
                temp += s[key+j]
            # print(temp)
            if temp not in ans:
                ans.append(temp)
        ext += 1
        if ext > 5:
            break
        if len(ans) >= 500:
            break
    if len(ans) >= 500:
        break
    else:
        ind += 1

# print(ans)
ans.sort()
print(ans[k-1])

# for i in range(len(s)):
#     if
import numpy as np
from collections import deque
infinity = -10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1

N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i][j] ==1:
            if A[i+1][j] == 1:
                G[W*(i+1)+j].append(W*i+j)
                G[W*i+j].append(W*(i+1)+j)

            if A[i][j+1] == 1:
                G[W*i+(j+1)].append(W*i+j)
                G[W*i+j].append(W*i+(j+1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            d = BFS(W*i+j)
        ans = max(ans,max(d))
print(ans)

    

### FIXED CODE ###

import numpy as np
from collections import deque
infinity = 10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1
#print(A)
N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i+1][j] == 1:
            #if W*(i+1)+j ==1:
                #print("a")
            #G[W*(i+1)+j].append(W*i+j)
            G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                #if W*(i-1)+j ==1:
                    #print("b")
                #G[W*(i-1)+j].append(W*i+j)
                G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            #if W* ==1:
                #print("c")
            #G[W*i+(j+1)].append(W*i+j)
            G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                #if W*(i+1)+j ==1:
                    #print("d")
                #G[W*i+(j-1)].append(W*i+j)
                G[W*i+j].append(W*i+(j-1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0

#print(G)

for i in range(N):
    #print(i)
    I = i//W
    J = i%W
    #print(I,J)
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))

print(ans)
x = []
for i in input().split():
    x.append(int(i))

if x[4]-x[0] > x[5]:
    print(':(')
else:
    print('Yay!')

### FIXED CODE ###

a, b, c, d, e, k = [int(input()) for i in range(6)]
if e-a > k:
    print(':(')
else:
    print('Yay!')
a,b = int(input().split())

if a + b <= 16:
  if a <= 8 and b <= 8:
    print('Yay!')
  else:
    print(':(')
else:
  print(':(')

### FIXED CODE ###

a,b = map(int, input().split())
 
if a + b <= 16:
  if a <= 8 and b <= 8:
    print('Yay!')
  else:
    print(':(')
else:
  print(':(')