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

from operator import itemgetter
import array
import collections

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    weight = 0

    for edge in edges:
        if not uf.same(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            weight+=edge.weight
    return weight
    
Edge = collections.namedtuple('Edge',('start','end','weight'))
N = int(input())
xli = []
yli = []


for i in range(N):
    x,y = [int(x) for x in input().split()]
    xli.append([x-1,i])
    yli.append([y-1,i])
xli.sort()
yli.sort()

edges = []
for i in range(N-1):
    edges.append(Edge(xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
    edges.append(Edge(yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))
ans = compute_mst_kruskal(N,edges)
print(ans)


### FIXED CODE ###

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] #1_indexed
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in dp[i-1].items():
        dp[i][dw] = max(dp[i][dw],dv)
        if w+dw<=W:
            dp[i][w+dw] = max(dp[i][w+dw],v+dv)
print(max(dp[-1].values()))


### FIXED CODE ###

import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
flag = bfs(0)
judge = flag[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    ans = bfs(i)
    if ans[1][0] == 1:
        print("1")
    else:
        print(ans[0][0]+1)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if v == 0 and start != 0:
                d[v] = d[c]+1
                pre[v] = c
                return [pre,d]
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans = bfs(0)
judge = ans[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    print(ans[0][i]+1)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
RowIdx = set()
ColIdx = set()
Grid = defaultdict(list)
RowGrid = defaultdict(list)
ColGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	RowGrid[r].append(c)
	ColGrid[c].append(r)
	Grid[(r, c)] = a
	RowIdx.add(r)
	ColIdx.add(c)	

fresh = 1
while(fresh == 1):
	fresh = 0
	for row in RowIdx:
		if (len(RowGrid[row]) == 1):
			continue
		TempRow = RowGrid[row]
		for pointer in TempRow:
			TempCol = TempRow.copy()
			TempCol.remove(pointer)
			for pair in TempCol:
				dif = Grid[(row, pointer)] - Grid[(row, pair)]
				ObjCol = ColGrid[pointer].copy()
				ObjCol.remove(row)
				for obj in ObjCol:
					val = Grid[(obj, pointer)]- dif 
					if (val < 0):
						print("No")
						exit()
					if ((obj, pair) in Grid):
						if (val != Grid[(obj, pair)]):
							print("No");
							exit()
						else:
							continue
					else:
						Grid[(obj, pair)] = val
						RowGrid[obj].append(pair)
						ColGrid[pair].append(obj)
						fresh = 1
print("Yes")


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

import sys
def main():
  n,q,*c=map(int,sys.stdin.buffer.read().split())
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:c[x+x-~n]):
    l,r=c[i+i+n],c[i+i-~n]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s+=t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()
### BUGGY CODE ###

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i-k)
    while(j < i):
        dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j])
        j = j + 1

# Output
print(dp[n-1])

### FIXED CODE ###

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i-k)
    while(j < i):
        dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j])
        j = j + 1

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

N = int(input())
A= [input() for i in range(N)]

for i in range(N):
    hoge = A.pop(i)
    print(max(A))
    A.insert(i,hoge)
    

### FIXED CODE ###

N = int(input())
A=[int(input()) for i in range(N)]

normal = max(A)
hoge=sorted(A)
exception = hoge[-2]

for i in range(N):
    if A[i] == normal:
        print(exception)
    else:
        print(normal)
### BUGGY CODE ###

N, K = map(int, input().split())
*P, = map(int, input().split())
expec = [(P[i] * (P[i] + 1) / 2) / P[i] for i in range(N)]
ans = 0
for i in range(N-K+1):
    ans = max(ans, sum(expec[i:i+K]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
*P, = map(int, input().split())
cum = [0] * (N + 1)
for i in range(N):
    cum[i+1] = cum[i] + (P[i] * (P[i] + 1) / 2) / P[i]
ans = 0
for i in range(N-K+1):
    ans = max(ans, cum[i+K] - cum[i])
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math

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

N = int(input())
s = [input() for i in range(N)]

for i in range(N):
    s[i] = ''.join(sorted(s[i]))

unique_s = set(s)

output = 0
for k in unique_s:
     if s.count(k) != 1:
        output += int(comb(s.count(k), 2))

print(output)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
s = [input() for i in range(N)]

output = 0
dic = dict()
for i in range(N):
    tmp = ''.join(sorted(s[i]))
    if tmp not in dic:
        dic[tmp] = 1
    else:
        output += dic[tmp]
        dic[tmp] += 1

print(output)
### BUGGY CODE ###

import numpy as np
from numba import jit
verbose = False

N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())), dtype=np.int64)

ul = np.ceil(np.sum(A)/(K))
ll= np.floor(np.max(A)/(K+1))

EPS = 1 / 10**6

@jit(nopython=True)
def cut(A, c, N):
    return (np.sum(np.ceil(A/c))-N)

c = np.ceil((ul+ll)/2)
mx = np.max(A)
while True:
    if ul-ll == 1:
        break
    nk = cut(A, c, N)
    if verbose:
        print('c:', c, 'nk:', nk, 'ul - ll:', ul, '/', ll)
    prev = c
    if nk  >K: # more cuts than target; larger logs can be made
        ll = c
        c = np.ceil((ul + c)/2)
    else: #i.e. nk < K, less cuts than target
        ul = c
        c = np.floor((c + ll)/2)
        
if cut(A, ll+EPS, N) >= K:
    print(np.min((np.max(A), int(ul))))
else:
    print(int(ll))
    


### FIXED CODE ###

import numpy as np
from numba import jit
import random
verbose = False
rand = False

if rand:
    N, K = random.choice(range(10)), random.choice(range(10))
    A = np.array(random.choices(range(10**9), k=N))
else:
    N, K = list(map(int, input().split()))
    A = np.array(list(map(int, input().split())), dtype=np.int64)

ul = np.ceil(np.sum(A)/(K+1))
ll= np.floor(np.max(A)/(K+1))

EPS = 1 / 10**6

@jit(nopython=True)
def cut(A, c, N):
    return (np.sum(np.ceil(A/c))-N)

c = np.ceil((ul+ll)/2)
mx = np.max(A)
while True:
    if ul-ll <= 1:
        break
    nk = cut(A, c, N)
    if verbose:
        print('c:', c, 'nk:', nk, 'ul - ll:', ul, '/', ll)
    prev = c
    if nk  >K: # more cuts than target; larger logs can be made
        ll = c
        c = np.floor((ul + c)/2)
    else: #i.e. nk < K, less cuts than target
        ul = c
        c = np.ceil((c + ll)/2)
        
if cut(A, ll+EPS, N) >= K:
    print(np.min((np.max(A), int(ul))))
else:
    print(int(ll))
### BUGGY CODE ###

import sys
import numpy as np
sys.argv.append('ONLINE_JUDGE')
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    ans = 0

    answers = np.empty(Q, np.int32)
    nl, nr = 0, 0
    for i in ind:
        pass
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

@njit((i8[:, :], ), cache=True)
def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

@njit((i8[:], i8[:, :]), cache=True)
def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0
    

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q,2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))
### BUGGY CODE ###

kk, s = map(int, input().split(" "))
count = 0
for i in range(0, kk + 1):
    for j in range(0, kk + 1):
        for k in range(0, kk + 1):
            if i + j + k == s:
                count += 1

print(count)


### FIXED CODE ###

k, s = map(int, input().split(" "))
count = 0
for i in range(0, k + 1):
    for j in range(0, k + 1):
            if 0 <= s - i - j <=k:
                count += 1

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

N=int(input())
P=list(map(int,input().split()))
x=0
for i in range(N):
    B=0
    a=P[i]
    for j in range(i+1):
        b=P[j]
        if a>b:
            break
        else:
            B+=1
    if i+1==B:
        x+=1
print(x)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
x=1
Min=P[0]
for i in range(1,N):
    if Min>P[i]:
        Min=P[i]
        x+=1
print(x)
### BUGGY CODE ###

import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    x,y = IL()
    bit = 2**x
    for i in range(bit):
        tmp = 0
        for j in range(x):
            if (i>>j)&1:
                tmp += 2
            else:
                tmp += 4
        if tmp == y:
            print('Yes')
            exit()
    print('No')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    x,y = IL()
    if 4*x<y or y%2!=0:
        print('No')
        exit()
    for i in range(x+1):
        if 4*i+2*(x-i)==y:
            print('Yes')
            exit()
    print('No')
    return

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

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n >= 100:
        if lst[i] >= lst[n-1] ** 0.5:
          continue
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)


### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = {i:0 for i in range(1,N+1)} #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = {i:-1 for i in range(1,N+1)} #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*[a for a in ans.values()])

### FIXED CODE ###

import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
H,W = map(int,input().split())
Gd,L,R,U,D=[None]*H,[None]*H,[None]*H,[None]*H,[None]*H
for _ in range(H):
  Gd[_] = list(input())
  L[_], R[_], D[_], U[_] = [0]*W, [0]*W, [0]*W, [0]*W
L=np.array(L)
R=np.array(R)
U=np.array(U)
D=np.array(D)
HL=range(H)
WL=range(W)
def ma():
  for h in HL:
    for w in WL:
      if Gd[h][w]=='#':
        R[h][w]=0
      else:
        if w==0:
          R[h][w]=1
        else:
          R[h][w]=R[h][w-1]+1
      wr=W-w-1
      if Gd[h][wr]=='#':
        L[h][wr]=0
      else:
        if w==0:
          L[h][wr]=1
        else:
          L[h][wr]=L[h][wr+1]+1

  for w in WL:
    for h in HL:
      if Gd[h][w]=='#':
        D[h][w]=0
      else:
        if h==0:
          D[h][w]=1
        else:
          D[h][w]=D[h-1][w]+1
      hr=H-h-1
      if Gd[hr][w]=='#':
        U[hr][w]=0
      else:
        if h==0:
          U[hr][w]=1
        else:
          U[hr][w]=U[hr+1][w]+1
  return np.max(D+U+L+R-3)
print(ma())

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))
### BUGGY CODE ###

def main():
  N, K = map(int, input().split())
  A_list = input().split()

  root = [1]

  break_flag = 0
  for n in range(K):
    new = A_list[ int(root[n])-1 ]
    if new not in root:
      root.append(new)
    else:
      ind = root.index(new)
      break
  else:
    print(new)
    break_flag = 1
    
  if break_flag == 0:  
	  pre = len(root[:ind])
	  roop = len(root)-pre

	  print(root[ind:][(K-pre)%roop])
   
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  N, K = map(int, input().split())
  A_list = input().split()

  root = [1]

  record = [-1]*N
  break_flag = 0
  for n in range(K):
    new = int(A_list[ int(root[n])-1 ])
    if record[new-1] <0:
      record[new-1]=1
      root.append(new)
    else:
      ind = root.index(new)
      break
  else:
    print(new)
    break_flag = 1
    
  if break_flag == 0:  
	  pre = len(root[:ind])
	  roop = len(root)-pre

	  print(root[ind:][(K-pre)%roop])
   
if __name__ == '__main__':
  main()