Harryxun/stf_run huggingface dataset:
import sys
from collections import Counter

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    s = input()
    N = len(s)
    K = ii()

    if N <= 50:
        A = set()
        for i in range(N):
            for j in range(i, N):
                A.add(s[i:j+1])
        A = list(A)
        A.sort()
        print(A[K-1])
    else:
        c = sorted(list(s))[0]
        A = set()
        for i in range(N):
            if s[i] == c:
                for j in range(5):
                    A.add(s[i:i+j+1])
        A = sorted(list(A))
        print(A[K-1])



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import Counter

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    s = input()
    N = len(s)
    K = ii()

    A = set()
    for i in range(N):
        for j in range(K):
            A.add(s[i:i+j+1])
    A = list(A)
    A.sort()
    print(A[K-1])


if __name__ == '__main__':
    main()
#include <iostream>
using namespace std;
int fact(int n)
{
  int facto=1;
  for (int i = 1; i < n+1;i++)
  {
    facto = facto * i;
  }
  return facto;
}


int main()
{
	int x,y, result;
	cin >> x >> y;
	result = (fact(x)/(2*fact(x-2))) + (fact(y)/(2*fact(y-2)));
	cout << result << endl;
	return 0;
}

### FIXED CODE ###

def fact(n):
  fact=1
  for i in range(1,n+1): 
    fact = fact * i 
  return fact


x,y = input().split()
x = int(x)
y = int(y)
print((fact(x)//(2*fact(x-2))) + (fact(y)//(2*fact(y-2))))
N = int(input())

a = N%100
a = a%10

if a == 0 or a == 1 or a == 6 or a == 8:
    print("pon")
elif a == 3:
    print("bon")
else:
    print("hon"

### FIXED CODE ###

N = int(input())

a = N%100
a = a%10

if a == 0 or a == 1 or a == 6 or a == 8:
    print("pon")
elif a == 3:
    print("bon")
else:
    print("hon")
a,b=map(int,input())
print(a*b)


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
n,k=map(int,input().split())
if(k=0){
print(0)
}
print(n-k)


### FIXED CODE ###

n,k=map(int,input().split())
if k==1:
    print(0)
else:
    print(n-k)
import numpy as np

n = int(input())

a = list(map(int, input().split()))
l = [0 for i in range(100010)]

q = int(input())

s = np.sum(a)

for ae in a:
    l[ae] += 1

ans = []

for i in range(q):
    b, c = map(int, input().split())

    m_num = l[b]
    l[b] = 0
    m_s = m_num*b

    p_s = m_num*c
    l[c] += m_num

    s = s - m_s + p_s

    ans.append(s)

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


### FIXED CODE ###

import numpy as np

n = int(input())

a = list(map(int, input().split()))
l = [0 for i in range(100010)]

q = int(input())

s = np.sum(a)

for ae in a:
    l[ae] += 1

ans = []

for i in range(q):
    b, c = map(int, input().split())

    m_num = l[b]
    l[b] = 0
    m_s = m_num*b

    p_s = m_num*c
    l[c] += m_num

    s = s - m_s + p_s

    ans.append(s)

for i in range(q):
    print(ans[i])
N = int(input())
b = list(map(int,input().split()))

a = []
a.append(b[-1])
for i in range(1,N-1):
    a.append(min(b[-i], b[-(i+1)]))
a.append(max(b[0], b[1]))

print(sum(a))

### FIXED CODE ###

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

a = []
a.append(b[-1])
for i in range(1,N-1):
    a.append(min(b[-i], b[-(i+1)]))
a.append(max(b[0], a[N-2]))

print(sum(a))
n = input()

d = [1000 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]

def BFS(s):
  q = []
  q.append(s)
  d[s] = 0
  while q.length != 0:
    u = q.pop()
    for v in range(n):
      if M[u][v] == 0 and d[v] != 1000:
        d[v] = d[u] + 1
        q.push(v)
  for i in range(n):
    print i+1, d[i]

for i in range(n):
  G = map(int, raw_input().split())
  for j in range(X[1]):
    M[G[0]-1][G[2+j]-1] = 1

BFS()

### FIXED CODE ###

n = input()
  
d = [-1 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
  
def BFS(s):
  color[0] = 1
  q = []
  q.append(s)
  d[s] = 0
  while len(q) != 0:
    u = q[0]
    q.pop(0)
    for v in range(n):
      if M[u][v] == 1 and color[v] == 0:
        color[v] = 1
        d[v] = d[u] + 1
        q.append(v)
  color[u] = 2
  for i in range(n):
    print i+1, d[i]
  
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    M[G[0]-1][G[2+j]-1] = 1
  
BFS(0)
T = str(input())
T += "P"
ans = ""

# 末尾が"P"なら無条件でD, 末尾が"D"なら今見ている文字の次が"P"なら"D", "D"なら"P"

for i in range(len(T)-1):
    if T[i] == "?":
        if ans[-1] == "P":
            ans += "D"
        elif ans[-1] == "D":
            if T[i+1] == "P":
                ans += "D"
            elif T[i+1] in ["D", "?"]:
                ans += "P"
    else:
        ans += T[i]
print(ans)


### FIXED CODE ###

T = str(input())
T += "P"
ans = ""

# 末尾が"P"なら無条件でD, 末尾が"D"なら今見ている文字の次が"P"なら"D", "D"なら"P"

for i in range(len(T)-1):
    if i == 0 and T[i] == "?":
        if T[i+1] == "P":
            ans += "D"
        else:
            ans += "P"
    else:
        if T[i] == "?":
            if ans[-1] == "P":
                ans += "D"
            elif ans[-1] == "D":
                if T[i+1] == "P":
                    ans += "D"
                elif T[i+1] in ["D", "?"]:
                    ans += "P"
        else:
            ans += T[i]
print(ans)
N, M = map(int, input().split())

a_s = []

for _ in range(M):
    a_m = int(input())
    a_s.append(a_m)

def count(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in a_s:
        return 0
    else:
        return count(n-1) + count(n-2)

ans = count(N) % 1000000007;

print(ans)


### FIXED CODE ###

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

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

for _ in range(M):
    a = int(input())
    flag[a] = 1


dp[0] = 1
if flag[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1;

for i in range(2, N+1):
    if flag[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])
a,b = (int, input().split())
if a*b%2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b = map(int, input().split())
if (a*b)%2 == 0:
  print("Even")
else:
  print("Odd")
N, T = map(int, input().split())
c = []
t = []

for i in range(N):
    box = [0,0]
    box[0], box[1] = map(int, input().split())
    c.append(box[0])
    t.append(box[1])

cost = 1000
check = -1

for i in range(N):
    if t[i] <=T and c[i] <= cost:
        check = i
        cost = c[i]
        #print(i)
        #print(cost)

if index == -1:
    print('TLE')
else:
    print(cost)

### FIXED CODE ###

N, T = map(int, input().split())
c = []
t = []

for i in range(N):
    box = [0,0]
    box[0], box[1] = map(int, input().split())
    c.append(box[0])
    t.append(box[1])

cost = 1000
check = -1
for i in range(N):
    if t[i] <=T and c[i] <= cost:
        check = i
        cost = c[i]
        #print(i)
        #print(cost)

if check == -1:
    print('TLE')
else:
    print(cost)
import math as m1
n, h = map(int, input().split())
a, b = [], []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)
b = list(reversed(sorted(b)))
m = max(a)
ans = 0
for i in b:
    if i > m:
        if h - i <= 0:
            print(ans + 1)
            exit()
        h -= i
        ans += 1
    if 
print(ans + m1.ceil(h / m))

### FIXED CODE ###

import math as m1
n, h = map(int, input().split())
a, b = [], []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)
b = list(reversed(sorted(b)))
m = max(a)
ans = 0
for i in b:
    if i > m:
        if h - i <= 0:
            print(ans + 1)
            exit()
        h -= i
        ans += 1
print(ans + m1.ceil(h / m))
%%time
import math

A,B,H,M =int(input("A :")),int(input("B :")),int(input("H :")),int(input("M :"))
if 1<=A<=1000 and 1<=B<=1000 and 0<=H<=11 and 0<=M<=59:
    hw=(2*math.pi)/(12*60*60) #時針の角速度[rad/s]
    mw=(2*math.pi)/(60*60) #分針の角速度[rad/s]
    time_h=H*60*60 #Hour時間[s] 
    time_m=M*60 #Min時間[s]
    aw=hw*(time_h+time_m) #Arad[rad] #最後の鬼門だった！！なるほどね！40min経ってる間に時針も進んでるから。。
    bw=mw*time_m #Brad[rad]
    rad=abs(bw-aw)
    # 正弦定理で出力結果を得る(a^2=b^2+c^2-2bccosθ)
    print(math.sqrt(A**2+B**2-2*A*B*math.cos(rad)))
    #確認用
    #print(time_h,time_m,aw,bw,rad) 
else: 
    print("各値の条件は次の通り:1<=A,B<=1000,0<=H<=11,0<=M<=59")
    print("あなたの入力:A={},B={},H={},M={}".format(A,B,H,M))

### FIXED CODE ###

import math

A,B,H,M =map(int, input().split())
if 1<=A<=1000 and 1<=B<=1000 and 0<=H<=11 and 0<=M<=59:
    hw=(2*math.pi)/(12*60*60) #時針の角速度[rad/s]
    mw=(2*math.pi)/(60*60) #分針の角速度[rad/s]
    time_h=H*60*60 #Hour時間[s] 
    time_m=M*60 #Min時間[s]
    aw=hw*(time_h+time_m) #Arad[rad] #最後の鬼門だった！！なるほどね！40min経ってる間に時針も進んでるから。。
    bw=mw*time_m #Brad[rad]
    rad=abs(bw-aw)
    # 正弦定理で出力結果を得る(a^2=b^2+c^2-2bccosθ)
    print(math.sqrt(A**2+B**2-2*A*B*math.cos(rad)))
    #確認用
    #print(time_h,time_m,aw,bw,rad) 
else: 
    print("各値の条件は次の通り:1<=A,B<=1000,0<=H<=11,0<=M<=59")
    print("あなたの入力:A={},B={},H={},M={}".format(A,B,H,M))
def gcd(a,b):
    if(a>b):swap(a,b)
    if(a==0):return b
    return gcd(b%a,a)

a,b=map(int,input().split())
print(int(a*b/gcd(a,b)))

### FIXED CODE ###


def gcd(a,b):
    if(a>b):a,b=b,a
    if(a==0):return b
    return gcd(b%a,a)

a,b=map(int,input().split())
print(int(a*b/gcd(a,b)))
import collections

n = int(input())
blueCards = [input() for i in range(n)]
blueCards = collections.Counter(blueCards)
m = int(input())
redCards = [input() for i in range(m)]
redCards = collections.Counter(redCards)

diff = blueCards - redCards
print(diff.most_common()[0][1])

### FIXED CODE ###

import collections

n = int(input())
blueCards = [input() for i in range(n)]
blueCards = collections.Counter(blueCards)
m = int(input())
redCards = [input() for i in range(m)]
redCards = collections.Counter(redCards)

diff = blueCards - redCards
print(diff.most_common()[0][1]) if diff else print(0)
N, M = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N)

for m in range(M):
  a, b = map(int, input().split())
  uf.union(a, b)
  
print(len(uf.roots()) - 1)

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N+1)

for m in range(M):
  a, b = map(int, input().split())
  uf.union(a, b)
  
print(len(uf.roots()) - 1 - 1)
A=list(int(input())for i in range(5))
com=0
num=-1
for i in range(5):
    if A[i]%10==0:
        continue
    else:
        rem=10-A[i]%10
    if com<rem:
        com=rem
        num=i
        tmp=A[i]
if len(A)!=0:
    A[num]=0
ans=0
for a in A:
    if a==0:
        continue
    if a%10==0:
        ans+=a
    else:
        ans+=(a//10+1)*10
ans+=tmp
print(ans)


### FIXED CODE ###

A=list(int(input())for i in range(5))
ans=0
num=0
com=0
for a in A:
    if a%10==0:
        ans+=a
    else:
        tmp=10-a%10
        ans+=(a//10+1)*10
        if com<tmp:
            com=tmp
            num=a
if num==0:
    print(ans)
else:
    ans-=(num//10+1)*10
    ans+=num
    print(ans)
a,b =(int(i) for i in input().split())

try:
  print(a - (b*2))
else:
  print("0")

### FIXED CODE ###

a,b =(int(i) for i in input().split())
result = a - (b*2)
if result > 0:
  print(result)
else:
  print("0")
# -*- coding: utf-8 -*-
     
id, gate = map(int, input().split())
a = [list(map(int,input().split())) for i in range(gate)]
b = []

for i in range(gate)
    c = range(a[i, 0], a[i, 1])
    b.extend(c)

d = range(id)

d = set(d)
b = set(b)

list = list(b&d)
print(len(list))

### FIXED CODE ###

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

ans = 0
L, R = 0, 114514

for i in range(m):
    l, r = map(int, input().split())
    L, R = max(L, l), min(R, r)

print(R - L + 1 if R - L + 1 >= 1 else 0)
N,M,K = int(input())
ans = 'win'
if N+M+K >= 22:
  ans = 'bust'
print(ans)

### FIXED CODE ###

N,M,K = map(int,input().split())
ans = 'win'
if N+M+K >= 22:
  ans = 'bust'
print(ans)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = []
temp=0
for i in range(m):
    x.append(a[i]-temp-1)
    temp = a[i]+1
x.append(n-temp)

temp = 1
div = 1000000007

for i in x:
    temp = (temp*fib(i+1))%div

print(temp)


### FIXED CODE ###

def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = []
temp=0
for i in range(m):
    x.append(a[i]-temp-1)
    temp = a[i]+1
x.append(n-temp)

temp = 1
div = 1000000007

for i in x:
    temp = (temp*Fib(i+1))%div

print(temp)
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))


### FIXED CODE ###

b = input()

if b == "A":
    result = "T"
elif b == "C":
    result = "G"
elif b == "G":
    result = "C"
elif b == "T":
    result = "A"

print(result)
import copy
inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_list = []
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    prime_list.append(2)
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        prime_list.append(i)
if m_copy != 1:
    prime_list.append(m_copy)
import collections
k = collections.Counter(prime_list)
b = list(k.values())
import math
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

### FIXED CODE ###

import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1

dp = [[1 for _ in range(30)] for _ in range(n)]
for i in range(1, 30):
    for j in range(1,n):
        dp[j][i] = (dp[j - 1][i] + dp[j][i - 1]) % inf

for bb in b:
    ans *= dp[n - 1][bb]
    ans = ans % inf
print(ans)
print(math.factorial(int(input()))%(10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
n=int(input())
a=list(map(int, input().split()))
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1] and a[i+1]>a[i+2]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1] and a[i+1]<a[i+2]:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1] and kai==0:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)
n = int(input())
m = int(input())
print((n-1)*(m-1))


### FIXED CODE ###

n,m = map(int,input().split())
print((n-1)*(m-1))
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 1:
    return a
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  rs = 1
  for i in range(s):
    rs = rs*(n-i)%mod
  rl = rs
  for i in range(s,l):
    rl = rl*(n-i)%mod
  for i in range(1,s+1):
    rs = rs*mpow(i,mod-2)%mod
  rl = rl
  for i in range(s+1,l+1):
    rl = rl*mpow(i,mod-2)%mod
  if a < b:
    nCa, nCb = rs, rl
  else:
    nCa, nCb = rl, rs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa,nCb)

### FIXED CODE ###

inp = [int(i) for i in input().split()]
N = inp[0]
R = inp[1]
if N >= 10:
	print(R)
else:
  	print(R+100*(10-N))
def sum(n):
  n=str(n)
  return sum(list(map(int,n)))

t=0
n,a,b=map(int,input().split())
for i in range(n+1):
  if a<=sum(i)<=b:t+=i
print(t)

### FIXED CODE ###

def SUM(N):
  N=str(N)
  return sum(list(map(int,N)))

t=0
n,a,b=map(int, input().split())
for i in range(n+1):
  if a<=SUM(i)<=b:t+=i
print(t)
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    tmp_color = 1
    for edge in n_list[node]:
        try:
            if edge[1] == parent_edge_id:
                continue
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
        except Exception:
            print(0)
        paint(edge[0], edge[1])
        tmp_color += 1

    
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num    a
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])
a=input()
print(str(ord(a)+1)

### FIXED CODE ###

a=input()
b = chr(ord(a)+1)
print(b)
s = list(input())
s.sort()

t = list(input())
t.sort(reverse=True)

if s == t:
    print('No')
else:
    j = 0
    for i in s:
        if i < t[j]:
            print('Yes')
            break

        if i > t[j]:
            print('No')
            break
        j += 1



### FIXED CODE ###

s = list(input())
s.sort()

t = list(input())
t.sort(reverse=True)

if s < t:
    print('Yes')
else:
    print('No')
import numpy as np

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

#階乗
def factorial(a):
    if a == 0:
        return 1
    else: 
        val = 1
        for i in np.arange(a)+1:
            val = val * i
        return val
    
def factorial2(a,b):
    if a == 0:
        return 1
    else: 
        val = 1
        for i in np.arange(b)+a-b+1:
            val = val * i
        return val

#組み合わせ数
def comb(a,b):
    return int(factorial2(a,b)/factorial(b))

for i in range(k):
    print(int(comb(k-1,i) * comb(n-k+1,i+1)) % (pow(10, 9) + 7))

### FIXED CODE ###

import numpy as np

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

for i in range(k):
    print(int(comb(k-1,i, pow(10, 9) + 7) * comb(n-k+1,i+1, pow(10, 9) + 7)) % (pow(10, 9) + 7))