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

import sys
sys.setrecursionlimit(1000000) 

N,M = map(int,input().split())
a = [list(map(int, input().split())) for _ in range(N-1)]
b = [list(map(int, input().split())) for _ in range(M)]

ans=[0]*N
results = {}
for word in a:
    results.setdefault(word[0], []).append(word[1])

for i in b:
    ans[i[0]-1] += i[1]

def sumup(ne):
    global ans
    if ne in results:    
        for k in results[ne]:
            ans[k-1] += ans[ne-1]
            sumup(k)

sumup(1)
for i in ans:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.append(x)
xs.sort()
tmp = list(set(tmp))
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
st = SegTree([len(tmp)]*len(tmp), len(tmp), len(tmp), min)
for t,r,x in xs:
    while True:
        if q < t:
            c = st.query(0,len(tmp))
            if c != len(tmp):
                print(tmp[c])
            else:
                print(-1)
            Q-=1
            if Q == 0:
                break
            q = int(input())
        else:
            break
#    print(t,r,x)
    if Q==0:
        break
    if r:
        st.update(x2i[x], x2i[x])
    else:
        st.update(x2i[x], len(tmp))
print("-1\n"*Q)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
c=0
for i in range(len(a)):
  for j in range(len(a)):
    d=0
    if i==n-1-j:
      continue
    elif a[i]%a[n-1-j]==0:
      d+=1
      break
  if d==0:
     c+=1
print(c)    
      

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
for i in A:
  dp[i]+=1
for i in range(1,10**6+1):
  if dp[i]>0:
    for j in range(2*i,10**6+1,i):
      dp[j]=0
print(dp.count(1))
### BUGGY CODE ###

d = int(input())
C = list(map(int, input().split()))
S = list(list(map(int, input().split())) for _ in range(d))

def satisfication(task_list):
    res = 0
    kaisai = [0] * 26
    date = 0
    for t in task_list:
        date += 1
        kaisai[t-1] = date
        res += S[date - 1][t-1]
    
        for i in range(26):
            res -= C[i] * (date - kaisai[i])
        
    return res

task = []

for i in range(d):
    manzoku = 0
    task_tmp = 0
    for j in range(26):
        task.append(j)
        tmp = satisfication(task)
        if tmp > manzoku:
            manzoku = tmp
            task_tmp = j
        task.pop()
    task.append(task_tmp)

print(*task, sep='\n')


### FIXED CODE ###

d = int(input())
c = list(map(int, input().split()))
s = list(map(int, input().split()) for _ in range(d))

import random
for i in range(d):
    print(int(random.uniform(1, 26)))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(K, N):
    std = 1
    com = 1
    for j in range(K):
        std *= A[i-j]
        com *= A[i-j-1]
    if std > com:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K =map(int, input().split())
A = list(map(int, input().split()))
for i in range(N-K):
    if A[K+i] > A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = [l.index(i)+1 for i in range(1,n+1)]
print(' '.join(map(str,ans)))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
n = [i for i in range(1,n+1)]
d = dict(zip(l,n))
print(' '.join(map(str,list(d.values()))))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))+[0]
a=[a[i] for i in range(n) if a[i]!=a[i+1]]
s=0
while a:
  n=len(a)
  if n==1:
    a=[]
  else:
    d=a[0]-a[1]>0
    for i in range(n-1):
      if d==(a[i]-a[i+1]<0):
        a=a[i+1:]
        break
    else:
      a=[]
  s+=1
print(s)


### FIXED CODE ###

n = int(input())
ans = 1
a, b = False, False
x = list(map(int, input().split()))
for i in range(1, n):
    if x[i] > x[i - 1]:
        a = True
    if x[i] < x[i - 1]:
        b = True
    if a and b:
        a, b = False, False
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
value = 0
for i in range(n - 1):
    for j in range(i+1, n):
        value += li[i] ^ li[j]
ans = value % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    t = arr & 1
    c1 = np.count_nonzero((arr & 1))
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

import sys
import math
#import numpy as np

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 = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = [(limit // i)%MOD for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += (x*y)%MOD
    answer %= MOD

print(answer)

### FIXED CODE ###

import sys
import numpy as np

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前のdpを更新に使う。
        dp_before_update = dp[:]
        for j in range(N+1):
            dp[j] = (dp_before_update[j-1] * lst_p[i]) + (dp_before_update[j] * (1 - lst_p[i]))
    
    ans = sum(dp[(N//2+1):])

    print(ans)

main()

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = 0
    for i in range((N+1)//2, N+1):
        ans += dp[N][i]

    print(ans)

main()
### BUGGY CODE ###

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

a = [0]*n
for i in range(m):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    a[j-1] += 1

print(a.count(m))

### FIXED CODE ###

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

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)
### BUGGY CODE ###

input()
n = [int(i) for i in input().split()]
index = 0
count = 0
while any([i % 2 == 0 for i in n]):
    if n[index] % 2 == 0:
        n[index] /= 2
        n[index] = int(n[index])
        count += 1
    else:
        index += 1

print(count)

### FIXED CODE ###

input()
n = [int(i) for i in input().split()]
index = 0
count = 0
while index < len(n):
    if n[index] % 2 == 0:
        n[index] /= 2
        n[index] = int(n[index])
        count += 1
    else:
        index += 1
print(count)
### BUGGY CODE ###

import collections
import copy
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    sum = 0
    b = copy.copy(a)
    b.pop(i)
    c = collections.Counter(b)
    for j in c.values():
       sum += j * (j - 1) /2
    print(int(sum))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

c = Counter(a)
key = c.keys()
comb = 0
for i in key:
    comb += (c[i]) * (c[i]-1) // 2 #禁止されていない状態の組み合わせを調べる

for i in a:
    ans = comb - (c[i]-1) #a[i]が禁止されている状態の組み合わせ
    print(ans)
### BUGGY CODE ###

N,M,K = [int(i) for i in input().split()]
graph_fri = [[] for _ in range(N+1)]
graph_blo = [[] for _ in range(N+1)]
for i in range(M):
    A,B = [int(j) for j in input().split()]
    graph_fri[A].append(B)
    graph_fri[B].append(A)
for i in range(K):
    C,D = [int(j) for j in input().split()]
    graph_blo[C].append(D)
    graph_blo[D].append(C)
ans = [0] * N
from collections import deque
for k in range(1,N+1):
    que = deque()
    li = deque()
    seen = [False] * (N+1)
    que.append(k)
    while len(que) != 0:
        x = que.popleft()
        seen[x]=True
        for i in graph_fri[x]:
            if seen[i]:
                continue
            li.append(i)
            que.append(i)
            seen[i] = True
    li = set(list(li))
    graphA = set(graph_fri[k])
    graphB = set(graph_blo[k])
    d = li - graphA - graphB
    ans[k-1] = len(d)
print(*ans)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
#Union Find
N,M,K = inputlist()
graph = [[] for _ in range(N)]
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N)
for i in range(M):
    A,B = inputlist()
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
    unite(A-1,B-1)
bgraph = [[] for _ in range(N)]
for i in range(K):
    C,D = inputlist()
    if same(C-1,D-1):
        bgraph[C-1].append(D-1)
        bgraph[D-1].append(C-1)
li = [0]*N
for i in range(N):
    k = size(i)
    n = len(graph[i])
    m = len(bgraph[i])
    li[i] = k-n-m-1
print(*li)
### BUGGY CODE ###

# coding: utf-8
#解法1 ABのK番まで　＋　CのK番まで
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]

for i in range(min(K,X)):
    for j in range(min(K,Y)):
        AB.append(A[i]+B[j])

AB.sort(reverse=True)
C.sort(reverse=True)

ABC=[]

for i in range(min(K,X*Y)):
    for j in range(min(K,Z)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])


### FIXED CODE ###

# coding: utf-8
#解法1 ABのK番まで　＋　CのK番まで
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]

for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse=True)
C.sort(reverse=True)

ABC=[]

for i in range(min(K,X*Y)):
    for j in range(min(K,Z)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline


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

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        heapq.heappush(mins[uf.find(i)], a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    for v in mins.values():
        ans += heapq.heappop(v)
    other_a = sorted(sum(mins.values(), []))
    return 'Impossible' if len(other_a) < len(mins) - 2 else ans + sum(other_a[:len(mins) - 2])

print(main())


### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline


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

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())
### BUGGY CODE ###


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

H = list(map(int, input().split()))
INF = float("inf")
dp = [INF] * N
dp[0] = 0
dp[1] = abs(H[0] - H[1])

for i in range(2, N):
    # １マス～Kマス先まで飛ぶ。ｊを１～Kまで動かす
    for j in range(1, K+1):
        if i-j < 0:
            break # スタートより後ろに戻る場合は飛ばす
        dp[i] = min(dp[i], dp[i-j] + abs(H[i] - H[i-j])) 

print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float("inf")

dp = [INF] * N
dp[0] = 0
for i in range(1, N):
    for j in range(K):
        if i - j-1 < 0:
            break # スタート地点より手前になる場合は飛ばす
        dp[i] = min(dp[i], dp[i-j-1] + abs(h[i] - h[i-j-1]))

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

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, sys.stdin.readline().split())
h = tuple(map(int, sys.stdin.readline().split()))
cost = [None]*N
cost[0] = 0

for i in range(N+1):
    for j in range(1, K+1):
        if i + j > N-1:
            break
        tmp = cost[i] + abs(h[i] - h[i+j])
        if cost[i+j] == None or cost[i+j] > tmp:
            cost[i+j] = tmp
        
print(cost[N-1])

### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
h = tuple(map(int, sys.stdin.readline().split()))
cost = [None]*N
cost[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i + j > N-1:
            break
        tmp = cost[i] + abs(h[i] - h[i+j])
        if cost[i+j] == None or cost[i+j] > tmp:
            cost[i+j] = tmp

print(cost[N-1])
### BUGGY CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=[0]*TL
CL=[0]*TL #子供の座標

for j in range(TL):
  i=j
  hozon=j
  if SL[i]=="R":
   
    while True:
      if SL[i]=="L":
        index=i
        #print(index)
        break
      i=i+1
    idou=index-hozon
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index-1
  else:
  
    while True:
      if SL[i]=="R":
        index=i
        #print(index)
        break
      i=i-1
    idou=hozon-index
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index+1
for i in range(TL):
  BL[i]=CL.count(i)
print(*BL)

### FIXED CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=[0]*TL
ans=[0]*TL #子供の座標
cnt=0
for j in range(2):
  for i in range(TL):
    
    if SL[i]=="R":
      cnt=cnt+1
    else:
      ans[i]=ans[i]+cnt//2
      ans[i-1]=ans[i-1]+(cnt+1)//2
      cnt=0
    
  SL.reverse()
  ans.reverse()
  for i in range(TL):
    if SL[i]=="R":
      SL[i]="L"
    else:
      SL[i]="R" 
for i in range(TL):
  print(ans[i])
### BUGGY CODE ###

s=input()
a=[0]*13
a[0]=1
for i in s:
  b=[0]*13
  for j,k in enumerate(a):
    b[(j*10)%13]+=k
  a=b[:]
  b=[0]*13
  if i=="?":
    for l in range(10):
      for j,k in enumerate(a):
        b[(j+l)%13]+=k
  else:
    for j,k in enumerate(a):
      b[(j+int(i))%13]+=k
  a=[j%(10**9+7) for j in b]
print(a[5]%(10**9+7))

### FIXED CODE ###

s=input()
a=[0]*13
a[0]=1
for i in s:
  b=[0]*13
  for j,k in enumerate(a):
    b[(j*10)%13]+=k
  a=b[:]
  b=[0]*13
  if i=="?":
    for l in range(10):
      for j,k in enumerate(a):
        b[(j+l)%13]+=k
  else:
    for j,k in enumerate(a):
      b[(j+int(i))%13]+=k
  a=[j%(10**9+7) for j in b]
print(a[5]%(10**9+7))
### BUGGY CODE ###

import sys
from collections import deque


input = sys.stdin.readline


def torf():
    for i in range(2, N):
        n = B[i-2]
        count = 1
        while n != 1:
            n = B[n-2]
            count += 1
        if count != D[i-1]:
            return False
    return True


def main():
    while que:
        nn = que.popleft()
        for n in edges[nn-1]:
            if D[n-1] == INF or D[n-1] > D[nn-1] + 1:
                D[n-1] = D[nn-1] + 1
                que.append(n)
                if n > 1:
                    B[n-2] = nn
    if torf():
        print("Yes")
        for b in B:
            print(b)
    else:
        print("No")


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        edges[a-1].append(b)
        edges[b-1].append(a)
    B = [0]*(N-1)
    que = deque([1])
    INF = 10**10
    D = [INF]*N
    D[0] = 0
    main()


### FIXED CODE ###

import sys
from collections import deque


input = sys.stdin.readline


def main():
    while que:
        nn = que.popleft()
        for n in edges[nn-1]:
            if D[n-1] == INF or D[n-1] > D[nn-1] + 1:
                D[n-1] = D[nn-1] + 1
                que.append(n)
                if n > 1:
                    B[n-2] = nn
    print("Yes")
    for b in B:
        print(b)


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        edges[a-1].append(b)
        edges[b-1].append(a)
    B = [0]*(N-1)
    que = deque([1])
    INF = 10**10
    D = [INF]*N
    D[0] = 0
    main()
### BUGGY CODE ###

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

l = [1]

now_town = 1
loop_town = 0
for i in range(N):
    now_town = A[now_town-1]
    if now_town in l:
        loop_town = l.index(now_town)
        break
    else:
        l.append(now_town)

loop_num = len(l)-loop_town
if K > loop_town:
    num = (K - loop_town)%loop_num + loop_town
else:
    num = K
# 
# num = (K+1)%len(l)
# print(l)

print(l[num])

### FIXED CODE ###

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

l = [1]
kanryou_town = [0]*(N+1)
kanryou_town[1] = 1
now_town = 1
loop_town = 0
for i in range(N):
    now_town = A[now_town-1]
    if kanryou_town[now_town] == 1:
        loop_town = l.index(now_town)
        break
    else:
        kanryou_town[now_town] = 1
        l.append(now_town)

loop_num = len(l)-loop_town
if K > loop_town:
    num = (K - loop_town)%loop_num + loop_town
else:
    num = K
#
# num = (K+1)%len(l)
# print(l)

print(l[num])
### BUGGY CODE ###

import sys
n=int(input())
array=[int(i) for i in input().split()]

if n%2==0:
    sub=1
else:
    sub=2
    if array.count(0) != 1:
        print(0)
        sys.exit()

for i in range(sub,n,2):
    if array.count(i) != 2:
        print(0)
        sys.exit()


print(2**int(n/2))

### FIXED CODE ###

import sys
n=int(input())
array=list(map(int, input().split()))

if not (0<=min(array) and max(array)<n):
    print(0)
    sys.exit()

if n%2==0:
    if (n**2)/2 != sum(array):
        print(0)
        sys.exit()
else:
    if (n**2-1)/2 != sum(array):
        print(0)
        sys.exit()

sub_list=list(set(array))

if n%2==0:
    if int(n/2)==len(sub_list):
        print((2 ** int(n / 2))%(10**9 + 7))
    else:
        print(0)
else:
    if int(n/2)==len(sub_list)-1:
        print((2 ** int(n / 2)) % (10 ** 9 + 7))
    else:
        print(0)