Harryxun/stf_run huggingface dataset:
N = int(input())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
# print(g)

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])
N, S = map(int, input().split())
A = list(map(int, input().split()))
D = {0: [[-1, -1]]}
for i in range(N):
    L = [[j, D[j]] for j in D]
    L.sort(reverse=True)
    for jn, j in enumerate(L):
        if j[0]+A[i] <= S:
            for kn, k in enumerate(j[1]):
                if j[0]+A[i] in D:
                    D[j[0]+A[i]].append([(j[0]>0)*k[0]+(j[0]==0)*i, i])
                else:
                    D[j[0]+A[i]] = [[(j[0]>0)*k[0]+(j[0]==0)*i, i]]
p = 0
for i in D[S]:
    p += (i[0] + 1) * (N - i[1])
print(p)

### FIXED CODE ###

N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
L = [0 for _ in range(S+1)]
p = 0
F = {0}
for i in range(N):
    L[0] += 1
    X = [[j, L[j]] for j in F]
    for j in X:
        if j[0] + A[i] <= S:
            L[j[0]+A[i]] += j[1]
            L[j[0]+A[i]] %= mod
            F.add(j[0]+A[i])
    p += L[S]
    p %= mod

print(p)
#include <iostream>

using namespace std;

int main() {
    int x;
    cin>>x;
    if (x==0){
        cout<<1<<endl;
        
    }
    else{
        cout<<0<<endl;
    }

    return 0; 
}

### FIXED CODE ###

x=int(input())
if x==0:
  print(1)
elif x==1:
  print(0)
from bisect import bisect_right
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*ab = map(int, read().split())

    AB = []
    for a, b in zip(*[iter(ab)]*2):
        AB.append((a, b))

    ans = 0
    AB.sort()
    a, b = AB[N // 2]
    ans += bisect_right(list(range(a, b+1)), AB[min(N // 2 + 1, N-1)][1])
    
    AB.sort(key=lambda x: x[1])
    a, b = AB[N // 2]
    ans += b - a + 1 - bisect_right(list(range(a, b+1)), AB[N // 2 - 1][0])
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*ab = map(int, read().split())

    AB = []
    for a, b in zip(*[iter(ab)]*2):
        AB.append((a, b))

    if N % 2 == 0:
        AB.sort()
        a1, _ = AB[N // 2 - 1]
        a2, _ = AB[N // 2]
    
        AB.sort(key=lambda x: x[1])
        _, b1 = AB[N // 2 - 1]
        _, b2 = AB[N // 2]

        ans = b1 + b2 - (a1 + a2) + 1
    
    else:
        AB.sort()
        a, _ = AB[N // 2]
    
        AB.sort(key=lambda x: x[1])
        _, b = AB[N // 2]
        
        ans = b - a + 1
    
    print(ans)


if __name__ == "__main__":
    main()
N, A, B, C, D = list(map(int, input().split()))

S = input()

# 以下indexに変更
A-=1
B-=1
C-=1
D-=1

L = [1]*N

# 0を岩、1を通路とする
for i in range(N):
    if S[i] == '#':
        L[i] =  0


def search(idx, g, reversed_goal):
    L[idx] =0
    if not reversed_goal:
        if idx+1 == g:
            L[idx] = 1
            return True
        if idx+2 == g: 
            L[idx] = 1
            return True

    else:
        if idx+2 == g and L[idx+1] and L[idx+3]:
            L[g] = 0
            return True

        if idx+1 == g and L[idx+2]:
            L[g] = 0
            return True

        if idx+1 == g or idx+2 == g:
            return False


    if reversed_goal:
        if L[idx+2] and L[idx+1]:
            L[idx] =1
            L[idx+1] = 0
            return True


    if L[idx+2]:
        L[idx] = 1
        return search(idx+2, g, reversed_goal)
    
    if L[idx+1]:
        L[idx] = 1
        return search(idx+1, g, reversed_goal)
    
    return False

def main():
    reversed_goal = C > D
    if not reversed_goal:
        if search(B,D,False):
            if search(A,C,False):
                return 'Yes'
            
        return 'No'

    else:
        if search(B,D,True):
            if search(A,C,False):
                return 'Yes'

        return 'No'

ans = main()
print(ans)

### FIXED CODE ###

if __name__ == '__main__':
    N, A, B, C, D = map(int, input().split())
    S = str(input())
 
    answer = "-1"
 
    if C < D:
       if S[A:D:].count("##") >= 1:
           answer = "No"
       else:
           answer = "Yes"
    else:
       if S[B-2:D+1:].count("...") >= 1:
           answer = "Yes"
       else:
           answer = "No"
 
    print(answer)
import sys

rhombus = rectangle = 0
for line in sys.stdin:
    a, b, c = map(int, input().split(","))
    if c ** 2 == a ** 2 + b ** 2:
        rectangle += 1
    if a == b and c ** 2 != a ** 2 + b ** 2:
        rhombus += 1
print(rectangle, rhombus)

### FIXED CODE ###

import sys

rhombus = rectangle = 0
for line in sys.stdin:
    a, b, c = map(int, line.split(","))
    if c ** 2 == a ** 2 + b ** 2:
        rectangle += 1
    elif a == b:
        rhombus += 1
print(rectangle)
print(rhombus)
text = "ACL"
output = text * K
print(output)

### FIXED CODE ###

k = int(input())
text = "ACL" * k
print(text)
n,a,b,c,d = map(int,input().split())
s = list(input())

if (b-a)*(d-c)>0 and max(a,b) < min(c,d):
  for i in range(min(a,b),max(c,d)):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  print('Yes')

elif (b-a)*(d-c)>0 and max(a,b) > min(c,d):
  for i in range(a,c):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  for i in range(b,d):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  print('Yes')
 
else:
  for i in range(min(a,b),max(c,d)):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  for i in range(max(a,b),min(c,d)+1):
    if s[i-1]=='.' and s[i]=='.' and s[i+1]=='.':
      print('Yes')
      exit()
  print('No')

### FIXED CODE ###

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

if (b-a)*(d-c)>0 and max(a,b) < min(c,d):
  for i in range(min(a,b)-1,max(c,d)):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  print('Yes')

elif (b-a)*(d-c)>0 and max(a,b) > min(c,d):
  for i in range(a-1,c):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  for i in range(b-1,d):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  print('Yes')
 
else:
  for i in range(min(a,b)-1,max(c,d)):
    if s[i]=='#' and s[i+1]=='#':
      print('No')
      exit()
  for i in range(max(a,b)-1,min(c,d)):
    if s[i-1]=='.' and s[i]=='.' and s[i+1]=='.':
      print('Yes')
      exit()
  print('No')
import math
N=int(input())
s = list( map(int , input().split()) )
ans = s[0]
count = 0
for i in range(1,N-1):
 ans = math.gcd(ans,s[i])
while i < pow(10,9):
 if ans%2 == 0:
  count +=1
  ans = ans/2
 else:
  break
print(count)

### FIXED CODE ###

import fractions
N=int(input())
s = list( map(int , input().split()) )
ans = s[0]
count = 0
for i in range(1,N):
 ans = fractions.gcd(ans,s[i])
while i < pow(10,9):
 if ans%2 == 0:
  count +=1
  ans = ans/2
 else:
  break
print(count)
L, R = map(int, input().split())
ans_l = []
if R-L<2019:
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = (i*j)%2019
            ans_l.append(ans)
    print(min(ans_l)):
else:
    print(0)

### FIXED CODE ###

L, R = map(int, input().split())
ans_l = []
if R-L<2019:
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = (i*j)%2019
            ans_l.append(ans)
    print(min(ans_l))
else:
    print(0)
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():

    n = gete(int)
    l = list(geta(int))
    l.sort()

    l_max = 2000
    # p[k]: number of sticks with length >= k
    p = np.zeros((l_max + 1), dtype=np.int64)

    for li in l:
        p[:li + 1] += 1

    ans = 0
    for i, a in enumerate(l):
        for b in l[i + 1:]:
            ans += p[abs(a - b) + 1] - p[a + b]

            if abs(a - b) < a:
                ans -= 1

            if abs(a - b) < b:
                ans -= 1
    print(ans // 3)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():

    n = gete(int)
    l = list(geta(int))
    l.sort()

    l_max = 2000
    # p[k]: number of sticks with length >= k
    p = [0] * (l_max + 1)

    cur = 0
    acc = n
    for i in range(l_max + 1):
        p[i] = acc

        if cur < n and i == l[cur]:
            while cur < n and l[cur] == i:
                acc -= 1
                cur += 1

    ans = 0
    for i, a in enumerate(l):
        for b in l[i + 1:]:
            ans += p[abs(a - b) + 1] - p[a + b]

            if abs(a - b) < a:
                ans -= 1

            if abs(a - b) < b:
                ans -= 1
    print(ans // 3)


if __name__ == "__main__":
    main()
import math
n = input()
n = int(n.replace(' ', ''))

re = 'No'
for n == int(math.sqrt(n) ** 2):
    re = 'Yes'
        
print(re)

### FIXED CODE ###

import math
a, b = list(map(str,input().split()))
re = 'No'
concat = int(a + b)
# print(concat, math.sqrt(concat) ** 2, math.sqrt(concat))
if concat == int(math.sqrt(concat)) ** 2:
    re = 'Yes'
    
print(re)
#!/usr/bin/env python


matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]

def dfs(x,y,fruit):
  visited.append((x,y))
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if not (nx,ny) in visited and nx in xrange(w) and ny in xrange(h):
      if matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)



while True:
  h,w = map(int,raw_input().rstrip().split(" "))
  if h == 0 and w == 0:
    break
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
  for i in xrange(h):
    for j in xrange(w):
      if not (j,i) in visited:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans

### FIXED CODE ###

#!/usr/bin/env python
import sys

sys.setrecursionlimit(20000)

matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]
h = 0
w = 0

def dfs(x,y,fruit):
  #visited.append((x,y))
  visited[y][x] = 1
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if nx in xrange(w) and ny in xrange(h):
      if visited[ny][nx]==0 and matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)
  return 0


while True:
  h,w = map(int,raw_input().split())
  if h == 0 and w == 0:
    break
#  print h,w
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
    visited.append([0]*w)
  for i in xrange(h):
    for j in xrange(w):
      #if not (j,i) in visited:
      if visited[i][j] == 0:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans
import numpy as np
 
if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    ret = -1
    A_sum = sum(A)
    if not (A_sum < 0):
        ret = N - A_sum
    print(int(ret))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split(" ")))
val = N-sum(A)
if val < 0:
    print(-1)
else :
    print(N-sum(A))
import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
N = int(input())
D = list(map(int, input().split()))
mD = max(D)

c = collections.Counter(D)
c = dict(c)

ans = 1
tmp = 1
for i in range(mD+1):
    if not(i in c.keys()):
        ans = 0
        break
    elif i == 0:
        if c[0] > 1:
            ans = 0
            break
    elif i == 1:
        tmp = c[i]
    else:
        ans = (ans * tmp**c[i])%MOD
        tmp = c[i]

if N == 1:
    if D[0] == 0:
        print(1)
    else:
        print(0)
elif N < 5:
    print(D[100])
else:
    print(ans)

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
N = int(input())
D = list(map(int, input().split()))
mD = max(D)

c = collections.Counter(D)
c = dict(c)

ans = 1
tmp = 1
for i in range(mD+1):
    if not(i in c.keys()):
        ans = 0
        break
    elif i == 0:
        if c[0] > 1:
            ans = 0
            break
    elif i == 1:
        tmp = c[i]
    else:
        ans = (ans * tmp**c[i])%MOD
        tmp = c[i]

if D[0] != 0:
    print(0)
else:
    print(ans)
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		dp_src=dp[i-match_cnt]  #dpの遷移元
		if 0<=i-match_cnt and dp_src is not None:
			if dp[i] is None:
				dp[i]=dp_src+str(a)
			else:
				if int(dp[i])<int( dp_src+str(a) ):
					dp[i]=dp_src+str(a)
				
print dp[N]


### FIXED CODE ###

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]
N = int(input())
A = list(map(int, input().split()))

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    tmp = A[0]
    for i in range(N-2):
        print(tmp, A[i+1])
        tmp -= A[i+1]
    

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    tmp = A[-1]
    for i in range(N-1):
        print(tmp, A[i])
        tmp -= A[i]

elif count_p + count_m == 0:
    print(0)
    for i in range(N-1):
        print(0, 0)
    print(A[2*N])

else:
    print(sum_abs)
    cmz = count_m + count_z
    tmp = A[-1]
    for i in range(cmz - 1):
        print(tmp, A[i])
        tmp -= A[i]
    tmp_2 = A[cmz-1]
    for i in range(count_p-1):
        print(tmp_2, A[i+cmz])
        tmp_2 -= A[i+cmz]
    print(tmp, tmp_2)

### FIXED CODE ###

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

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    tmp = A[0]
    for i in range(N-2):
        print(tmp, A[i+1])
        tmp -= A[i+1]
    print(A[-1], tmp)

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    tmp = A[-1]
    for i in range(N-1):
        print(tmp, A[i])
        tmp -= A[i]

elif count_p + count_m == 0:
    print(0)
    for i in range(N-1):
        print(0, 0)

else:
    print(sum_abs)
    cmz = count_m + count_z
    tmp = A[-1]
    for i in range(cmz - 1):
        print(tmp, A[i])
        tmp -= A[i]
    tmp_2 = A[cmz-1]
    if count_p != 0:
        for i in range(count_p-1):
            print(tmp_2, A[i+cmz])
            tmp_2 -= A[i+cmz]
        print(tmp, tmp_2)
def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    found = None
    if _arr[low_ind] >= _ele:
        return low_ind
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
            print "after: " + str(D) + ", " + str(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()
A,B,C = map(int, input().split())
print('Yes') if abs(A-B)<C and A+B>C and A=B and B=C else print('No')

### FIXED CODE ###

A,B,C = map(int, input().split())
print('Yes') if A+B>C and C+B>A and A+C>B and A==B and B==C else print('No')
H, A = map(int, input().split())
times = 0
crack = Fasle
while True:
  H -= A
  times += 1
  if H <= 0:
    crack = True
  if crack:
    break
print(times)

### FIXED CODE ###

H, A = map(int, input().split())
times = 0
crack = False
while True:
  H -= A
  times += 1
  if H <= 0:
    break
print(times)
n,a,b,c,d=map(int,input().split())
s=str(input())
s=s.replace('.','0')
s=s.replace('#','1')
x=0
y=0
f=0
g=0
for i in range(c-a-2):
    x=int(s[i+a+1])
    y=int(s[i+a+2])
    if(x*y==1):
        f=-1
for j in range(d-b-2):
    x=int(s[j+b+1])
    y=int(s[j+b+2])
    if(x*y==1):
        g=-1
if(d<c):
    if(s[b+1:d].find('000')==-1 and ):
        f=-1
if(f==0 and g==0):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
s=str(input())
s=s.replace('.','0')
s=s.replace('#','1')
x=0
y=0
f=0
g=0
for i in range(c-a-1):
    x=int(s[i+a])
    y=int(s[i+a+1])
    if(x*y==1):
        f=-1
for j in range(d-b-1):
    x=int(s[j+b])
    y=int(s[j+b+1])
    if(x*y==1):
        g=-1
if(d<c):
    if(s[b-2:d+1].find('000')==-1):
        f=-1
if(f==0 and g==0):
    print('Yes')
else:
    print('No')
from collections import deque
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(1,N+1):
  G[i].append(A[i])

l = deque([A[1]])
seen = [False for i in range(N+1)]
seen[1] = True
d = [0 for i in range(N+1)]
d[A[1]] = 1
for i in range(K):
  v = l.popleft()
  if seen[v] != True:
    seen[v] = True
    l.append(A[v])
    if seen[A[v]] == True: 
      a = d[A[v]]
      b = d[v] + 1 - a
    else:  
      d[A[v]] = d[v] + 1
  else:  
    start = v
    break

kaisu = (K-a)%b
p = start
for i in range(kaisu):
  p = A[p]
print(p)  

### FIXED CODE ###

import sys
from collections import deque
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(1,N+1):
  G[i].append(A[i])

l = deque([A[1]])
seen = [False for i in range(N+1)]
seen[1] = True
d = [0 for i in range(N+1)]
d[A[1]] = 1
if A[1] == 1:
  print(1)
  sys.exit()

for i in range(K):
  v = l.popleft()
  if seen[v] == False:
    seen[v] = True
    l.append(A[v])
    if seen[A[v]] == True: 
      a = d[A[v]]
      b = d[v] + 1 - a
    else:  
      d[A[v]] = d[v] + 1
  else:  
    start = v
    break  
  if i == K-1:
    print(v)
    sys.exit()

kaisu = (K-a)%b
p = start
for i in range(kaisu):
  p = A[p]
print(p)
print(''.join(i[0] for i in input().split()).upper())

### FIXED CODE ###

s = input().split()
print(''.join(i[0] for i in s).upper())
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
for i in range(H):
    for j in range(W):
        if s[i][j]=='#':
            continue
            #もし見ている文字が#だったら通過
        cnt=0
        for k in [-1,0,1]:
            if i+k<0 or H<=i+k:
                continue
                #iが端の時通過
            for l in [-1,0,1]:
                if j+l<0 or j+l>=W:
                    continue
                    #jが端の時通過
                cnt+=1*(S[i+k][j+l]=='#')
                #一個前一個上~一個下一個右までの#の数を足す
        S[i][j]=str(cnt)
        #見ていた数を足した数字に変更
for i in range(H):
    print("".join(S[i]))


### FIXED CODE ###

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
            #もし見ている文字が#だったら通過
        cnt=0
        for k in [-1,0,1]:
            if i+k<0 or H<=i+k:
                continue
                #iが端の時通過
            for l in [-1,0,1]:
                if j+l<0 or j+l>=W:
                    continue
                    #jが端の時通過
                cnt+=1*(S[i+k][j+l]=='#')
                #一個前一個上~一個下一個右までの#の数を足す
        S[i][j]=str(cnt)
        #見ていた数を足した数字に変更
for i in range(H):
    print("".join(S[i]))
temp_dict = {
    "R": [],
    "G": [],
    "B": [],
}
for i, c in enumerate(s):
    temp_dict[c].append(i)

ans = 0
temp_list = list(product(temp_dict["R"], temp_dict["G"], temp_dict["B"]))
for temp in temp_list:
    temp = sorted(list(temp))
    if temp[0] - temp[1] != temp[1] - temp[2]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b
for i in range(n - 2):
    for j in range(i + 2, n, 2):
        if s[i] != s[(i + j) >> 1] != s[j] != s[i]:
            ans -= 1
print(ans)
def main():
    N = input().strip()
    ans = 0
    count = 0
    for i in range(len(N)):
        if N[i] != "9":
            break
        count += 1
    if count == len(N):
        print(9*count)
    elif count == len(N)-1:
        print(9*count+int(N[-2])-1)
    else:
        print(9*(len(N)-1)+int(N[count])-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = input().strip()
    all_nine = True
    for i in range(1, len(N)):
        if N[i] != "9":
            all_nine = False
    ans = int(N[0]) + 9 * (len(N) - 1)
    if all_nine:
        print(ans)
    else:
        print(ans - 1)

if __name__ == "__main__":
    main()