Harryxun/stf_run huggingface dataset:
MOD = 10 ** 9 + 7

s = str(input())
sl = list(s)
si = list(map(int,s))

cur = [0] * 13

if s[0] != "?":
    cur[si[0]] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + si[i]) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD

print(cur[5] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)
a,b,n = map(int, input().split())

t=0
xx=1
l=[-1]*(b+1)
p=1
d=b//a
if n>=b and b>1:
   while t == 0 and xx <= n:
      c=a*xx%b
      if l[c]==-1:
         l[c]=xx
      else:
         t=1
      xx+=d
   while t>-1:

      if l[p]>-1:
         t=-2
         x=l[p]
      p+=1
else:
   x=n
print(a*x//b-a*(x//b))


### FIXED CODE ###


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


if n>=b-1:
    x=b-1
else:
    x=n
print(a*x//b-a*(x//b))
N = int(input())
x = int(input())
y=x
cage = list(map(int,input().split()))
ans=0
for i in range(N):
    ind = cage.index(min(cage))
    if(min(cage) > x):
        break
    x = x - min(cage)
    cage[ind] = y
    ans += 1
if x>0:
    ans = ans - 1
print(ans)

### FIXED CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
 
x_tmp = x
for i, Ai in enumerate(sorted(A)):
    x_tmp -= Ai
    if x_tmp == 0:
        ans = i + 1
        break
    elif x_tmp < 0:
        ans = i
        break
    else: continue
else: ans = i
 
print(ans)
from heapq import heappush, heappop

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge.sort(key=lambda x: (x[1], x[0]))

q = [(1, 0)]
for l, r, c in edge:
    # print((l, r, c), q)

    if r < q[0][0]:
        continue

    cand = float("inf")
    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

    for y, z in q:
        if y < r:
            cand = min(cand, z)
        else:
            heappush(q, (y, z))
            break

    if cand != float("inf"):
        heappush(q, (r, cand + c))

# print(q)

ans = -1
for y, z in q:
    if y == n:
        if ans == -1:
            ans = z
        else:
            ans = min(ans, z)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    INF = float('inf')
    dist = [INF] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap, (dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edge[l].append((c, r))
for i in range(1, n):
    edge[i].append((0, i - 1))

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

print(ans)
A,B,X = map(int,input().split)
if (A <= X <= (A + B)):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

A,B,X = map(int,input().split())
if (A <= X <= (A + B)):
    print('YES')
else:
    print('NO')
N = int(input())
S = list(map(int, list(input()))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = True
            flag2 = True

            for a in S:
                if flag1:
                    if a == i:
                        flag1 = False
                elif flag2:
                    if a == j:
                        flag2 = False
                elif a == k:
                    cnt += 1
                    break

print(cnt)

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            pin = [i, j, k]
            x = 0

            for a in S:
                if a == pin[x]:
                    x += 1
                    if x == 3:
                        cnt += 1
                        break

print(cnt)
import math
n,k = map(int,input().split())
sl = [0]*n
dl = [0]*n
tree = [[] for i in range(n)]
mod = 10**9+7

for i in range(n-1):
  a,b = map(int,input().split())
  tree[a-1] += [b-1]
  tree[b-1] += [a-1]

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

def dfs(x,depth,k):
  sl[x] = 1
  dl[depth] += 1
  child = 0
  ans = 1
  for i in tree[x]:
    if sl[i] == 0:
      ans *= dfs(i,depth+1,k)
      ans %= mod
      child += 1
  if depth == 0:
    ans *= perm(k-1,child)
    ans %= mod
  else:
    ans *= perm(k-2,child)
    ans %= mod
  return ans

print(dfs(0,0,k)*k%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9+7

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

if __name__ == '__main__':
    main()
a,b,c=map(int,input().split())
print(a<b<c?"Yes":"No")

### FIXED CODE ###

a,b,c=map(int,input().split())
print(('No','Yes')[a<b<c])
n,m=map(int,input().split())
a=list(map(int,input().split() for i in range(n)))
for i in range(1,n+1):
    print(a.count(i))


### FIXED CODE ###

n,m=map(int,input().split())
li=[]
for i in range(m):
    a,b=map(int,input().split())
    li.append(a)
    li.append(b)

for j in range(1,n+1):
    print(li.count(j))
k = input()
a = int(k)
l = input()
b = int(l)

if a*b%2 == 0:
    print('Even')
else:
    print('Odd')

### FIXED CODE ###

a,b = (int(x) for x in input().split())
c = (a*b) % 2 
if c == 0:
    print('Even')
else:
    print('Odd')
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

blue = K
red = N-K

n = red+1

ans = []
for i in range(1, blue+1):
    if i == 1 or i == blue:
        ans.append(cmb(n, i))
    else:
        tmp = 1
        tmpn = n
        for j in reversed(range(1, i+1)):
            tmp *= cmb(tmpn, 1)
            tmpn -= 1
        ans.append(tmp)

for s in ans:
    print(s%(10**9+7))

### FIXED CODE ###

from math import factorial

def cmb(n,k):
    if n < k or n < 0 or k < 0:
        return 0
    return factorial(n)//(factorial(k)*factorial(n-k))

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

for i in range(1, K+1):
    ans = cmb(K-1, i-1) * cmb(N-K+1, i)
    print(ans%(10**9+7))
n, m = map(int, input().split())

graph = [[] for _ in range(n)]

lines = input().splitlines()

for line in lines:
    l, r, d = map(int, line.split())
    graph[l - 1].append(( d,r - 1))
    graph[r - 1].append((-d,l - 1))

INF = float("inf")
dist = [-INF]*n

# 未探索ノードの距離を0とする
for n in range(n):
    if dist[n] != -INF:
        continue
    else:
        stack = [n]
        dist[n] = 0
        
    # stackが空になるまで探索を繰り返す
    while len(stack):
        cur = stack.pop()
        
        # ノードcurと隣り合う未探索ノードをstackに追加
        for cost, nex_node in graph[cur]:
            if dist[nex_node] != -INF:
                continue
            else:
                dist[nex_node] = dist[cur] + cost
                stack.append(nex_node)

flag = True
for i in range(n):
    if not flag:
        break
    for d,node in graph[i]:
        if dist[node]-dist[i] != d:
            print("No")
            flag = False

if flag:
    print("Yes")

### FIXED CODE ###

class UnionFind:
    __slots__ = ["nodes", "weight"]
    
    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n
        self.weight = [0]*n
        
    def get_root(self, x:int) -> int:
        if x<0:
            raise ValueError("Negative Index")
        
        if self.nodes[x]<0:
            return x
        else:
            parent, self.nodes[x] = self.nodes[x], self.get_root(self.nodes[x])
            self.weight[x] += self.weight[parent]
            return self.nodes[x]

    def unite(self, x:int, y:int) -> None:
        if x<0 or y<0:
            raise ValueError("Negative Index")
            
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] < self.nodes[root_y]:
                bigroot, smallroot = root_x, root_y
            else:
                bigroot, smallroot = root_y, root_x
                
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot

    def relate(self, smaller:int, bigger:int, diff_weight:int) -> None:
        if smaller<0 or bigger<0:
            raise ValueError("Negative Index")
            
        s_root, b_root = self.get_root(smaller), self.get_root(bigger)
        if s_root == b_root:
            if self.weight[smaller] + diff_weight == self.weight[bigger]:
                return
            raise ValueError
            
        else:
            self.weight[b_root] = diff_weight - self.weight[bigger]
            self.nodes[s_root] += self.nodes[b_root]
            self.nodes[b_root] = smaller
            
   
         
N,M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))
 
uf = UnionFind(N)
relate = uf.relate    

try:
    for l,r,d in LRD:
        relate(l-1,r-1,d)
    print("Yes")
except Exception as e:
    print("No")
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)
    return divisors

import random
def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

import math
a, b = map(int,input().split())
ans = 1
gcd_div = make_divisors(math.gcd(a, b))
for i in gcd_div:
    if is_prime(i) == True:
        ans += 1
print(ans)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import fractions
a, b = map(int,input().split())

if fractions.gcd(a, b) == 1:
    print(1)
else:
    print(len(factorization(fractions.gcd(a, b))) + 1)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = [a[i] - b[i] for i in range(12)]
c.sort()

if sum(c) < 0:
    print(-1)

neg = [v for v in c if c < 0]
pos = [v for v in c if c > 0]
total = abs(sum(neg))

k = 0
for i, v in enumerate(reversed(pos)):
    k += v
    if k >= total:
        break

print(len(neg) + i + 1)

### FIXED CODE ###

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

c = [a[i] - b[i] for i in range(n)]
c.sort()

neg = [v for v in c if v < 0]
total = sum(neg)
num = len(neg)

if sum(c) < 0:
    print(-1)
elif num == 0:
    print(0)
else:
    for v in reversed(c[num:]):
        total += v
        num += 1
        if total >= 0:
            break
    print(num)
def c_christmas_eve(N, K, H):
    H.sort()
    ans = float('inf')
    for j in range(N - K + 1):
        h_max = H[j + 2]
        h_min = H[j]
        ans = min(ans, h_max - h_min)
    return ans

N, K = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(c_christmas_eve(N, K, H))

### FIXED CODE ###

def c_christmas_eve(N, K, H):
    H.sort()
    ans = float('inf')
    for j in range(N - K + 1):
        h_max = H[j + K - 1]
        h_min = H[j]
        ans = min(ans, h_max - h_min)
    return ans

N, K = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(c_christmas_eve(N, K, H))
N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
A_point=[K]*N
#全体の試合数Q-
for a in A:
  A_point[a]-=1
for aa in A_point:
  if aa<=0:
    print("NO")
  else:
    print("Yes")

### FIXED CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
A_point=[0]*N

for a in A:
  A_point[a-1]+=1

for aa in A_point:
  if K-(Q-aa)<=0:
    print("No")
  else:
    print("Yes")
A, B, C, D = map(int, input().split())
print('Left' if A + B > C + D else 'Balanced' if A + B = C + D else 'Right')

### FIXED CODE ###

A, B, C, D = map(int, input().split())
print('Left' if (A + B) > C + D else 'Balanced' if (A + B) == (C + D) else 'Right')
from itertools import accumulate
import bisect

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

a_acc = [0] + list(accumulate(a))  # aを0冊読む=1冊も読まない場合があるので、[0]を先頭に追加します
b_acc = list(accumulate(b))  # bisect_rightでは、x以下の要素がいくつあるか？を求めるので、こちらに0は入れません

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        # aをこれ以上読めません
        break

    bn = bisect.bisect_right(b_acc, rem)
    ans = max(ans, an + bn)

print(ans)

### FIXED CODE ###

N = int(input())
print(N+N*N+N*N*N)
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1),
                           dp[x][y-1] + ai * (n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))


### FIXED CODE ###

def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, k):
    m = 10**9+7
    res = 0
    for i in range(k, n+2):
        res += n*i - i*i + i + 1
    return res % m


if __name__ == "__main__":
    n, k = inums()
    print(solve(n, k))
S = int(input())
h = int(S)//3600
m = (int(S)%3600)//60
s = (int(S)%3600)%60 
print(h:m:s)

### FIXED CODE ###

S = int(input())
h = int(S//3600)
m = int(S%3600)//60
s = int(S%3600)%60 
print("{}:{}:{}".format(h,m,s))
x_list = [input()]
for i in range(5):
  if x_list[i] == 0:
    print(i)

### FIXED CODE ###

x_list = list(map(int, input().split()))
for i in range(5):
    if x_list[i] == 0:
        print(i + 1)
S = input()

if S == "SAT":
    print(1)
elif S=='FRI':
    print(2)
elif S=='THU':
    print(3)
elif S=='WED':
    print(4)
elif S=='TUE':
    print(5)
elif S=='MON':
    print(6)
else S=='SUN':
    print(7)
 

### FIXED CODE ###

S = input()

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else:
    print(1)
a , b = map(int,input().split())
list = []
papa = ""
for i in range(b):
  list.append(input()) 
c = sorted(list)
for x in c:
  papa += x
print(papa)

### FIXED CODE ###

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

if a.count(5) == 2:
  if a.count(7) == 1:
    print("YES")
  else:
    print("NO")
else:
  print("NO")
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7

res = [[-1 for _ in range(M)] for _ in range(N)]
dpl = [[-1 for _ in range(M)] for _ in range(N)]
def dp(i, j):
  if i < 0:
    return 0
  if j < 0:
    return 0
  if dpl[i][j] != -1:
    return dpl[i][j]
  if i == 1:
    temp = 0
    for k in range(j):
      temp += S[i] == T[k]
    return temp
  elif j == 1:
    temp = 0
    for k in range(j):
      temp += S[k] == T[j]
    return temp
  temp = 0
  for k in range(i):
    for l in range(j):
      temp += dpl[k][l]
      
  return temp

def search(i, j):
  if i < 0:
    return 0
  if j < 0:
    return 0
  if res[i][j] != -1:
    return res[i][j]
  temp = 0
  if S[i] == T[j]:
    temp = 1
    temp += dp[i][j]
  else:
    temp = 0
  return search(i - 1, j) + search(i, j - 1) - search(i - 1, j - 1) + temp

print(search(N - 1, M - 1) % mod)


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
mod = 10 ** 9 + 7
dp = np.ones(M + 1, dtype = np.int64)
 
for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % mod

print(dp[M])
input_1 = input("")
mylist = list(map(int, input_1.split(" ")))
H = mylist[0]
A = mylist[1]
if H % A =! 0:
  answer = H//A + 1
else:
  anser = H//A
print(answer)

### FIXED CODE ###

input_1 = input()
mylist = list(map(int, input_1.split(" ")))
H = mylist[0]
A = mylist[1]
if H % A != 0:
  answer = H//A + 1
else:
  answer = H//A
print(answer)
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()

ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

### FIXED CODE ###

def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
from collections import deque
N, M, K = map(int, input().split())
A = deque(list(map(int, input().split())))
B = deque(list(map(int, input().split())))
dp = [0] * (len(A)+len(B)+1)
i = j = 0
for idx in range(len(dp)):
    if i >= len(A) and j >= len(B):
        print(i+j)
        exit()
    if i >= len(A):
        dp[idx+1] = dp[idx] + B[j]
        j += 1
    elif j >= len(B):
        dp[idx+1] = dp[idx] + A[j]
    elif dp[idx] + A[i] < dp[idx] + B[j]:
        dp[idx+1] = dp[idx] + A[i]
        i += 1
    else:
        dp[idx+1] = dp[idx] + B[j]
        j += 1
    if dp[idx+1] > K:
        break
print(i+j-1)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a_s = [0] * (len(A)+1)
b_s = [0] * (len(B)+1)
for i in range(len(A)):
    a_s[i+1] = a_s[i] + A[i]
for i in range(len(B)):
    b_s[i + 1] = b_s[i] + B[i]

ans = 0
j = M
for i in range(len(a_s)):
    if a_s[i] > K:
        break
    while b_s[j] + a_s[i] > K:
        j -= 1
    ans = max(ans, i+j)
print(ans)
import sys

chash = {}
for i in range( ord( 'a' ), ord( 'z' ) ):
	chash[ chr( i ) ] = 0

line = sys.stdin.readlines().rstrip()
for i in range( len( line ) ):
	if line[i].isalpha():
		chash[ line[i].lower() ] += 1

for i in range( ord( 'a' ), ord( 'z' ) ):
	print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )

### FIXED CODE ###

import sys
 
chash = {}
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    chash[ chr( i ) ] = 0
 
while True:
    line = sys.stdin.readline().rstrip()
    if not line:
        break
    for i in range( len( line ) ):
        if line[i].isalpha():
            chash[ line[i].lower() ] += 1
 
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )
import sys
sys.setrecursionlimit(10**5)

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    if belongs[root] == -1:
        belongs[root] = group_ID
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    f_search(i, group_ID)
    group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
        group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])
n = int(input())
an = [int(input()) for i in range(n)]
c, s = 1, a[0]
while s != 2 and c < n:
    c, s = c + 1, a[s - 1]
print(c if c < n else -1)


### FIXED CODE ###

n = int(input())
an = [int(input()) for i in range(n)]
c, s = 1, an[0]
while s != 2 and c < n:
    c, s = c + 1, an[s - 1]
print(c if c < n else -1)