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

h, w = map(int, input().split())
a=[]
for i in range(h):
  a.append([it == '#' for it in input()])
q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]: q.append((i, j))
cnt = -1
while q:
  cnt += 1
  r = []
  for i, j in q:
    if i > 0 and not a[i-1][j]:
      a[i-1][j]=True
      r += [(i-1, j)]
    if i < h-1 and not a[i+1][j]:
      a[i+1][j]=True
      r += [(i+1, j)]
    ai = a[i]
    if j > 0 and not ai[j-1]:
      ai[j-1]=True
      r += [(i, j-1)]
    if j < w-1 and not ai[j+1]:
      ai[j+1]=True
      r += [(i, j+1)]
  q=r
print(cnt)



### FIXED CODE ###

def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

from functools import lru_cache
N = int(input())
S = input()

c = S.count('1')
m = int('0B'+S, 0)

@lru_cache(maxsize=None)
def calc(a, ans):
    if a == 0: return ans
    ans += 1
    m = bin(a).count('1')
    return calc(a%m, ans)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)

    print(calc(a, 0))
    


### FIXED CODE ###

import math
N = int(input())
S = input()

lst0 = [0]*N
lst1 = [0]*N
lst0[0] = 1
lst1[0] = 1
c = S.count('1')
m0 = int(S[-1])
m1 = int(S[-1])
for i in range(1, N):
    lst0[i] += (lst0[i-1]*2)%(c+1)
    if c == 1:lst1[i] = 0
    else: lst1[i] += (lst1[i-1]*2)%(c-1)
    m0 += lst0[i] * int(S[N - 1- i])
    m0 %= c+1
    m1 += (lst1[i] * int(S[N - 1 - i]))
    if c == 1: m1 = 0
    else: m1 %= c-1

memo = [0]*(N+1)

def calc(a):
    global ans, memo
    if a == 0: return ans
    ans += 1
    if memo[a] != 0:
        b = memo[a]
    else:
        b = bin(a).count('1')
        memo[a] = b
    return calc(a%b)
    
for i in range(N):
    if S[i] == '1':
        b = c - 1
        if b == 0: a = 0
        else: a = max((m1 - lst1[N - 1 - i])%b, (m1 - lst1[N - 1 - i]+ b)%b)
    else:
        b = c + 1
        a = (m0 + lst0[N - 1 - i])%b
    if b == 0: print(0)
    elif a == 0:print(1)
    else:
        ans = 1
        print(calc(a))
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

cs = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
    for j in range(w):
        cs[i + 1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

# print(*cs, sep='\n')
# print()

ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1 == 1:
            border.append(i + 1)
            cand += 1
    border.append(h)
    cand0 = cand
    j0 = 0
    cut = []
    j = 1
    while j <= w:
        # for j in range(1, w + 1):
        for i in range(len(border) - 1):
            # print(
            #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
            #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
            if cs[border[i + 1]][j] - cs[border[i + 1]][j0] - cs[
                    border[i]][j] + cs[border[i]][j0] > k:
                cand += 1
                j0 = j - 1
                j -= 1
                cut.append(j - 1)
                # print(border[i + 1], j, cs[border[i + 1]][j])
                break
        j += 1

    # print(border, cand0, cand, cut)
    ans = min(ans, cand)
print(ans)


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
indeg = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    G[r].append((l, d))
    indeg[r] += 1

from collections import deque
ng = False
visited = [0] * n
for start, deg in enumerate(indeg):
    if deg == 0 or visited[start] == 1:
        continue
    st = deque([[start, 0]])
    visited_cost = [-1] * n
    while st:
        i, cost = st.pop()
        for ni, nd in G[i]:
            if visited_cost[ni] == -1:
                # まだ記録されていない
                visited_cost[ni] = cost + nd
                st.append([ni, cost + nd])
            elif visited_cost[ni] == cost + nd:
                visited[ni] = 1
                continue
            else:
                # 既に記録されていて、矛盾している場合
                # 終了
                ng = True
                break
        if ng:
            break
    if ng:
        break

print('No' if ng else 'Yes')

### FIXED CODE ###

n, m = map(int, input().split())
G = [[] for _ in range(n)]
indeg = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    G[l].append((r, d))
    G[r].append((l, -d))

from collections import deque
ng = False
visited = [0] * n
visited_cost = [0] * n

for start in range(n):
    if visited[start]:
        continue
    visited[start] = 1
    st = deque([[start, 0]])
    while st:
        i, cost = st.pop()
        for ni, nd in G[i]:
            if visited[ni] == 0:
                visited[ni] = 1
                visited_cost[ni] = cost + nd
                st.append([ni, cost + nd])
            else:
                # 既に記録されていて、矛盾している場合
                if visited_cost[ni] != cost + nd:
                    # 終了
                    ng = True
                    break
        if ng:
            break
    if ng:
        break
print('No' if ng else 'Yes')
### BUGGY CODE ###

N, M = map(int, input().split())
cards = sorted(list(map(int, input().split())))
operation = []

for _ in range(M):
    operation.append(tuple(map(int, input().split())))

operation.sort(key=lambda x:x[1], reverse=True)

for ope in operation:
    FLG = False
    for j in range(ope[0]):
        if cards[j] < ope[1]:
            cards[j] = ope[1]
        else:
            FLG = True
            break
    if FLG:
        break
    cards.sort()

print(sum(cards))

### FIXED CODE ###

from collections import deque


N, M = map(int, input().split()) 
operation = [[1, card] for card in map(int, input().split())]

for _ in range(M):
    operation.append(list(map(int, input().split())))

operation.sort(key=lambda x:x[1], reverse=True)
operation = deque(operation)

maximum = 0
for _ in range(N):
    maximum += operation[0][1]
    operation[0][0] -= 1
    if operation[0][0] == 0:
        operation.popleft()

print(maximum)
### BUGGY CODE ###

import math

def comb(a,b):
  return math.factorial(a)//((math.factorial(b)*math.factorial(a-b)))

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

a.sort()
ans=-1
for i in range(N-1):
  if ans<comb(a[-1],a[i]):
    ans=comb(a[-1],a[i])
    max_i=i
print(a[-1],a[max_i])

### FIXED CODE ###

import math

def comb(a,b):
  return math.factorial(a)//((math.factorial(b)*math.factorial(a-b)))

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

a.sort()
a_max=a[-1]
a=a[:-1]
#print(a)

b = [[abs(i+(-a_max//2)),i] for i in a]
b.sort()
print(a_max, b[0][1])
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for i in range(q)]
if k>q:
    for i in range(n):
        print('Yes')
else:
    for i in range(1,n+1):
        print('Yes' if k-len(a)+a.count(i)>0 else 'No')

### FIXED CODE ###

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

import math
R, G, B, N = map(int, input().split())
rg_lis = []
ans = 0
cr = math.ceil(N/R)
cg = math.ceil(N/G)
cb = math.ceil(N/B)
for i in range(cr + 1):
    for j in range(cg + 1):
        tmp =  i * R + j * G
        if N - tmp >= 0:
            rg_lis.append(tmp)
        else:
          break
for l in rg_lis:
    if (N - l )% B == 0:
        ans += 1
print(ans)


### FIXED CODE ###

import math
R, G, B, N = map(int, input().split())
ans = 0
cr = math.ceil(N/R)
cg = math.ceil(N/G)
cb = math.ceil(N/B)
for i in range(cr + 1):
    for j in range(cg + 1):
        tmp =  i * R + j * G
        if N - tmp >= 0 and (N - tmp) % B == 0:
           ans += 1
        elif N - tmp < 0:
          break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    Query.append([c,b])
Query.sort(reverse=True)
for i in range(m):
    b,c = Query[i][1],Query[i][0]
    if min(A) >= c:
        break
    else:
        #A.sort()
        index = bisect.bisect_left(A,c)
        if b <= index:
            #for i in range(b):
            #    A[i] = c
            A = A[b:index] + [c for i in range(b)] + A[index:]
        else:
            #for i in range(index):
            #    A[i] = c
            A = [ c for i in range(index)] + A[index:]
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

N,T = map(int,input().split())
import bisect
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)

### FIXED CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)
### BUGGY CODE ###

import copy
from collections import deque
import numpy as np

h, w = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = np.full_like(s, 0).astype(int)
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and grid[cx + mx][cy + my] == 0:
                        if s[cx][cy] != s[cx + mx][cy + my]:
                            grid[cx + mx][cy + my] = grid[cx][cy] + 1
                            q.append((cx + mx, cy + my))
            grid = grid.flatten()
            grid[np.where(grid == 0)] = 1
            ans += (grid % 2 == 0).sum()
        else:
            continue

print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)
### BUGGY CODE ###

N, P = map(int, input().split())
S = list(map(int,list(input())))
U = []


for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp % P)
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))

### FIXED CODE ###

N, P = map(int, input().split())
S = list(map(int,list(input())))
U = [0 for i in range(N+1)]
POW = [1 for i in range(N)]

for i in range(N-1):
    POW[i+1] = (POW[i]*10) % P

for i in range(N):
    U[N-(i+1)] = (U[N-i] + S[N-1-i] * POW[i]) % P
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))
### BUGGY CODE ###

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  
  c=[[0]*w for i in range(h)]
  for i in range(h):
    for j in range(w):
      c[i][j]=abs(a[i][j]-b[i][j])
  
  dp=[[[] for i in range(w)] for j in range(h)]
  dp[0][0].append(c[0][0])
  for i in range(h):
    for j in range(w):
      for k in range(len(dp[i-1][j])):
        dp[i][j].append(abs(dp[i-1][j][k]-c[i][j]))
        dp[i][j].append(dp[i-1][j][k]+c[i][j])
      for k in range(len(dp[i][j-1])):
        dp[i][j].append(abs(dp[i][j-1][k]-c[i][j]))
        dp[i][j].append(dp[i][j-1][k]+c[i][j])
      dp[i][j]=list(set(dp[i][j]))
  print(min(dp[h-1][w-1]))

if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

import functools

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


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

mod=functools.reduce(gcd,A)

tmp=0
amax=max(A)
while 1:
  if amax-mod*tmp==K:
    print('POSSIBLE')
    exit()
  elif amax-mod*tmp<0:
    break
  tmp+=1
print('IMPOSSIBLE')


### FIXED CODE ###

import functools
from fractions import gcd
N,K=map(int,input().split())
A=list(map(int,input().split()))


mod=functools.reduce(gcd,A)

tmp=0
if max(A)>=K and K%mod==0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
p[0]=1

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    p[i-1]=p[j-1]
                else:
                    p[j-1]=p[i-1]

for i,a in enumerate(p):
    if i!=a-1 and a>=0 and p.count(i+1)>1:
        p=[a if k==i+1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

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

print(max(rank))
### BUGGY CODE ###

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

def count_inversion(input_array):
    n = len(input_array)
    s = [0 for _ in range(2 * n + 2)]
    res = 0
    for a in input_array:
        s[a + n] += 1
        res += sum(s[a + n + 1:])
    return res

b = list(sorted(set(a)))

m = n * (n + 1) // 4 + 1

ans = len(b) // 2

l = 0
r = len(b) - 1

while 1:
    s = [0 for _ in range(n)]
    s[0] = 0
    for i in range(1,n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    if count_inversion(s) > m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

### FIXED CODE ###

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])
### BUGGY CODE ###

N=int(input())
x=[int(input()) for _ in range(N)]

#x=dict(zip(range(1,N+1),a))
#print(x)
route=[1,]
#for _ in range(N):
while 2 not in route:
  #print(x[route[-1]])
  if route[-1]==2:
    break
  elif x[route[-1]-1] not in route:
    route.append(x[route[-1]-1])
  else:
    print(-1)
    exit()
    
print(len(route)-1)

### FIXED CODE ###

N=int(input())
x=[int(input()) for _ in range(N)]

on=1
ans=0
for _ in range(N):
  on=x[on-1]
  ans=ans+1
  if on==2:
    print(ans)
    exit()
  
print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
result = 0
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(i+1, N):
    calc = result + A[i] * A[j]
    compare = calc // mod
    result = calc if compare < 1 else calc - compare * mod
print(result)

### FIXED CODE ###

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

mod = 10 ** 9 +7
amount = sum(A)
calc = []
for i in range(N - 1):
  amount = amount - A[i]
  calc.append(amount)

for i in range(N - 1):
  calc[i] *= A[i]

print(sum(calc) % mod)
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
C = readline().decode().rstrip()

w_idx = []
r_idx = []
for i, c in enumerate(C):
    if c == 'W':
        w_idx.append(i)
    else:
        r_idx.append(i)

if (len(w_idx) == 0) | (len(r_idx) == 0):
    print(0)
    sys.exit()

cnt = 0

while w_idx[0] < r_idx[-1]:

    w_acc = w_idx.pop(0)
    r_acc = r_idx.pop(-1)
    w_idx.append(r_acc)
    r_idx.append(w_acc)
    w_idx.sort()
    r_idx.sort()
    cnt += 1

print(cnt)

### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
C = readline().decode().rstrip()

l, r = 0, N - 1
cnt = 0

while l < r:
    if C[l] == 'R':
        l += 1
    elif C[r] == 'W':
        r -= 1
    else:
        l += 1
        r -= 1
        cnt += 1

print(cnt)
### BUGGY CODE ###

S = input()

cnt = 0

for i in range(len(S)):
    if (i != 0):
        if S[i] == 'W':
            for _ in range(i):
                if S[_] == 'B':
                    cnt += 1

print(cnt)

### FIXED CODE ###

S = input()

cnt = 0
cnt_B = 0

for i in range(len(S)):
    if S[i] == 'W':
        cnt += cnt_B
    else:
        cnt_B += 1

print(cnt)