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

import sys
sys.setrecursionlimit(4100000)

from collections import Counter

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

for i in range(K):
    C, D = map(int, input().split())
    if graph_g[C-1] == graph_g[D-1]:
        block[C-1].append(D-1)
        block[D-1].append(C-1)

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

from collections import Counter

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return 0

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        if graph_g[edge] == None:
            dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

for i in range(K):
    C, D = map(int, input().split())
    if graph_g[C-1] == graph_g[D-1]:
        block[C-1].append(D-1)
        block[D-1].append(C-1)

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)
### BUGGY CODE ###

h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
# print(a_list)
# if (max(h_list), max(w_list)) in a_list:
#     print(a)
#     print(max(h_list) + max(w_list) - 1)
# else:
#     print(max(h_list) + max(w_list))
w_flag = []
for i in range(w):
    if w_list[i] == max(w_list):
        w_flag.append(i)
h_flag = []
for i in range(h):
    if h_list[i] == max(h_list):
        h_flag.append(i)
ans = []
for i in w_flag:
    for j in h_flag:
        if [j + 1, i + 1] not in a_list:
            # ans.append(max(h_list) + max(w_list) - 1)
            print(max(h_list) + max(w_list))
            exit()
print(max(h_list) + max(w_list) - 1)
            

### FIXED CODE ###

h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
h_max = max(h_list)
w_max = max(w_list)
w_flag = [0 for _ in range(w)]
for i in range(w):
    if w_list[i] == w_max:
        w_flag[i] = 1
h_flag = [0 for _ in range(h)]
for i in range(h):
    if h_list[i] == h_max:
        h_flag[i] = 1
flag = 0   
for i in range(m):
    if h_flag[a_list[i][0] - 1] == 1 and w_flag[a_list[i][1] - 1] == 1:
        flag += 1
s = sum(h_flag) * sum(w_flag)
print(h_max + w_max - 1 if flag == s else h_max + w_max)
### BUGGY CODE ###

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

AA = [0]*1000000

for i in range(N):
    ma = 1000000//A[i]
    for j in range(1,ma+1):
        AA[j*A[i]-1]+=1

ans = 0

for i in range(N):
    if AA[A[i]-1] == 1:
        ans += 1
        
print(ans)

### FIXED CODE ###

import math
N = int(input())
A = list(map(int,input().split()))
M = max(A)
cnt = [0 for i in range(M)]
for i in range(N):
    if cnt[A[i]-1] != 0:
        cnt[A[i]-1] = 2
    else:
        j = A[i]-1
        while j<M:
            cnt[j] += 1
            j += A[i]

ans = 0
for i in range(N):
    if cnt[A[i]-1] == 1:
        ans += 1
        
print(ans)
### BUGGY CODE ###

import heapq


def inpl():
    return list(map(int, input().split()))


N, M, S = inpl()
A = 51  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)


### FIXED CODE ###

import heapq

INF = 10**20
A = 50  # max A


def inpl():
    return list(map(int, input().split()))


def main():
    N, M, S = inpl()
    S = min(S, M * A)

    lines = [[] for _ in range(N * (M * A + 1))]
    for _ in range(M):
        in_s, in_t, cost, time = inpl()
        in_s -= 1
        in_t -= 1

        for n in range(cost, M * A + 1):
            s = in_s + n * N
            t = in_t + (n - cost) * N
            lines[s].append((t, time))

            s = in_s + (n - cost) * N
            t = in_t + n * N
            lines[t].append((s, time))

    for i in range(N):
        cost, time = inpl()
        for n in range(0, M * A + 1):
            s = i + n * N
            if n + cost > M * A:
                t = i + (M * A) * N
            else:
                t = i + (n + cost) * N
            lines[s].append((t, time))

    def dijkstra(N, S):
        weight = [INF] * N
        weight[S] = 0
        q = [[0, S]]
        heapq.heapify(q)
        while q:
            w0, s = heapq.heappop(q)
            for t, w in lines[s]:
                w += w0
                if weight[t] > w:
                    heapq.heappush(q, [w, t])
                    weight[t] = w

        return weight

    weight = dijkstra(N * (M * A + 1), 0 + S * N)

    ansl = [INF] * N
    for i, w in enumerate(weight):
        n = i % N
        if n == 0:
            continue
        else:
            ansl[n] = min(w, ansl[n])

    print("\n".join(map(str, ansl[1:])))


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

n=int(input())
a=[int(x) for x in input().split()]
m=1
for i in a:
  m*=i
print(m if m <= 10**18 else -1)

### FIXED CODE ###

import sys
n=int(input())
a=[int(x) for x in input().split()]
a=sorted(a, reverse=True)
m=1
if a[-1] == 0:
  print(0)
else:
  for i in a:
    m*=i
    if m > 10**18:
      print('-1')
      sys.exit()
  print(m)
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

s = input()

sl = list(s)
sl.append("2")

n = len(sl)
res=[]

temp =1
for i  in range(n-1):
    if sl[i+1] == sl[i]:
        temp +=1
    else:
        res.append(temp)
        temp = 1

resu = n-1

while len(res) >1:
    if res[0] > sum(res[1:]):
        resu = min(resu,res[0])
        x = res.pop(1)
        res[0] = res[0]+x
    else:
        resu = min(resu,sum(res[1:]))
        x = res.pop(1)
        res[0] =res[0]+x

print(resu)

### FIXED CODE ###

s = input()

sl = list(s)
sl.append("2")

n = len(sl)
res=[]

temp =1
for i  in range(n-1):
    if sl[i+1] == sl[i]:
        temp +=1
    else:
        res.append(temp)
        temp = 1

resu = n-1
m = n-1

while len(res) >1:
    resu = min(resu,max(res[0],m-res[0]))
    x = res.pop(1)
    res[0]  = res[0]+x    
    
print(resu)
### BUGGY CODE ###

def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):
        prev = dp[i-1]
        crr = dp[i]
        if i < c:
            next = dp[i+1]
        for j in range(d+1):
            if i > 0 and j > 0:
                if i == j == 1:
                    crr[j] -= (A+i-1) * (B+j-1)
                else:
                    tmp = prev[j-1]
                    #print(tmp, i, j)
                    tmp *= (A+i-1)*(B+j-1)

                    # print(crr[j], tmp)
                    crr[j] -= tmp

            if i < c:
                next[j] += crr[j]*(B+j)
            if j < d:
                crr[j+1] += crr[j]*(A+i)
            # print(dp)
            crr[j] %= mod

    print(dp[c][d])


main()


### FIXED CODE ###

def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            ret = 0
            if i == 0 and j == 0:
                continue
            if i > 0 and j > 0:
                if i == j == 1:
                    ret -= (A+i-1) * (B+j-1)
                else:
                    ret -= dp[i-1][j-1]
                    ret *= (A+i-1)*(B+j-1)
            ret += dp[i-1][j]*(B+j) + dp[i][j-1]*(A+i)

            ret %= mod
            dp[i][j] = ret
    print(dp[c][d])


main()
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
arr = list(map(int, input().split()))
heapq.heapify(arr)
for i in range(M):
    B, C = map(int, input().split())
    count = 0
    while True:
        a = heapq.heappop(arr)
        if a >= C or B <= count:
            heapq.heappush(arr,a)
            break
        else:
            count += 1
            heapq.heappush(arr,C)
print(sum(arr))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(M)]
heapq.heapify(a)
bc = sorted(bc, reverse=True, key=lambda x: x[1])
for i in range(M):
    count = 0
    while True:
        t = heapq.heappop(a)
        if t >= bc[i][1] or bc[i][0] <= count:
            heapq.heappush(a,t)
            break
        else:
            count += 1
            heapq.heappush(a,bc[i][1])
print(sum(a))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

(R,C,K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

grids = [[0]*C for _ in range(R)]

for r,c,v in rcv:
    grids[r-1][c-1] = v

from collections import defaultdict
dp = defaultdict(int)

for r in range(R):
    for c in range(C):
        value = grids[r][c]
        for i in range(1,4):
            dp[r,c,i] = dp[r,c-1,i]
            if i == 1:
                dp[r,c,i] = max(dp[r,c,i], max(dp[r-1,c,j] for j in range(1,4)) + value)
            dp[r,c,i] = max(dp[r,c,i], dp[r,c-1,i-1] + value)

print(max(dp[R-1,C-1,j] for j in range(4)))

### FIXED CODE ###

# from sys import stdin
# input = stdin.readline
(R,C,K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
 
grids = [[0]*C for _ in range(R)]
 
for r,c,v in rcv:
    grids[r-1][c-1] = v
 
dp = [0] * C

for r in range(R):
#     print(dp)
    ndp = [0] * C
    elm = [0] * 4
    for c in range(C):
        elm[0] = max(elm[0], dp[c])
        value = grids[r][c]
        if value:
            nelm = [0] * 4
            nelm[0] = elm[0]
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            for i in range(3)[::-1]:
                nelm[i + 1] = max(elm[i + 1], elm[i] + value)
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            elm = nelm
        ndp[c] = max(elm)
    dp = ndp
 

print(dp[-1])
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b
    a, b, c = a % MOD, b % MOD, c % MOD

ans = c % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: n * d}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost
            memo[0] = min(memo[0], cost + m * d)

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
                dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
                dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

    dfs(n, 0)
    print(memo[0])


### FIXED CODE ###

import sys
from heapq import heappush, heappop
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)


def solve(n, a, b, c, d):
    MAX = n * max(a, b, c, d) + 1
    memo = defaultdict(lambda: MAX)

    def dfs(m, cost):
        if memo[m] <= cost:
            return
        memo[m] = cost

        if m > 0:
            dfs(m // 2, cost + (m % 2) * d + a)
            dfs(m // 3, cost + (m % 3) * d + b)
            dfs(m // 5, cost + (m % 5) * d + c)

            dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
            dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
            dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

            dfs(0, cost + m * d)

    dfs(n, 0)
    return memo[0]


t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    ans = solve(n, a, b, c, d)
    print(ans)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def dfs(y0, y1, x0, x1):
    global k
    m = 0
    tmp = []
    for i in range(y0, y1):
        for j in range(x0, x1):
            a[i][j] = k
            if s[i][j] == '#':
                tmp.append([i, j])
                m += 1
            if m == 2:
                break
    if m == 1:
        k -= 1
    else:
        if tmp[0][0] != tmp[1][0]:
            pos = max(tmp[0][0], tmp[1][0])
            dfs(y0, pos, x0, x1)
            dfs(pos, y1, x0, x1)
        else:
            pos = max(tmp[0][1], tmp[1][1])
            dfs(y0, y1, x0, pos)
            dfs(y0, y1, pos, x1)

h, w ,k = MAP()
s = []
a = [[0]*w for i in range(h)]
for i in range(h):
    s.append(input())

dfs(0, h, 0, w)
for i in range(h):
    print(*a[i][:])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][m] == '#':
                a[i][m] = num
                m += 1
            if m < w:
                for j in range(m, w):
                    if s[i][j] == '#':
                        num += 1
                    a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][0] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][0] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])
### BUGGY CODE ###

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

l.sort()
count = 0

for i in range(n) :
    for j in range(1, n - i) :
        for k in range(1, n - i - j) :
            if l[i] + l[i + j] > l[i + j + k] :
                count += 1

print(count)

### FIXED CODE ###

from bisect import bisect_left

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

l.sort()
count = 0

for i in range(n - 2) :
    for j in range(i + 1, n - 1) :
        idx = bisect_left(l, l[i] + l[j])
        count += idx - (j + 1)

print(count)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
count =0

for i in range(k):
    if(a > 0):
        count += 1
        a -= 1
    elif(b > 0):
        count += 0
        b -= 1
    elif(c > 0):
        count += -1
        c -= 1
print(count)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
count = 0
if(a > k):
    count = k
elif(a + b > k):
    count = a
else:
    tmp = k -(a + b)
    count = a - tmp
print(count)
### BUGGY CODE ###

import math
N = 10**9+7
n = int(input())
a = list(map(int,input().split()))

ans = 0

a1 = max(a)
if a1 == 0:
    a1=2
ma = int(math.log2(a1))
if ma<0:
    ma=0
for i in range(ma+2):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*pow(2,i,N)
    ans%=10**9+7
print(ans)


### FIXED CODE ###

import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=np.count_nonzero(bit)
    ans+=s*(n-s)%N*po
    ans%=N
    po*=2
    po%=N
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for n in range(N):
    s = S[n]
    if s!='?':
        s = int(s)*(10**(N-n-1))%13
        for i in range(13):
            idx = (s+i)%13
            dp[n+1][idx] = dp[n][i]%mod
    else:
        for i in range(10):
            s = i*(10**(N-n-1))%13
            for j in range(13):
                idx = (s+j)%13
                dp[n+1][idx] += dp[n][j]%mod

print(dp[-1][5]%mod)

### FIXED CODE ###

S = input()
N = len(S)
dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for n in range(N):
    s = S[n]
    if s!='?':
        s = int(s)*pow(10, (N-n-1), 13)%13
        for i in range(13):
            idx = (s+i)%13
            dp[n+1][idx] = dp[n][i]%mod
    else:
        for i in range(10):
            s = i*pow(10, (N-n-1), 13)%13
            for j in range(13):
                idx = (s+j)%13
                dp[n+1][idx] += dp[n][j]%mod

print(dp[-1][5]%mod)
### BUGGY CODE ###

# ABC 65, B - trained
n = int(input())
A = [int(input()) for i in range(n)]
went = []
now = 1
for i in range(n):
    if now in went:
        print(-1)
        break
    if now == 2:
        print(i)
        break
    went.append(now)
    now = A[now-1]


### FIXED CODE ###

# ABC 65, B - trained
n = int(input())
A = [int(input()) for i in range(n)]
now = 1
went = set()
for i in range(n):
    if now == 2:
        print(i)
        break
    if now in went:
        print(-1)
        break
    went.add(now)
    now = A[now-1]
### BUGGY CODE ###

S = str(input())

ans = 0
for i in range(len(S)):
  for j in range(i+3, len(S)):
    if int(S[i:j+1]) % 2019 == 0:
      ans += 1
      
print(ans)

### FIXED CODE ###

S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

print(ans)
### BUGGY CODE ###

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

Ai_i = []

for i in range(len(A)):
    Ai_i.append(A[i] - (i+1))

max_abs = 0
for i in range(len(Ai_i)):
    if abs(Ai_i[i]) > max_abs:
        max_abs = abs(Ai_i[i])


min_abs = float("inf")
min_index = 0

for b in range(-max_abs, max_abs+1):
    abss = []
    for i in range(len(Ai_i)):
        abss.append(abs(Ai_i[i] + b))
    abs_sum = sum(abss)
    if abs_sum < min_abs:
        min_abs = abs_sum

print(min_abs)


### FIXED CODE ###

from math import ceil, floor
import statistics

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

Ai_i = [0 for i in range(len(A))]

for i in range(len(A)):
    Ai_i[i] = A[i] - (i+1)

n = 5

b_ceil = ceil(sum(Ai_i) / len(Ai_i))

bs = list(range(b_ceil-n, b_ceil+n))

bs = [int(statistics.median(Ai_i))]
abss_ls = [ 0 for i in range(len(bs)) ]
for i in range(len(bs)):
    for j in range(len(Ai_i)):
        abss_ls[i] += abs(Ai_i[j] - bs[i])

min_abs = min(abss_ls)
print(min_abs)
### BUGGY CODE ###

N,K=map(int,input().split())
def wa(N,K):
    a=0
    for i in range(0,K):
        a=a+N-2*i
    return a+1
d=0
for i in range(K,N+1):
  d=d+wa(N,i)
print((d+1)%(10**9+7))


### FIXED CODE ###

N,K=map(int,input().split())
def wa(N,K):
    return K*(N+1-K)+1
d=0
for i in range(K,N+2):
  d=d+wa(N,i)
print((d)%(10**9+7))