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

N,M,K=map(int,input().split())
A,B=[0],[0]
A+=map(int,input().split())
B+=map(int,input().split())

for i in range(1,N+1):
    A[i]+=A[i-1]
for i in range(1,M+1):
    B[i]+=B[i-1]

ans=0
for i in range(N+1):
    for j in range(M+1):
        x=A[i]+B[j]
        if x>K:
            break
        ans=max(ans,i+j)

print(ans)


### FIXED CODE ###

N,M,K=map(int,input().split())
A,B=[0],[0]
A+=map(int,input().split())
B+=map(int,input().split())

for i in range(1,N+1):
    A[i]+=A[i-1]
for i in range(1,M+1):
    B[i]+=B[i-1]

ans,j=0,M
for i in range(N+1):
    if A[i]>K:
        break
    while j>0 and A[i]+B[j]>K:
        j-=1
    ans=max(ans,i+j)

print(ans)
### BUGGY CODE ###

import numpy as np

N, W = [int(x) for x in input().split()]
weight = np.zeros((N,2))
for x in range(N):
    weight[x] = [int(y) for y in input().split()]
#topdown
memo = np.zeros((N+1,W+1))
for x in range(N+1):
    memo[x] = [-1]*(W+1)

def dp(n,w):
    if w < 0:
        return -float('inf')
    elif n == 0 or w == 0:
        return 0
    elif memo[n][w] != -1:
        return memo[n][w]
    else:
        memo[n][w] = max(dp(n-1,w), dp(n-1,w - int(weight[n-1][0])) + weight[n-1][1])
        return memo[n][w]

print(int(dp(N,W)))

### FIXED CODE ###

import numpy as np

N, W = [int(x) for x in input().split()]
items = [tuple(map(int, input().split())) for _ in range(N)]

#topdown
memo = np.zeros(shape = W+1, dtype = np.int64)

for w,v in items:
    memo[w:] = np.maximum( memo[w:], memo[:-w] + v)

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

import sys

F = 2*10**5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

stack=[0]
order=[0]
parent=[0]*n
while stack:
    node = stack.pop()
    for child in neighbers[node]:
        if child==parent[node]:
            continue
        stack.append(child)
        order.append(child)
        parent[child]=node

# (size,combination)
upinfo=[(0,1)]*n
downinfo=[(0,1)]*n

for node in order[::-1]:
    if len(neighbers[node])==1:
        downinfo[node]=(1,1)
    else:
        totalsize=0
        totalcomb=1
        for child in neighbers[node]:
            if child == parent[node]:
                continue
            size,comb=downinfo[child]
            totalsize+=size
            totalcomb=(totalcomb*comb)%mod
            totalcomb=(totalcomb*inv[size])%mod
        totalcomb=(totalcomb*fact[totalsize])%mod
        downinfo[node]=(totalsize+1,totalcomb)
for node in order[1:]:
    totalsize=0
    totalcomb=1
    for brother in neighbers[parent[node]]:
        if brother == node:
            continue
        size,comb=upinfo[parent[node]] if brother == parent[parent[node]] else downinfo[brother]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    upinfo[node]=(totalsize+1,totalcomb)
for node in range(n):
    totalsize=0
    totalcomb=1
    for child in neighbers[node]:
        size,comb=upinfo[node] if child==parent[node] else downinfo[child]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    print(totalcomb)



### FIXED CODE ###

n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

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

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")
### BUGGY 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
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(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()
### BUGGY CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

state = [[0 for _ in range(C)] for _ in range(3)]
for c in range(C):
    for w in range(N):
        for h in range(N):
            cost = D[grid[h][w]-1][c]
            state[(h+w)%3][c] += cost

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c3 == c1 or c3 == c2:
                continue
            cost = state[0][c1] + state[1][c2] + state[2][c3]
            if c1 == 0 and c2 == 1 and c3 == 2:
                ans = cost
                continue
            ans = min(cost, ans)
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

def main():
    state = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for w in range(N):
            for h in range(N):
                cost = D[grid[h][w]-1][c]
                state[(h+w)%3][c] += cost

    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c3 == c1 or c3 == c2:
                    continue
                cost = state[0][c1] + state[1][c2] + state[2][c3]
                if c1 == 0 and c2 == 1 and c3 == 2:
                    ans = cost
                    continue
                ans = min(cost, ans)
    print(ans)

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

# /usr/bin/python
# -*- coding: utf-8 -*-
import math



D = 10**9+7

def main():
  NM = sorted(list(map(int, input().split())))
  if NM[1]-NM[0] > 1:
    return 0
  elif NM[0]==NM[1]:
    ret = 2*(math.factorial(NM[0])**2) % D
    return ret
  else:
    ret = math.factorial(NM[0])*math.factorial(NM[1])
    return ret

if __name__ == "__main__":
  print(main())

### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import math



D = 10**9+7

def main():
  NM = sorted(list(map(int, input().split())))
  if NM[1]-NM[0] > 1:
    return 0
  elif NM[0]==NM[1]:
    ret = 2*(math.factorial(NM[0])**2) % D
    return ret
  else:
    ret = math.factorial(NM[0])*math.factorial(NM[1]) % D
    return ret

if __name__ == "__main__":
  print(main())
### BUGGY CODE ###

N=int(input())
S=[input() for n in range(N)]

kind=[]
for e in S:
    if e not in kind:
        kind.append(e)

print(len(kind))

### FIXED CODE ###

N=int(input())
S=[input() for n in range(N)]

S.sort()

i=1
prev=S[0]
for e in S:
    if prev!=e:
        i+=1
    prev=e

print(i)
### BUGGY CODE ###

import numpy as np

n, q = map(int, input().split())
s = input()
l_ = np.zeros(q)
r_ = np.zeros(q)

for i in range(q):
    l_tmp, r_tmp = map(int, input().split())
    l_[i] = l_tmp
    r_[i] = r_tmp
l_ = l_ - 1
r_ = r_ - 1
for i in range(q):
    cnt = 0
    t = s[int(l_[i]) : int(r_[i]) + 1]
    for j in range(len(t) - 1):
        if t[j : j + 2] == "AC":
            cnt += 1
    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]

for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  print(a.index(i+1)+1,end=" ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
  ans[a[i]-1] = i+1
for i in range(n):
  print(ans[i],end=" ")
### BUGGY CODE ###

N=int(input())
S=list(input())

ans=0
i=0
while i<N-2:
    j=i+1
    while j<N-1:
        k=j+1
        while k<N:
            ans+=1*(S[i]!=S[j])*(S[j]!=S[k])*(S[k]!=S[i])*(j-i!=k-j)
            k+=1
        j+=1
    i+=1

print(ans)



### FIXED CODE ###

N=int(input())
S=list(input())

ans=S.count('R')*S.count('G')*S.count('B')


i=0
while i<N-1:
    j=i+1
    while 2*j-i<N:
        ans-=1*(S[i]!=S[j])*(S[j]!=S[2*j-i])*(S[2*j-i]!=S[i])
        j+=1
    i+=1

print(ans)
### BUGGY CODE ###

def n_gram(target,n):
    count = 0
    for idx in range(len(target) - n + 1):
        if int(target[idx:idx+n]) % 2019 == 0:
            count += 1
    return count

c = 0
s = input()
n = 4
num_list = ()
s_len = len(s)
while n <= s_len:
    c += n_gram(s,n)
    n += 1
print(c)

### FIXED CODE ###

s = input()[::-1]

count = [0]*2019
count[0] = 1  # そもそもあまりが0ってことは2019の倍数確定なので

num, d = 0, 1  # 初期化

for char in s:
    num += int(char)*d
    num %= 2019
    d *= 10
    d %= 2019
    count[num] += 1  # 2019で割ったあまりをキーとして値を追加していく

ans = 0
for c in count:
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
A = [LIST() for i in range(N-1)]
P = [LIST() for i in range(Q)]

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    tree[A[i][0]-1].append(A[i][1]-1)
    tree[A[i][1]-1].append(A[i][0]-1)

for i in range(Q):
    cnt[P[i][0]-1] += P[i][1]

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N
checked[0] = 1

while q:
    v = q.pop()
    checked[v] = 1
    for u in tree[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    a, b = LIST()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(Q):
    node, point = LIST()
    cnt[node-1] += point

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N
checked[0] = 1

while q:
    v = q.pop()
    checked[v] = 1
    for u in tree[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt)
### BUGGY CODE ###

N = int(input())
S = input()
B = {'R','G','B'}
ans = 0
for i in range(N-1):
    s = S[i]
    for j in range(i+1,N):
        if S[j] != s:
            l = j-i
            t = (B-{s,S[j]}).pop()
            L = S[j+1:j+l]
            R = S[j+l+1:]
            ans += L.count(t)+R.count(t)

print(ans)

### FIXED CODE ###

N = int(input())
S = tuple([s for s in input()])
B = {'R','G','B'}
ans = 0
d = {}
d['R'] = 0
d['G'] = 1
d['B'] = 2
num = [[0,0,0]for _ in range(N+1)]
for i in range(N):
    for j in range(3):
        num[i+1][j] = num[i][j]
        if d[S[i]] == j:
            num[i+1][j] += 1
num = tuple(num[1:])
for i in range(N-2):
    s = S[i]
    for j in range(i+1,N-1):
        if S[j] != s:
            l = j-i
            t = (B-{s,S[j]}).pop()
            L = 0
            R = 0
            if l > N-j-1:
                ans += num[N-1][d[t]]-num[j][d[t]]
            else:
                L = num[j+l-1][d[t]]-num[j][d[t]]
                R = num[N-1][d[t]]-num[j+l][d[t]]
                ans += L+R
print(ans)
### BUGGY CODE ###

N = input()
for i in range(1,int(10e8)) :
    if (i % 2) == 0 :
        if (i % int(N)) == 0 :
            print(i)
            break

### FIXED CODE ###

N = int(input())

if N % 2 == 0 :
    print(N)
else :
    print(N * 2)
### BUGGY CODE ###

# C - Reconciled?
N, M = map(int,input().split())

Sn = 1
for i in range(1,N+1):
    Sn *= i

Sm = 1
for i in range(1,M+1):
    Sm *= i

ans = 0
if abs(N-M) > 1:
    ans = 0
elif abs(N-M) == 1:
    ans = Sn * Sm
else:
    ans = Sn*Sm*2

ans = ans % 1000000007

print(ans)


### FIXED CODE ###

# C - Reconciled?
import math
N, M = map(int,input().split())

S = math.factorial(min(N,M)) % 1000000007

ans = 0
if abs(N-M) > 1:
    ans = 0
elif abs(N-M) == 1:
    ans = S*S*max(N,M)
else:
    ans = S*S*2

ans = ans % 1000000007

print(ans)
### BUGGY CODE ###

import copy

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

ans = 0
finish = False
q = []
base_used = [True] + [False] * N
count = 0

while not finish and count != N:
  finish = True
  ans += 1
  used = copy.deepcopy(base_used)
  
  for idx, u in enumerate(used):
    if not u:
      a = A[idx-1][0]
      if not used[a] and A[a-1][0] == idx:
        used[idx] = True
        used[a] = True
        q.extend([idx, a])
        finish = False
    else:
      continue
  
  while q:
    a = q.pop(0)-1
    A[a].pop(0)
    if not A[a]:
      base_used[a+1] = True
      count += 1

if N != count:
  ans = -1
print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    Id = {}
    
    cur = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            Id[(i,j)] = cur
            cur += 1
            
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: k = Id[(i, j)]
            else: k = Id[(j, i)]
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

MOD = 10**9 + 7
def nCr(n,r):
    numerator, denominator = 1, 1
    for i in range(r):
        # n * N-1 * ... * n-r+1
        numerator = numerator * (n-i) % MOD
        # r * r-1 * ... * 1
        denominator = denominator * (r-i) % MOD

    # フェルマーの小定理より、aの逆元（逆数）が、a**(m-2)とのこと
    denominator = pow(denominator, MOD-2, MOD)
    return numerator * denominator % MOD


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

idxs = [[] for _ in range(N)]
for i,a in enumerate(A):
    idxs[a-1].append(i)

for i in range(N):
    if len(idxs[i]) == 2:
        first = idxs[i][0]
        second = idxs[i][1]
        break

for i in range(1, N+2):
    if i == 1:
        print(N)
    elif i == N+1:
        print(1)

    else:
        a = nCr(N+1, i)
        # firstより左にある数字とsecondより右にある数字からi-1個、firstかsecondを選んで長さiの部分列が作れる場合
        cnt = first + (N-second)
        if cnt >= i-1:
            a -= nCr(cnt, i-1)
            a %= MOD
        
        print(a)


### FIXED CODE ###

from collections import Counter
N = int(input())

A = list(map(int, input().split()))
c = Counter(A)
s = c.most_common()[0][0]
idx_s = [i for i,x in enumerate(A) if x == s]
l = idx_s[0]
r = idx_s[1]

MOD = 10**9+7
fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

for i in range(1,N+2):
    print((nCr(N+1, i) - nCr(l+N+1-(r+1), i-1)) % MOD)
### BUGGY CODE ###

n = int(input())
string = input()
count = []
for i in range(n+1):
    left = string[:i]
    right = string[i:]
    tmp_max = max(left.count("W"), right.count("R"))
    count.append(tmp_max)
print(min(count))

### FIXED CODE ###

n = int(input())
string = input()

left = string[:0]
right = string[0:]
w, r = left.count("W"), right.count("R")
count = max(w,r)

for i in range(1,n+1):
    next_str = string[i-1]
    if next_str == "W":
        w +=1
    else:
        r -= 1
    tmp = max(w,r)
    if tmp < count:
        count = tmp
        
print(count)
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
A = [0]*(N+1)
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = A[i-2] + A[i-1]
print(A[N] %1000000007)

### FIXED CODE ###

N,M = map(int,input().split())
a = set(int(input()) for x in range(M))
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
q=int(input())
bc=[]
for i in range(q):
    bc.append([int(i) for i in input().split()])

import collections
collect = collections.Counter(a)

for i in bc:
    if i[1] in collect:
        collect[i[1]] += collect.pop(i[0],0)
    else:
        if i[0] in collect:
            collect[i[1]] = collect.pop(i[0],0)
    ans=0
    for k,v in collect.items():
        ans += (k * v)
    print(ans)


### FIXED CODE ###

#sum を計算しておく
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
q=int(input())
bc=[]
for i in range(q):
    bc.append([int(i) for i in input().split()])

import collections
collect = collections.Counter(a)

ans=0
for k,v in collect.items():
    ans += (k * v)
for i in bc:
    if i[0] in collect:
        if i[1] in collect:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] += collect.pop(i[0],0)
        else:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] = collect.pop(i[0],0)
    print(ans)
### BUGGY CODE ###

#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
#color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
color =0
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            #color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

K = int(input())

if (K%10) % 2 == 0:
    pass
    print(-1)

elif (K%10) % 5 == 0:
    pass
    print(-1)
else:
    num = 7
    for i in range(K+1):
        if num % K == 0:
            print(str(i+1))
            break
        num = num *10 + 7
    else:
        print(-1)



### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

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

ans = 1
for i in alist:
    ans *= i
    if 0 in alist:
        ans = 0
        break
    elif ans > 10**18:
        ans = -1
        break

print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in alist:
    ans = 0
else:
    for i in alist:
        ans *= i
        if ans > 10**18:
            ans = -1
            break

print(ans)