Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x!=par[p]:
            par[x]=p
            descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[-1]+[0]*n

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)
cur(1)
sys.exit()

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+2)]
descend=[1 for i in range(n+1)]
par=[0]+[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)

cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])
import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

    return (A//c,B//c)
 
 
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod
 
 
 
def resolve():
    N = int(input())
 
    
    km = dict()
    kp = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())
 
        if A == 0 and B == 0:
            zerozero+=1
            raise
            continue
 

 
        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)
 
 
 
        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    ans = 1

    groups = []
    for (x,y),v in km.items():
        if (-y,x) in kp:
            groups.append((v,kp[(-y,x)]))
            del kp[(-y,x)]
        else:
            groups.append((v,0))

    for v in kp.values():
        groups.append((v,0))


    for i,j in groups:
        ans *= (pow_r(2,i)+pow_r(2,j)-1)%1000000007
        ans %= 1000000007



    print((ans+zerozero-1)%(10**9+7))       

resolve()

### FIXED CODE ###

import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

    return (A//c,B//c)
 
 
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod
 
 
 
def resolve():
    N = int(input())
 
    
    km = dict()
    kp = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())
 
        if A == 0 and B == 0:
            zerozero+=1

            continue
        
        if A == 0:
            B = -abs(B)
        if B == 0:
            A = abs(A)

 
        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)
 
 
 
        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    ans = 1

    groups = []
    for (x,y),v in km.items():
        if (-y,x) in kp:
            groups.append((v,kp[(-y,x)]))
            del kp[(-y,x)]
        else:
            groups.append((v,0))

    for v in kp.values():
        groups.append((v,0))


    for i,j in groups:
        ans *= (pow_r(2,i)+pow_r(2,j)-1)%1000000007
        ans %= 1000000007



    print((ans+zerozero-1)%(10**9+7))       

resolve()
def main ():
N = int(input())
A = list(map(int,input().split()))

prod = 1 
for a in A:
  prod *= a
  if prod > 1000000000000000000:
    print(-1)
  else:
    print(prod) 

main ()

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  A.sort()
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  
  print(prod) 
 
main()
a = int(input())
l = input()
dp = [0]*1110
qp = [0]*1110
ans = 0
#print('###############')
def bfs(i,x,y):
	#print(i,x)
	if y == 3:
		ans +=1
		return 0
	else:
		for j in range(i,a):
			if int(x+str(l[j])) != 1:bfs(j+1,x+str(l[j]),y+1)
			dp[int(x+str(l[j]))] = 1
bfs(0,'',0)
print(sum(qp))

### FIXED CODE ###

a = int(input())
b = input()
ans = 0
for i in range(1000):
	T = '0'*(3-len(str(i)))
	t = T+ str(i)
	I = 0
	while I < 3:
		for j in b:
			#if t == '022':print(I,t[I],j)
			if I == 3:
				break
			if t[I] == j:I+=1
			#if t == '022':print(I,j)
		
		if I == 3: 
			#print(t)
			ans +=1
		break
print(ans)
n = int(input())
# min, max, sum は関数名なので
# 別名を使うとよい
min0 = 100000
max0 = -100000
sum0 = 0
for i in range(n):
  x = int(input())
  min0 = min(min0, x)
  max0 = max(max0, x)
  sum0 += x
 
print(min0, max0, sum0)



### FIXED CODE ###

n = int(input())
ns = list(map(int, input().split()))

print(min(ns), max(ns), sum(ns))
N,T = map(int,input().split())
t = input().split()
amount =0

if t[0] <= T:
    amount+=t[0]
else:
    amount+=T
    
for index in range(N-1):
    t_sub = int(t[index+1])-int(t[index])
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

### FIXED CODE ###

if __name__ == '__main__':
    N, T = map(int, input().split())
    ts = list(map(int, input().split()))
    
    
amount =0


    
for index in range(N-1):
    t_sub = ts[index+1]-ts[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)
import numpy as np
from fractions import gcd

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))


def main():
    x = 1
    ans = 0
    for a in A:
        tmp = gcd(x, a)
        # ans += (i) * A[i] // tmp + A[i] * x //tmp  
        x = (x * a) // tmp
    
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//a)
        
    print(b%MOD)
main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
def main()->None:
    N, C, K = map(int, input().split())
    range_N = range(N)
    T = [int(input()) for i in range_N] # バスの出発時刻
    T = sorted(T)
    
    bus = 0
    passenger = 0
    start = 0

    for i in range_N:
        if passenger == 0:
            start = t[i] + K
            passenger = 1

        elif passenger == C:
            bus += 1
            start = t[i] + K
            passenger = 1

        else:
            if t[i] > start:
                bus += 1
                start = t[i] + K
                passenger = 1

            else:
                passenger += 1
    print(bus+1)


if __name__ == "__main__":
    main()

### FIXED CODE ###





def main()->None:
    N, C, K = map(int, input().split())
    range_N = range(N)
    T = [int(input()) for i in range_N] # バスの出発時刻
    T = sorted(T)
    
    bus = 0
    passenger = 0
    start = 0

    for i in range_N:
        if passenger == 0:
            start = T[i] + K
            passenger = 1

        elif passenger == C:
            bus += 1
            start = T[i] + K
            passenger = 1

        else:
            if T[i] > start:
                bus += 1
                start = T[i] + K
                passenger = 1

            else:
                passenger += 1
    print(bus+1)


if __name__ == "__main__":
    main()
S = {'MON':6, 'TUE':5, 'WED':4, 'THU':3, 'FRI':2, 'STA':1, 'SUN':7}

s = input()
print = S[s]

### FIXED CODE ###

S = {'MON':6, 'TUE':5, 'WED':4, 'THU':3, 'FRI':2, 'SAT':1, 'SUN':7}

s = input()
print(S[s])
A = int(input())
B = int(input())

if A < B * 2:
    print(0)
else:
    print(A - 2*B)

### FIXED CODE ###

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

if A[0] < A[1] * 2:
    print(0)
else:
    print(A[0] - 2*A[1])
sys.stdin = f
r = int(input())
ans = 3*r*r
print(ans)

### FIXED CODE ###

r = int(input())
ans = 3*r*r
print(ans)
import sys

n, m = map(int, input().split())
x = list(map(int, input().split()))
if m == 1:
    print(0)
    sys.exit()
x.sort()
a = []
for i in range(m - 1):
    a.append(abs(x[i] - x[i + 1]))
ans = sum(a)
a.sort(reverse=True)
for i in range(n - 1):
    ans -= a[i]
print(ans)


### FIXED CODE ###

import sys

n, m = map(int, input().split())
x = list(map(int, input().split()))
if m == 1:
    print(0)
    sys.exit()
if n == 1:
    print(max(x) - min(x))
    sys.exit()
if n >= m:
    print(0)
    sys.exit()
x.sort()
a = []
for i in range(m - 1):
    a.append(abs(x[i] - x[i + 1]))
ans = sum(a)
a.sort(reverse=True)
for i in range(n - 1):
    ans -= a[i]
print(max(0, ans))
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B):
    if A <= 6 and B <= 6:
        return 'Yay!'
    else:
        return ':('


def main():
    A = read_int()
    B = read_int()
    print(slv(A, B))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B):
    if A <= 8 and B <= 8:
        return 'Yay!'
    else:
        return ':('


def main():
    # A = read_int()
    # B = read_int()
    A, B = read_int_n()
    print(slv(A, B))


if __name__ == '__main__':
    main()
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率が高い順にソート
# 効率が同じなら、小規模な順
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))


### FIXED CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))
import sys
n,m = map(int,input().split())
ans = [-1 for i in range(n)]
check = [0 for i in range(n)]
if n == 1:
    s,c = map(int,input().split())
    print(c)
    sys.exit()
else:
    for i in range(m):
        s,c = map(int,input().split())
        if ans[s-1] == -1:
            ans[s-1] = c
        else:
            if c == ans[s-1]:
                continue
            else:
                print(-1)
                sys.exit()
        if s-1 == 0:
            if c == 0:
                print(-1)
                sys.exit()
    for i in range(1,n+1):
        if ans[i] == -1:
            ans[i] = 0
    if ans[0] == -1:
        ans[0] = 1
    ans2 = ''
    for i in range(n):
        ans2 += str(ans[i])
    print(ans2)

### FIXED CODE ###

import sys
n,m = map(int,input().split())
ans = [-1 for i in range(n)]
if n == 1:
    if m == 0:
        print(0)
        sys.exit()
    else:
        for i in range(m):
            s,c = map(int,input().split())
            if ans[s-1] == -1:
                ans[s-1] = c
            else:
                if c == ans[s-1]:
                    continue
                else:
                    print(-1)
                    sys.exit()
        print(ans[0])
else:
    for i in range(m):
        s,c = map(int,input().split())
        if s-1 == 0:
            if c == 0:
                print(-1)
                sys.exit()
            else:
                if ans[s-1] == -1:
                    ans[s-1] = c
                else:
                    if c == ans[s-1]:
                        continue
                    else:
                        print(-1)
                        sys.exit()
        else:
            if ans[s-1] == -1:
                    ans[s-1] = c
            else:
                if c == ans[s-1]:
                        continue
                else:
                    print(-1)
                    sys.exit()
    if ans[0] == -1:
        ans[0] = 1
    for i in range(n):
        if ans[i] == -1:
            ans[i] = 0
    ans2 = ""
    for i in range(n):
        ans2 += str(ans[i])
    print(ans2)
def attk(HP,Magic,D0):
    T = HP // Magic[0][0]
    MD0 = T * Magic[0][1]
    MD1 = (T+1) * Magic[0][1]
    Z = HP % Magic[0][0]
    ND = Magic[0][1]
    if len(Magic) == 1:
        return (MD1)
    A = attk(Z,Magic.pop(0),ND)
    if D0 > MD0+A:
        if MD1 > MD0+A:
            return MD0+A
        else:
            return MD1
    else:
        return D0

H,N = map(int,input().split())
A =[]
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b,a/b))
print(A)
B = sorted(A, key=lambda s: s[1]) 
C = sorted(B, key=lambda s: s[2], reverse=True) 
print(C)

for i in range(N-1):
    if C[N-1-i][2] ==C[N-2-i][2]:
        C.pop(N-1-i)
print(C)
TDMAX = (H // C[0][0])*C[0][1]
if (H%C[0][0])!=0:
    TDMAX += c[0][1]
TD = attk(H,C,TDMAX)
print(TD)

### FIXED CODE ###

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))
n,m = map(int,input().split())
info_list=[]
for i in range(m):
    info_list.append(list(map(int,input().split())))
p_list = list(map(int,input().split()))

count= 0

for i in range((n)**2):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(m) 
    for j in info_list:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k)-1])
        if swith_sum%2 == p_list[info_list.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:        
        count += 1

print(count)

### FIXED CODE ###

n,m = map(int,input().split())
info_list=[]
for i in range(m):
    info_list.append(list(map(int,input().split())))
p_list = list(map(int,input().split()))

count= 0

for i in range(2**n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n) 
    for j in info_list:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k)-1])
        if swith_sum%2 == p_list[info_list.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:        
        count += 1

print(count)
from collections import Counter

s = input()
K = int(input())
c = Counter(s)

key = sorted(c.keys())
ans = []
queue = []

while (len(ans) < K):
    if queue:
        queue = sorted(list(set(queue)))
        res = queue.pop(0)
        ans.append(res)
        ans = list(set(ans))
    else:
        c = key.pop(0)
        queue.append(c)
        ind = [i for i in range(len(s)) if s[i] == c]
        for i in ind:
            for j in range(len(s) - i - 1):
                queue.append(s[i:i+j+1])

print(ans[K-1])


### FIXED CODE ###

from heapq import heappush, heappop

s = input()
K = int(input())

min_s = sorted(list(set(s)))

res = [min(s)]
q = []
x = 0

while len(set(q)) < K:
    min_index = [n for n, v in enumerate(s) if v == min_s[x]]
    for m in min_index:
        for i in range(1, 6):
            if m+i <= len(s):
                q.append(s[m:m+i])
    x += 1

ans = sorted(list(set(q)))[K-1]

print(ans)
size, jumps = map(int, input().split())
array =  list(map(int, input().split()))
dp = [0]* size
dp[1]=  dp[0] + abs(array[1] - array[0]) 
for i in range(1,size):
	for j in range(jumps):	
		if i+j < n :
			dp[i] = min(dp[j],abs(array[i] - array[j]))
print(dp[-1])
		


### FIXED CODE ###

size = int(input())
array =  list(map(int, input().split()))
dp = [0]* size
dp[1]=  dp[0] + abs(array[1] - array[0]) 
for i in range(2,size):
	dp[i] = min(
	dp[i-1] + abs(array[i] - array[i-1]),
	dp[i-2] + abs( array[i] - array[i-2] )
	)
print(dp[-1])
n, m = [int(i) for i in input().split()]

matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split])

vector = []
for mi in range(m):
    vector.append(int(input()))


for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]
        
        print(m)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
  
matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split()])
  
vector = []
for mi in range(m):
    vector.append(int(input()))
  
b = []
for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]
  
    print(sum)
S = int(input())
h = S // 3600
m = (S % 3600) // 60
s = (S % 3600) % 60
print(':'.join[h, m, s])


### FIXED CODE ###

S = int(input())
h = S // 3600
m = (S % 3600) // 60
s = (S % 3600) % 60
print(str(h) + ':' + str(m) + ':' + str(s))
AB = int(input())
BC = int(input())
CA = int(input())
print((AB*BC)/2)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a>b and a>c:
    ans=(0.5)* b * c
elif b>a and b>c:
    ans=(0.5)* a * c
else:
    ans = (0.5) * a * b

print(int(ans))
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]

G=[[] for _ in range(N)]
cnt=[0]*N
for i in range(N-1):
  cnt[AB[i][0]-1]+=1
  cnt[AB[i][1]-1]+=1
  G[AB[i][0]-1].append(AB[i][1])
  G[AB[i][1]-1].append(AB[i][0])
K=max(cnt)
print(K)
#print(G)
#print(cnt)

color=[[] for _ in range(N)]
for i in range(N-1):
  colors=[n for n in range(1,K+1)]
  for j in range(len(color[AB[i][0]-1])):
    colors.remove(color[AB[i][0]-1][j])
  for k in range(len(color[AB[i][1]-1])):
    colors.remove(color[AB[i][1]-1][k])
  color[AB[i][0]-1].append(colors[0])
  color[AB[i][1]-1].append(colors[0])
  print(colors[0])

### FIXED CODE ###

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

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

ans=[None]*(N-1)
def dfs(now,color):
  cnt=1
  for to,j in G[now]:
    if cnt==color:
      cnt+=1
    ans[j]=cnt
    dfs(to,cnt)
    cnt+=1

dfs(0,0)
print(max(ans))
print(*ans, sep="\n")
import bisect
n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab[1])
    if ab[1] == n:
        G.append(ab[0])

S.sort()
G.sort()
        
ans = 'IMPOSSIBLE'
if len(S) != 0 and len(G) != 0:
    for s in S:
        idx = bisect.bisect_left(G, s)
        if s == G[idx]:
            ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
S = set()
G = set()

for i in range(m):
    s, g = map(int, input().split())
    if s == 1:
        G.add(g)
    if g == n:
        S.add(s)

if len(S&G) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')