Harryxun/stf_run huggingface dataset:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class BIT:
	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

	def sum(self, t):
		s = 0
		while t > 0:
			s += self.tree[t]
			t -= t & -t
		return s

	def add(self, t, x):
		while t <= self.size:
			self.tree[t] += x
			t += t & -t

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N
	# for i in range(N):
	# 	lastappeared[c[i] - 1] = i
	ans = [0] * N
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort()
	bit = BIT(N)
	val = 0
	right = 1
	for r, l, i in LR:
		while right <= r:
			if lastappeared[c[right] - 1] == None:
				bit.add(right, 1)
			else:
				bit.add(lastappeared[c[right] - 1], -1)
				bit.add(right, 1)
			lastappeared[c[right] - 1] = right

			right += 1

		if l == 1:
			anspre = bit.sum(r)
		else:
			anspre = bit.sum(r) - bit.sum(l - 1)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

	ans = [0] * Q
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



if __name__ == '__main__':
	main()
n=int(input())
l=[]
for _ in range(n):
    l.append(int(iｂnput()))
print(sum(l)-int(max(l)/2))


### FIXED CODE ###

n=int(input())
l=[]
for _ in range(n):
    l.append(int(input()))
print(sum(l)-int(max(l)/2))
A, B = map(int, input().split())
X = [i for i in range(N)]
Y = []
def chk(a, b):
    print("?", a, b)
    return 1 if input() == "Y" else 0
while X:
    if not Y:
        Y.append(X.pop())
    else:
        if chk(Y[-1], X[-1]):
            Y.append(X.pop())
        else:
            Y.pop()
print("!", "".join([str(chk(Y[-1], i)) for i in range(N)]))

### FIXED CODE ###

A, B = map(int, input().split())
N = A + B
X = [i for i in range(N)]
Y = []
def chk(a, b):
    print("?", a, b)
    return 1 if input() == "Y" else 0
if A <= B:
    print("Impossible")
else:
    while X:
        if not Y:
            Y.append(X.pop())
        else:
            if chk(Y[-1], X[-1]):
                Y.append(X.pop())
            else:
                X.pop()
                Y.pop()
    print("!", "".join([str(chk(Y[-1], i)) for i in range(N)]))
N = int(input())
As = list(map(int, input().split()))
judge = As[0]
preans = []
hand = 1000
kabu = 0
while As:
    a = As.pop(0)
    if a <= judge:
        preans.append(a)
    else:
        buy = min(preans)
        while hand >= buy:
            kabu += 1
            hand-= buy
        hand += kabu * a
        judge = a
        kabu = 0
        preans = []
print(hand)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
yen = 1000
kabu = 0
for n in range(N-1):
    if As[n] < As[n+1]:
        kabu += yen // As[n]
        yen -= kabu * As[n]
        yen += kabu * As[n+1]
        kabu = 0
print(yen)
import numpy as np

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

l = n - k + 1
lis = [0]*l
#0, 1, 2
for i in range(l):
  z = np.prod(a[i:i+k])
  lis[i] = z
for i in range(n - k):
  if lis[i] < lis[i + 1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

a = int(input())

if 400 <= a < 600:
  print(8)
elif 600 <= a < 800:
  print(7)
elif 800 <= a < 1000:
  print(6)
elif 1000 <= a < 1200:
  print(5)
elif 1200 <= a < 1400:
  print(4)
elif 1400<= a < 1600:
  print(3)
elif 1600 <= a < 1800:
  print(2)
elif 1800 <= a < 2000:
  print(1)
from heapq import *
import numpy as np

def dk(start,node,edge):
  d = [0] * node
  d[start] = 0
  q = [(0, start)]
  
  while(len(q) != 0):
    ci, i = heappop(q)
    for j in edge[i]:
      nc = ci + cost[i][j]
      d[j] = int(nc%2)
      heappush(q,(nc, j))
  return d

#入力
N = int(input())
#エッジ
E = [[] for _ in [0]*(N)]
cost = np.zeros((N, N))

for i in range(N-1):
  a,b,w = (int(x) for x in input().split())
  E[a-1].append(b-1)
  cost[a-1][b-1] = w
  cost[b-1][a-1] = w


d = dk(0, N, E)

#出力
print(*d, sep = "\n")
    

### FIXED CODE ###

import numpy as np
import sys
INF = float('inf')
sys.setrecursionlimit(10**5)
max = 10**5+5

def dk(start,node,edge):
  ans = [INF] * node
  ans[0] = 0
  q = [start]
  
  while(len(q) != 0):
    i = q.pop()
    for j, cost in edge[i]:
      if(ans[j] != INF):
        continue
      ans[j] = (ans[i] + cost)%2
      q.append(j)
  return ans

#入力
N = int(input())
#エッジ
E = [[] for _ in [0]*(max)]

for i in range(N-1):
  a,b,w = (int(x) for x in input().split())
  E[a-1].append((b-1, w))
  E[b-1].append((a-1, w))


ans = dk(0, N, E)

#出力
print(*ans, sep = "\n")
import math


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 100000
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
max_p_nums = 0
for a in A:
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = int(a / p)
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
if max_p_nums == 1:
    print('pairwise coprime')
elif max_p_nums < N:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

import math


def get_pseudo_input():
    N = 3
    A = [6, 10, 16]
    return N, A


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
p_nums[1] = N
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        # print(f"  a={a}")
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums <= 1:
    # GCD of A is 1
    print('pairwise coprime')
elif max_p_nums == N:
    # GCD of A is not 1
    print('not coprime')
else:
    print('setwise coprime')
a, p = input().split()
print((a*3 + p) // 2)

### FIXED CODE ###

a, p = map(int, input().split())
ans = (a*3+p) // 2
print(ans)
N A B = list(map(int, input().split()))

total_cost = N * A

if total_cost > B:
  total_cost = B
  
print(total_cost)


### FIXED CODE ###

N, A, B = list(map(int, input().split()))
 
total_cost = N * A
 
if total_cost > B:
  total_cost = B
  
print(total_cost)
from fractions import gcd

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

s = input()
t = input()

# accept
# a c p
# a  e

# 最小公倍数。被ったらNG
l = n * m // gcd(n, m)
x = [None] * l
for i, c in enumerate(s):
    x[i*l//n] = c

for i, c in enumerate(t):
    a = x[i*l//m]
    if a is None:
        continue
    elif a != c:
        print(-1)
        exit()

print(l)


### FIXED CODE ###

from fractions import gcd

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

s = input()
t = input()

# accept
# a c p
# a  e

g = gcd(n, m)
a = n // g
b = m // g
for i in range(g):
    if s[i*a] != t[i*b]:
        print(-1)
        exit()

print(n*m//g)
N , K = map(int,input().split())
S = input()

if S[K] == 'A' :
    S[K] = 'a'
if S[K] == 'B' :
    S[K] = 'b'
if S[K] == 'C' :
    S[K] = 'c'

print(S)

### FIXED CODE ###

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

ans = S[:K-1] + S[K-1].replace('A','a').replace('B','b').replace('C','c') + S[K:]

print(ans)
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



g = 0
# @lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)

root = 1
for j in g:
    if len(g[j]) == 1:
        root = j
        break

ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
from itertools import permutations
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    *D, = map(int, input().split())

    def solve(S, D):
        Q = [0]*(n+1)
        for P in permutations(S):
            for i, e in enumerate(P):
                Q[i+1] = e + Q[i]
            yield sum(min(abs(d - q) for q in Q) for d in D)
    print(min(solve(S, D)))

### FIXED CODE ###

from collections import deque
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    D = sorted(map(int, input().split()))

    SA = sum(S)
    rest = sum(d-SA for d in D if SA <= d)

    memo = {2**n-1: rest}
    def dfs(state, su, idx):
        if state in memo:
            return memo[state]
        res = 10**18
        for i in range(n):
            if (state >> i) & 1 == 0:
                s = 0; j = idx
                nxt = su + S[i]
                while j < m and D[j] <= nxt:
                    s += min(nxt - D[j], D[j] - su); j += 1
                res = min(res, s + dfs(state | (1 << i), su + S[i], j))
        memo[state] = res
        return res
    print(dfs(0, 0, 0))
import sys
sys.setrecursionlimit(10**9)

k = int(input())
l = len(str(k))+4
A = [str(i+1) for i in range(9)]
B = ["0"] + A
ans = []
#print(l)

def dfs(num,l):
    if len(num) >= l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i)) < 2:
                dfs(num + i,l)
if k <= 9:
    print(k)
else:
    for i in A:
        dfs(i,l)
    ans = sorted(ans)
    #print(ans)
    print(ans[k-1])

### FIXED CODE ###

from collections import deque

K=int(input())

def bfs(k):
    queue = deque()
    for i in range(1, 10):#1~9までをqueueに追加しておく
        queue.append(i)
    cnt = 1
    
    while queue:
        x = queue.popleft()#左から取り出すと、自動的に小さい順から取り出せる
        if cnt == k:
            return x
        cnt += 1 #これまでのルンルン数の数
        last = x%10 #末尾の数字
        if last > 0:
            queue.append(x*10+last-1)#x-1⇒x⇒x+1の順にを末尾に追加すると順番になる。0と9に注意
        queue.append(x*10+last)
        if last < 9:
            queue.append(x*10+last+1)
            
print(bfs(K))
A = input()
B = input()

print(A * B)

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
k = int(input())
a,b = map(int, input().split)
largest = (b//k)*k
print("OK" if largest >= a else "NG")

### FIXED CODE ###

k = int(input())
a,b = map(int, input().split())
largest = (b//k)*k
print("OK" if largest >= a else "NG")
def main(N, M, C):
    lst = []
    for c in C:
        for l in lst:
            if c[0] in l:
                l.add(c[1])
                break
            elif c[1] in l:
                l.add(c[0])
                break
        else:
            lst.append(set(c))
    # print(lst)
    print(max({len(l) for l in lst}))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(int, input().split())))
    main(N, M, C)

### FIXED CODE ###

from collections import Counter

# 再帰回数のエラー？と思われるので再帰上限を変更 10**3→10**9
import sys
sys.setrecursionlimit(10 ** 9)

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            return lst[x]
            # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数)

    def unite(x, y):    # 集合の連結を行う関数
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y

    {unite(*c) for c in C}  # 集合の連結を行う．

    print(max(Counter(map(get_root, lst)).values()))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)
input_a = input()
input_b = input()
a = int(input_a)
b = int(input_b)
c = a * b

if c % 2 == 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

def main():
    a, b = [int(_) for _ in input().split()]
    print("Even") if a * b % 2 == 0 else print("Odd")

main()
prices = [100, 101, 102, 103, 104, 105]
dp = [100, 101, 102, 103, 104, 105]

x = int(input())
while x > dp[-1]:
  maxv = dp[-1]
  next_max = 100000
  for v in dp:
    for p in prices:
      if v + p < next_max and v + p > maxv:
        next_max = v + p
 
if x = dp[-1]:
  print(1)
else:
  print(0)
  



### FIXED CODE ###

#config:utf-8
x = input()

if int(x) < 100:
    print(0)
elif 5 * int(x[0:-2]) >= int(x[-2:]):
    print(1)
else:
    print(0)
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# A が2で何回割れるか
N, M = lr()
A = lr()
A = [x // 2 for x in A]
cnt = 0
while all(x%2 == 0 for x in A):
    cnt += 1
    A = [x // 2 for x in A]

if any(x%2 == 0 for x in A):
    print(0); exit()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = M // lcm - M // (2 * lcm)
print(answer)
# 21

### FIXED CODE ###

import sys
import numpy as np
from fractions import gcd
from functools import reduce

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
B = A // 2

def merge(a, b):
    g = gcd(a, b)
    a //= g; b //= g
    if a%2 == 0 or b%2 == 0:
        return 0
    n = g * a * b
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, B)
if x == 0:
    answer = 0
else:
    answer = M // x - M // (2*x)

print(answer)
S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    if len(aset)-1 > K-c:
        break
    c += len(aset)-1


alist = sorted(list(aset))
for al in alist:
    if al == '':
        continue
    c += 1
    if c == K:
        ans = al
        break

print(ans)

### FIXED CODE ###

def main():
    S = input()
    N = len(S)
    K = int(input())

    S1 = {}
    for i, s in enumerate(S):
        if not s in S1.keys():
            S1[s] = [i]
        else:
            S1[s].append(i)
    alp = sorted(list(S1.keys()))

    c = 0
    for a in alp:
        aset = set()
        inds = S1[a]
        for d in inds:
            up = min(N-d+1, K+1)
            for i in range(up):
                aset.add(S[d:d+i])
        L = len(aset)-1
        if L >= K-c:
            break
        c += L

    for _ in range(10):
        M = '何だこれはもうやめてくれよ'
        for a in aset:
            if a < M:
                M = a
        aset.discard(M)
        if M == '':
            continue
        c += 1
        if c >= K:
            ans = M
            break

    print(ans)



if __name__=='__main__':
    main()
N, M = map(int,input().split())
A = []
dp = [0] * N
for i in range(M):
  A.append(int(input()))

  
for i in range(2):
  if not((i+1) in A):
    dp[i] = 1 + dp[i-1] + dp[i-2]
    
for i in range(2,N):
  if not((i+1) in A):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%1000000007)

### FIXED CODE ###

from collections import deque

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

A = deque()
dp = [0] * N
for i in range(M):
  A.append(int(input()))
A.append(N+1)

if N == 1:
  print(1)

elif N == 2:
  if 1 in A:
    print(1)
  else:
    print(2)
    
else:
  a = A.popleft()
  if a != 1:
    dp[0] = 1
  else:
    a = A.popleft()
    
  if a != 2:
    dp[1] = dp[0] + 1
  else:
    a = A.popleft()
    
  for i in range(2,N):
    if a != i+1:
      dp[i] = dp[i-1] + dp[i-2]
    else:
      a = A.popleft()
  print(dp[-1]%1000000007)
import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

print(res)

### FIXED CODE ###

import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

print(res)
N=int(input())
S=input()
key=0
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      s=S[i]+S[j]+S[k]
      if s in key:continue
      else:key+=1
print(key)

### FIXED CODE ###

N=int(input())
S=input()
i_lis=[]
key=0
for i in range(N-2):
  if S[i] in i_lis:continue
  else:i_lis.append(S[i])
  j_lis=[]
  for j in range(i+1,N-1):
    if S[j] in j_lis:continue
    else:j_lis.append(S[j])
    k_lis=[]
    for k in range(j+1,N):
      if S[k] in k_lis:continue
      else:k_lis.append(S[k]);key+=1
print(key)
N,K = map(int,input().split())
A = list(map(int,input().split()))
A_dict = {i:a for i,a in enumerate(A,1)}

History = [1]
History_set = {1}
now = 1
for _ in range(N):
    now = A_dict[now]
    if now not in History_set:
        History.append(now)
        History_set.add(now)
    else:
        break
#print(History,now)
if K < N:
    print(History[K])
else:
    e = History.index(now)
    #print(e)
    #print(History[e:])
    loop_num = len(History[e:])
    #print(loop_num)
    num = (K-e)%loop_num
    #print(num)
    print(History[e:][num])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A_dict = {i:a for i,a in enumerate(A,1)}

History = [1]
History_set = {1}
now = 1
for i in range(N):
    now = A_dict[now]
    if now not in History_set:
        History.append(now)
        History_set.add(now)
    else:
        break
#print(History,now)
if K < i:
    print(History[K])
else:
    e = History.index(now)
    #print(e)
    #print(History[e:])
    loop_num = len(History[e:])
    #print(loop_num)
    num = (K-e)%loop_num
    #print(num)
    print(History[e:][num])