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

import math

k = int(input())

total = 0
ran = range(1, k + 1)
for i in ran:
    for j in ran:
        for k in ran:
            total += math.gcd(k, math.gcd(i, j))

    
print(total)


### FIXED CODE ###

from math import gcd
from collections import defaultdict

k = int(input())

memo = defaultdict(defaultdict)

rg = range(1, k + 1)
for i in rg:
    for j in rg:
        memo[i][j] = memo[j][i] = gcd(i, j)

ret = 0
for i in rg:
    for j in rg:
        tmp = memo[i][j]
        for k in rg:
            res = memo[k][tmp]
            ret += res

print(ret)
### BUGGY CODE ###

from functools import reduce

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

m = max(a)
d = [0] * (m + 1)
d[1] = 1
for i in range(2, m + 1):
    for j in range(i, m + 1, i):
        if d[j] == 0:
            d[j] = i

def prime_factorize(n):
    res = []
    if n == 1:
        return res
    while n > 1:
        res.append(d[n])
        n //= d[n]
    return res

def is_pairwise_coprime():
    s = set()
    for ai in a:
        p = set(prime_factorize(ai))
        ns = s | p
        if len(s) + len(p) != len(ns):
            return False
        s = ns
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from functools import reduce

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

m = max(a)
d = [0] * (m + 1)
d[1] = 1
for i in range(2, m + 1):
    for j in range(i, m + 1, i):
        if d[j] == 0:
            d[j] = i

def prime_factorize(n):
    res = []
    if n == 1:
        return res
    while n > 1:
        res.append(d[n])
        n //= d[n]
    return res

def is_pairwise_coprime():
    exists = [0] * (m + 1)
    for ai in a:
        for p in set(prime_factorize(ai)):
            if exists[p]:
                return False
            exists[p] = 1
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N , M = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(M)]
relay_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[1] for X in s if X[0] in relay_candidate]
if N in goal_candidate:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

N , M = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(M)]

ans = "IMPOSSIBLE"

start_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[0] for X in s if X[1]==N]

ans = len(start_candidate)+len(goal_candidate)-len(set(start_candidate+goal_candidate))
if ans != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

#+++++

def main():
	n = int(input())
	nn = [[min(i+1,j+1,n-i,n-j) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = False
		nn[x][y]-=1
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v+is_sit[x-1][y]:
				nn[x-1][y] = v+is_sit[x-1][y]
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v+is_sit[x+1][y]:
				nn[x+1][y] = v+is_sit[x+1][y]
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v+is_sit[x][y-1]:
				nn[x][y-1] = v+is_sit[x][y-1]
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v+is_sit[x][y+1]:
				nn[x][y+1] = v+is_sit[x][y+1]
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)


### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

#+++++

def main():
	n = int(input())
	nn = [[min(i,j,n-i-1,n-j-1) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]
		is_sit[x][y] = False
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v:
				nn[x-1][y] = v
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v:
				nn[x+1][y] = v
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v:
				nn[x][y-1] = v
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v:
				nn[x][y+1] = v
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

N, M = map(int, input().split())
a = []
b = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
    a.append(B)
    b.append(A)
for i in range(2*M):
    if a[i] == 1:
        for j in range(2*M):
            if b[i] == a[j] and b[j] == N:
                print("POSSIBLE")
                flag = 1
                break
    if flag == 1:
        break

if flag == 0:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    ship[a].append(b)
    ship[b].append(a)

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
S = [input() for _ in range(n)]
ans = 0

def verify_anagrams(w1, w2):
  f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
  return f(w1) == f(w2)

for i in range(n):
  for j in range(i+1, n):
    if verify_anagrams(S[i], S[j]):
      ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
sorted_word = {}

for i in range(n):
  word = ''.join(sorted(input()))
  sorted_word.setdefault(word, 0)
  sorted_word[word] += 1

def pair_num(n):
  return (n * (n - 1)) // 2

print(sum(map(pair_num, sorted_word.values())))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
print(dp[N-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
	dp=[0]*N
	for i in range(1,N):
		dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
	print(dp[N-1])
main()
### BUGGY CODE ###

h,w,m=[int(x) for x in input().split()]

hnm=[0]*h
wnm=[0]*w
bomb=[]
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hnm[hi]+=1
    wnm[wi]+=1
    bomb.append((hi,wi))

hmax=max(hnm)
wmax=max(wnm)
    
hidx=[]
for idx,val in enumerate(hnm):
    if hmax==val:
        hidx.append(idx)
    
widx=[]
for idx,val in enumerate(wnm):
    if wmax==val:
        widx.append(idx)
    
ofst=-1
for i in hidx:
    for j in widx:
        if not (i,j) in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict
from heapq import heapify
from heapq import heappop
from heapq import heappush
from _collections import defaultdict

h,w,m=[int(x) for x in input().split()]

hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=set()
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add((hi,wi))

hmax=max(hcnt.values())
wmax=max(wcnt.values())

hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

ofst=-1
for i in hidx:
    for j in widx:
        if not (i,j) in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    k = [c]*b
    a = a + k
a.sort()
a = a[-n::]
ans = sum(a)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
p = [(a[i], 1) for i in range(n)]

for i in range(m):
    b, c = map(int, input().split())
    p.append((c, b))
    
p.sort()
p.reverse()
ans, count = 0, n
for (s, t) in p:
    k = min(count, t)
    ans += s * k
    count -= t
    if count <= 0:
        break
    
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L[j+1:],L[i]+L[j])
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()

    n = len(S)
    counts = [0] * 2019
    counts[0] += 1
    T = [0] * (n+1)
    for i in reversed(range(n)):
        T[i] = (10**(n-1-i) * int(S[i]) + T[i+1]) % 2019
        counts[T[i]] += 1

    ans = 0
    for c in counts:
        ans += c*(c-1)//2  # cC2
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

P = 2019

def main():
    S = input().rstrip()

    n = len(S)
    counts = [0] * P
    counts[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + (d * int(s)) % P) % P
        d = (d * 10) % P
        counts[T] += 1

    ans = 0
    for c in counts:
        ans += c*(c-1)//2  # cC2
    print(ans)


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

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    U = set([0])
    dic = {0:1} # value:count
    ans = 0
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        u = V[rev_i+1] % K
        if u in U:
            dic[u] += 1
            cnt = dic[u]
            ans -= (cnt-1) * (cnt-2) // 2
            ans += cnt * (cnt-1) // 2
        else:
            dic[u] = 1
            U.add(u)


    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)

    ans //= 2
    ans %= K
    
    print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

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

from bisect import bisect_left
import sys

input = sys.stdin.readline

n = int(input())
p = tuple(map(int, input().split()))

pos = [[] for _ in range(n + 1)]
for ind, pp in enumerate(p):
    for j in range(pp + 1):
        pos[j].append(ind)

ans = 0
for i, pp in enumerate(p):
    ind = bisect_left(pos[pp], i)

    left = 1
    if ind - 1 >= 0:
        left = i - pos[pp][ind - 1]
    else:
        left = i + 1
    right = 0
    if ind + 1 < len(pos[pp]):
        i_right = pos[pp][ind + 1]
        right = 1
        if ind + 2 < len(pos[pp]):
            right = pos[pp][ind + 2] - i_right
        else:
            right = n - i_right

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

    left = 0
    if ind - 1 >= 0:
        i_left = pos[pp][ind - 1]
        left = 1
        if ind - 2 >= 0:
            left = i_left - pos[pp][ind - 2]
        else:
            left = i_left + 1
    right = 1
    if ind + 1 < len(pos[pp]):
        right = pos[pp][ind + 1] - i
    else:
        right = n - i

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc140/submissions/7411285
# 写経

def main():
    N = int(input())
    *p, = map(int, input().split())

    xtoi = [-1] * (N + 1)
    for i, x in enumerate(p):
        xtoi[x] = i

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    iter_inds = iter(xtoi)
    next(iter_inds)

    ans = 0
    for x, ind in enumerate(iter_inds, start=1):
        # l2, ..., l1, ..., x, ..., r1, ..., r2
        # (l2,r1) or (l1,r2)
        l1 = L[ind]
        l2 = L[l1]
        r1 = R[ind]
        r2 = R[r1]
        ans += x * ((l1 - l2) * (r1 - ind) + (r2 - r1) * (ind - l1))
        L[r1] = l1
        R[l1] = r1
    print(ans)


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

import copy

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

list_tmp = []
list_A = []
dict_AB = {}
for i in range(N):
    A, B = map(int, input().split())
    if dict_AB.get(A) is None:
        dict_AB[A] = B
    else:
        list_tmp.append((A, B))
    list_A.append(A)

list_A.sort()

ct = 0
money = 0
for i in list_A:
    A = i
    tmp = copy.deepcopy(list_tmp)
    if tmp:
        for j in list_tmp:
            if j[0] == A:
                B = j[1]
                list_tmp.remove((A, B))
                break
            else:
                B = dict_AB[A]
    else:
        B = dict_AB[A]
    for j in range(B):
        money += A
        ct += 1
        if ct == M:
            break
    if ct == M:
        break

print(money)


### FIXED CODE ###

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

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

AB.sort(key=lambda x: (x[0], x[1]))

ct = 0
money = 0
for i in AB:
    A, B = i[0], i[1]
    for i in range(B):
        money += A
        ct += 1
        if ct == M:
            break
    if ct == M:
        break

print(money)
### BUGGY CODE ###

'''
期待値
E[X] = sum(1:N)/N
'''

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

# 期待値のリスト生成
ex_list = list()
for i in range(len(p)):
	ex_list.append(sum(range(1,p[i]+1))/p[i])

ans = list()
for i in range(N-K+1):
	ans.append(sum(ex_list[i:i+K]))
	# ans.append(ex_list[i:i+K])
# print(ans)
ans.sort(reverse=True)
print(ans[0])

### FIXED CODE ###

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

# 期待値の累積和リストを生成
ex_list = list() 
for i in range(len(p)):
	if i != 0:
		ex_list.append(((1+p[i])/2)+ex_list[-1])
	else:
		ex_list.append((1+p[i])/2)

ans = ex_list[K-1]
for i in range(N-K):
	# print(i,ex_list[i],ex_list[i+K])
	ex = abs(ex_list[i] - ex_list[i+K])
	if ans < ex:
		ans = ex
print(ans)
### BUGGY CODE ###

n,m=map(int, input().split()) 
key=[]
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])

DP=[[float('inf')]*2**n for i in range(m+1)]
DP[0][0]=0

for i in range(m):
    for j in range(2**n):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j-(j&key[i][1])])
if DP[-1][-1]==float('inf'):
    print(-1)
else:
    print(DP[-1][-1])

### FIXED CODE ###

n,m=map(int, input().split()) 
key=[]
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])

DP=[[float('inf')]*2**n for i in range(m+1)]
DP[0][0]=0

for i in range(m):
    for j in range(2**n):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j-(j&key[i][1])])
if DP[-1][-1]==float('inf'):
    print(-1)
else:
    print(DP[-1][-1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for _ in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count_arr=[0]*n

for i in range(1,n):
  count_arr[i]=count_arr[i-1]+(1 if s[i-1]=='A' and s[i]=='C' else 0)

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

n = int(input())
a = list(map(int, input().split()))
cnt = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    cnt *= a[i]
    if cnt > 10**18:
        cnt = -1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    cnt *= a[i]
    if cnt > 10**18:
        cnt = -1
        break
print(cnt)
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
if D[0] != 0:
  print(0)
  exit()
ans = 1
A = []
for i in range(max(D)+1):
  A.append(D.count(i))
for i in range(max(D)+1):
  if A[i] == 0:
    print(0)
    exit()
  if i > 0:
    ans *= pow(A[i-1], A[i], mod)
print(ans % mod)

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ans = 1
A = [0]*(max(D)+1)
for i in range(N):
  A[D[i]] += 1
if D[0] != 0 or not all(D[1:]) or not all(A):
  print(0)
  exit()
if D[0] != 0:
  print(0)
  exit()
for i in range(1, max(D)+1):
#  if A[i] == 0:
#    print(0)
#    exit()
  ans = ans * pow(A[i-1], A[i], mod) % mod
print(ans % mod)
### BUGGY CODE ###

n=int(input())
a=input()
q=int(input())
ans=[]
for _ in range(q):
    b,c = input().split(' ')
    a = a.replace(b,c)
    ans.append(sum(map(int,a.split(' '))))
for s in ans:
    print(s)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
counter = Counter(a)
sum_res = sum(a)
for _ in range(q):
    before, after = map(int, input().split())
    sum_res -= before * counter[before]
    sum_res += after * counter[before]
    counter[after] += counter[before]
    counter[before] = 0
    print(sum_res)
### BUGGY CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
follow = 0
for i in range(N):
  Amari_ = (int(S[N-i-1]) * pow(10, i) + follow) % 2019
  ans += amari[Amari_]
  amari[Amari_] += 1
  follow = Amari_
  if Amari_ == 0:
    ans += 1

print(ans)

### FIXED CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))
### BUGGY CODE ###

import queue

N = int(input())
ab = []
deg = [0 for i in range(N)]
child = [[] for _ in range(N)]
edge = {}
color = [0 for _ in range(N-1)]
for i in range(N-1):
  tmp = list(map(int, input().split()))
  deg[tmp[0]-1] += 1
  deg[tmp[1]-1] += 1
 
  child[tmp[0]-1].append(tmp[1]-1)
  child[tmp[1]-1].append(tmp[0]-1)
  tmp = [tmp[0]-1, tmp[1]-1]
  edge[tuple(tmp)] = i
  
q = queue.Queue()
q.put([None, 0, None])
used = [0]
# parent, self, color
while not q.empty():
  current = q.get()
  if current[0] is not None:
    cnt = 1
    for c in child[current[1]]:
      if c in used:
        continue
      used.append(c)
      if cnt == current[2]:
        cnt += 1
      q.put([current[1], c, cnt])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = cnt
      
      cnt += 1
  else:
    for i, c in enumerate(child[current[1]]):
      used.append(c)
      q.put([current[1], c, i+1])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      #print(edge[tuple(ind)], i+1)
      color[edge[tuple(ind)]] = i+1
print(max(deg))
for c in color:
  print(c)

### FIXED CODE ###

import queue

N = int(input())
ab = []
deg = [0 for i in range(N)]
child = [[] for _ in range(N)]
edge = {}
color = [0 for _ in range(N-1)]
for i in range(N-1):
  tmp = list(map(int, input().split()))
  deg[tmp[0]-1] += 1
  deg[tmp[1]-1] += 1
 
  child[tmp[0]-1].append(tmp[1]-1)
  child[tmp[1]-1].append(tmp[0]-1)
  tmp = [tmp[0]-1, tmp[1]-1]
  edge[tuple(tmp)] = i
  
q = queue.Queue()
q.put([None, 0, None])
used = [0]
# parent, self, color
while not q.empty():
  current = q.get()
  if current[0] is not None:
    cnt = 1
    for c in child[current[1]]:
  #    if c in used:
  #      continue
      used.append(c)
      if cnt == current[2]:
        cnt += 1
      q.put([current[1], c, cnt])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = cnt
      child[c].remove(current[1])
      cnt += 1
  else:
    for i, c in enumerate(child[current[1]]):
      used.append(c)
      q.put([current[1], c, i+1])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      #print(edge[tuple(ind)], i+1)
      color[edge[tuple(ind)]] = i+1
      child[c].remove(current[1])

print(max(deg))
for c in color:
  print(c)
### BUGGY CODE ###

S = input()
n = len(S)
x = 10 ** 9 + 7
a = [1,0,0,0,0,0,0,0,0,0,0,0,0]
 
c = [1, -3, -4, -1, 3, 4]
for i in range(n):
    b = [0] * 13
    p = i % 6
    if S[n - i - 1] == "?":
        for j in range(13):
            for k in range(10):
                b[j] += a[(j - c[p] * k) % 13]
            b[j] = b[j] % x
        a = b
    else:
        s = int(S[n - i - 1])
        for j in range(13):
            b[j] = a[(j - c[p] * s) % 13]
        a = b
print(a[5])

### FIXED CODE ###

S = input()
n = len(S)
x = 10 ** 9 + 7
a = [1,0,0,0,0,0,0,0,0,0,0,0,0]

c = [1, -3, -4, -1, 3, 4]
for i in range(n):
    b = [0] * 13
    p = i % 6
    if S[n - i - 1] == "?":
        for j in range(13):
            for k in range(10):
                b[j] += a[(j - c[p] * k) % 13]
            b[j] = b[j] % x
        a = b
    else:
        s = int(S[n - i - 1])
        for j in range(13):
            b[j] = a[(j - c[p] * s) % 13]
        a = b
print(a[5])