Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))

if N % 3:
    ans = len(set(A)) == 1
else:
    c = Counter(A)
    if len(c) != 3:
        ans = False
    else:
        x, y, z = c.keys()
        ans = (x | y == z)
print('Yes' if ans else 'No')


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
if len(c) == 3:
    x, y, z = c.keys()
    ans = (c[x] == c[y] == c[z]) and (x ^ y == z)
elif len(c) == 2:
    ans = (0 in c) and (c[0] * 3 == N)
elif len(c) == 1:
    ans = 0 in c
else:
    ans = False
print('Yes' if ans else 'No')
K = int(input())
a = 0
n = 0
out = -1
for _ in range(K):
  a += 7 * (10 ** n)
  if a % K == 0:
    out = n + 1
    break
return print(out)


### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[A[i]//2 for i in range(len(A))]

import math
ans=B[0]
for i in range(1,N):
  ans=math.gcd(ans,B[i])
mul=B[0]//ans
for j in range(1,N):
  mul=mul*(B[j]//ans)
lcm=ans*mul

if all((lcm//b)%2==1 for b in B):
  Max=M//lcm
  if MaX%2==1:
    print((Max+1)//2)
  else:
    print((Max)//2)
else:
  print(0)


### FIXED CODE ###

K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")
x, t = imap(int, input().split())
print(x-t if x-t>0 else 0)

### FIXED CODE ###

x, t = map(int, input().split())
print(x-t if x-t>0 else 0)
import math

n, m = map(int, input().split())
item_price = list(map(int, input().split()))
# n, m = (3, 7)
# item_price = [1, 1, 1]
item_price.sort(reverse=True)
devided_two_price = [math.ceil(math.log2(i)) for i in item_price]
use_ticket_list = [0] * n
sum = 0

x = 0
a = 2
for i in range(m):
    if devided_two_price[x] == a:
        x += 1
        use_ticket_list[x] += 1
        devided_two_price[x] -= 1
    elif devided_two_price[x] >= devided_two_price[x+1]:
        use_ticket_list[x] += 1
        devided_two_price[x] -= 1
    else:
        x += 1
        use_ticket_list[x] += 1
        devided_two_price[x] -= 1
    if x == n-1:
        x = 0
        a -= 1

for i in range(n):
    sum += item_price[i] // (2**use_ticket_list[i])

print(sum)

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math

n, m = map(int, input().split())
item_price_list = list(map(int, input().split()))

item_price_list = list(map(lambda x: x*(-1), item_price_list))
heapify(item_price_list)
for i in range(m):
    a = heappop(item_price_list)
    heappush(item_price_list, math.ceil(a/2))
    
print((-1)*sum(item_price_list))
N = int(input())
A = [[x-1 for x in list(map(int, input().split()))][::-1] for i in range(N)]

def can_match(i, A, next_set):
    if not A[i]:
        return
    j = A[i][-1]

    if A[j][-1] == i:
        if i < j:
            next_set.add((i,j))
        else:
            next_set.add((j,i))

next_set = set()
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[1][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
# （１行読み込み→splitしてlist化→各要素に対して-1する）←を逆順にする（[::-1]）をN回繰り返す
A = [[x-1 for x in list(map(int, input().split()))][::-1] for i in range(N)]

def can_match(i, A, next_set):
    if not A[i]: # A[i]が空の場合
        return
    j = A[i][-1] # j = iさんの次の対戦相手

    if A[j][-1] == i: # jさんの次の対戦相手がiさんの場合（＝相思相愛の場合）
        if i < j: # 常に(小, 大)で格納する
            next_set.add((i,j))
        else: # 常に(小, 大)で格納する
            next_set.add((j,i))

# next_setの初期化
next_set = set() # setは集合を表す
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[match[1]][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)
a,b,c=map(int,input().split())
sum=a+b+c

if sum>21:
  print("bust")
  
  else:
    print("win")

### FIXED CODE ###

a,b,c=map(int,input().split())
val=a+b+c
if val > 21:
    print("bust")
else:
    print("win")
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

A,B=map(int, input().split())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
print(len(C)-count)

### FIXED CODE ###

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

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

A,B=map(int, input().split())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
  print(len(C)-count)
a,b=map(int,input().split())
m=1#初期値、受け口の数
n=0#初期値、ソケットの個数
 
while True:
  m += a-1
  n += 1
  if m>=b:
    break
print(n)

### FIXED CODE ###

a, b = map(int, input().split())
c = 0
sum = 1
while True:
    if sum>= b:
        print(c)
        break
    else:
        sum += a-1
        c+= 1
# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7

ans=1

if K==N:
    for i in range(N):
        ans*=A[i]
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]

print(ans%MOD)

### FIXED CODE ###

# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7

ans=1

if K==N:
    for i in range(N):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
elif max(A)<=0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1 and Ap:
        ans*=Ap.pop(0)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        k
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**7+1
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

    print(result%(10**9+7))

main()

### FIXED CODE ###

def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1

    for _ in range(0,K-1,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

    print(result%(10**9+7))

main()
m=input()
def s(x):
  if x=='1':
  	return '9'
  else:
    return '1'
print(s(m[0])+s(m[1])+s(m[2])

### FIXED CODE ###

m=input()
def s(x):
  if x=='1':
    return '9'
  else:
    return '1'
print(s(m[0])+s(m[1])+s(m[2]))
n = int(input())
card = list(map(int,input().split()))

card.sort()

ans = 0
for i in range(n//2+1):
            ans += card[2*i]-card[2*i+1]
if n%2==1:
            ans += card[-1]

print(ans)

### FIXED CODE ###

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

card.sort(reverse=True)

asum = 0
bsum = 0
for i in range(n):
  if i%2==0:
    asum += card[i]
  else:
    bsum += card[i]

print(asum-bsum)
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
xls = []
uls = []
for _ in range(N):
    x,u = input().split()
    if u == JPY:
        x = int(x)
    else:
        x = float(x)
    xls.append(x)
    uls.append(u)

answer = 0
for i in range(N):
    if uls[i] == JPY:
        money = xls[i]
    else:
        money = xls[i]*380000
    answer += money

print(answer)
    
 


### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())

answer = 0
for _ in range(N):
    x,u = input().split()
    if u == "JPY":
        money = float(x) 
    else:
        money = float(x)*380000.0
    answer += money
print(answer)
from scipy.misc import comb

MAX = 10**9 + 7

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * comb(M*N-2, K-2, exact=True)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

if __name__ == '__main__':
    solve()
import math
n = int(input())
l = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // math.gcd(ans, a[i])
print(ans - 1)


### FIXED CODE ###

import fractions
n = int(input())
l = list(map(int, input().split()))
m = l[0]
for i in range(1, n):
    m = m * l[i] // fractions.gcd(m, l[i])
m = m - 1
ans = 0
for i in l:
    ans += m % i
print(ans)
from more_itertools import pairwise

N = int(input())
H = [int(i) for i in input().split()]
cnt = 0
max_cnt = 0
for h, r in pairwise(H):
    if r <= h:
        cnt += 1
    else:
        max_cnt = max(max_cnt, cnt)
        cnt = 0

print(cnt)

### FIXED CODE ###

#from more_itertools import pairwise

N = int(input())
H = [int(i) for i in input().split()]
cnt = 0
max_cnt = 0
for h, r in zip(H, H[1:]):
    print()
    if r <= h:
        cnt += 1
    elif h < r and cnt:
        max_cnt = max(max_cnt, cnt)
        cnt = 0

ans = max(max_cnt, cnt)

print(ans)
a=int(input());print('Yes' if a[0]==a[2] else 'No')

### FIXED CODE ###

a=input();print('Yes' if a[0]==a[2] else 'No')
#ABC070-C TLE
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    g=gcd(a,b)
    return a/g*b

n=I()
t=[]
ans=1
for i in range(n):
    tmp=I()
    ans=lcm(ans,tmp)
print(int(ans))

### FIXED CODE ###

#ABC070-C TLE
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    g=gcd(a,b)
    return a*b//g

n=I()
t=[]
ans=1
for i in range(n):
    tmp=I()
    ans=lcm(ans,tmp)
print(ans)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




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

lst = [-1] * (N + 1)
for i in range(N):
    a = A[i]
    if lst[a] == -1:
        lst[a] = i
    else:
        left = lst[a]
        right = i
        break
# print (left, right)
F = Factorial(N + 1, MOD).comb

for i in range(1, N + 2):
    if left + N - right >= i - 1:
        tmp = F(N + 1, i) - F(left + (N- right), i - 1)
    else:
        tmp = F(N + 1, i)
    print (tmp % MOD)






### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second

U = 10 ** 5 + 1
def power_mod(a, n):
    if n == 0:
        return 1
    x = power_mod(a//2)

def make_fact(fact, fact_inv):
    for i in range(1, U + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    fact_inv[U] = pow(fact[U], MOD - 2, MOD)
    for i in range(U, 0, -1):
        fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n - k]
    x %= MOD
    return x

fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)

for i in range(1, n + 2):
    ans = comb(n + 1, i) - comb(left + right, i - 1)
    print (ans % MOD)
N = int(input())
a = list(map(int,input().split()))

S1 , S2 = {}, {}
for i in range(N):
    S1[a[i]] = S1.get(a[i], 0) + 1

for i in range(2 * N, 3* N):
    S2[a[i]] = S2.get(a[i], 0) + 1

i = N
j = 2 * N - 1

minS1 = min(S1)
maxS2 = max(S2)

while i <= j:
    delS1 = a[i] - minS1
    delS2 = maxS2 - a[j]

    if delS1 >= 0 and delS1 >= delS2:
        #print("chang S1")
        val = S1.pop(minS1)
        if val >= 2:
            S1[minS1] = val - 1
        S1[a[i]] = S1.get(a[i], 0) + 1
        minS1 = min(S1)
        i += 1

    elif delS2 >= 0:
        val = S2.pop(maxS2)
        if val >= 2:
            S2[minS2] = val - 1
        S2[a[j]] = S2.get(a[j], 0) + 1
        maxS2 = max(S2)
        j -= 1

    else:
        i += 1

sumS1, sumS2 = 0, 0
for i in S1.items():
    sumS1 += i[0] * i[1]
for j in S2.items():
    sumS2 += j[0] * j[1]

print(sumS1 - sumS2)



### FIXED CODE ###

from heapq import *

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

sumS1 = [0 for i in range(N + 1)]
S1 = a[0:N]
heapify(S1)
sumS1[0] = sum(S1)

for k in range(1, N + 1):
    if S1[0] < a[N + k - 1]:
        sumS1[k] = sumS1[k - 1] +a[N + k - 1] - S1[0]
        heapreplace(S1, a[N + k - 1])
    else:
        sumS1[k] = sumS1[k - 1]

sumS2 = [0 for i in range(N + 1)]
S2 =  [-1 * i for i in a[2 * N:3 * N]]
heapify(S2)
sumS2[N] = sum(S2)

for k in range(1, N + 1):
    if S2[0] < -1 * a[2 * N - k]:
        sumS2[N - k] = sumS2[N - k + 1] - a[2 * N - k] - S2[0]
        heapreplace(S2, -1 * a[2 * N - k])
    else:
        sumS2[N - k] = sumS2[N - k + 1]


res = [float("-inf")] * (N + 1)
for i in range(N + 1):
    res[i] = sumS1[i] + sumS2[i]

res.sort()
print(res[N])
import sys

a = raw_input()
b = raw_input()
c = raw_input()
 
print(a[0])
print(b[1])
print(c[2])

### FIXED CODE ###

a = input()
b = input()
c = input()
 
print(a[0]+b[1]+c[2])
import numpy as np
a,b = input().split()
print('{:.0f}'.np.ceil((int(a)+int(b))/2))

### FIXED CODE ###

import numpy as np
a,b = input().split()
print(int(np.ceil((int(a)+int(b))/2)))
s = input()
cnt = 0
ans = []
for i in s:
    if i == 'R':
        cnt += 1
    else:
        ans.append(cnt)
        cnt = 0
print(max(ans))

### FIXED CODE ###

s = input()
if s == 'RRR':
    print(3)
elif s == 'RRS' or s == 'SRR':
    print(2)
elif s == 'SSS':
    print(0)
else:
    print(1)
n,m = map(int,input().split())
ac,wa = 0,0
number=[0]*N

for m in range(m):
  p,s = input().split()
  p = int(p) - 1
  if number[p]!=1:
    if s == "WA":
      number[p]+=1
    elif s == "AC":
      ac+=1
      wa+=number[p]
      number[p]=-1
print(ac,wa)

### FIXED CODE ###

n,m = map(int,input().split())
ac,wa = 0,0
number=[0]*n

for i in range(m):
  p,s = input().split()
  p = int(p) - 1
  if number[p]!=-1:
    if s == "WA":
      number[p]+=1
    elif s == "AC":
      ac+=1
      wa+=number[p]
      number[p]=-1
print(ac,wa)
import numpy as np
a,b,h,m=map(float,input().split())
pi=np.pi
h_deg=(1/6)*pi*h
m_deg=(1/30)*pi*m
deg=abs(m_deg-h_deg)
if(deg>pi):
    deg=2*pi-deg
else:
    pass
c=a**2+b**2-2*a*b*np.cos(deg)
print(c**(1/2))
print(deg/pi)

### FIXED CODE ###

import numpy as np
a,b,h,m=map(int,input().split())
pi=np.pi
h_deg=(1/6)*pi*h+(1/360)*pi*m
m_deg=(1/30)*pi*m
deg=abs(m_deg-h_deg)
if(deg>pi):
    deg=2*pi-deg
else:
    pass
c=a**2+b**2-2*a*b*np.cos(deg)
print(c**(1/2))
import math

s = list(input())
t = list(input())
s.sorted()
t.sorted()
if s < t:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import math

s = list(input())
t = list(input())
s.sort()
t.sort()
t.reverse()
if s < t:
    print('Yes')
else:
    print('No')
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = (['#'] + list(input()) + ['#'] for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)

step = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1)
       if a[i][j] == '#']

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)


### FIXED CODE ###

h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)
n = int(input())
count = 0
dic = {}
for _ in range(n):
    key = ''.join(sorted(input()))
    if key in dic:
        c += dic[key]
        dic[key] += 1
    else:
        dic[key] = 1
print(count)

### FIXED CODE ###

n = int(input())
count = 0
dic = {}
for _ in range(n):
    key = ''.join(sorted(input()))
    if key in dic:
        count += dic[key]
        dic[key] += 1
    else:
        dic[key] = 1
print(count)
# https://atcoder.jp/contests/abc159/tasks/abc159_d

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

box = [0] * (N + 1)
box_2 = [0] * (N + 1)
box_3 = [0] * (N + 1)

for i in range(N):
    box[A_list[i] + 1] += 1

for i in range(N):
    if box[i] > 1:
        box_2[i] = (box[i] * (box[i] - 1)) / 2
        box_3[i] = ((box[i] - 1) * (box[i] - 2)) / 2

ans_base = sum(box_2)

for i in range(N):

    if box[A_list[i]] > 0:
        diff = box_2[A_list[i]] - box_3[A_list[i]]
        print(int(ans_base - diff))
    else:
        print(int(ans_base))
    


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/tasks/abc159_d

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

box = [0] * (N + 1)
box_2 = [0] * (N + 1)
box_3 = [0] * (N + 1)

for i in range(N):
    box[A_list[i]] += 1

for i in range(N + 1):
    if box[i] > 1:
        box_2[i] = (box[i] * (box[i] - 1)) / 2
        box_3[i] = ((box[i] - 1) * (box[i] - 2)) / 2

ans_base = sum(box_2)

for i in range(N):

    if box[A_list[i]] > 0:
        diff = box_2[A_list[i]] - box_3[A_list[i]]
        print(int(ans_base - diff))
    else:
        print(int(ans_base))
N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(N-1,0)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])