Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n, x, m = map(int, input().split())
mod_list = [-1 for i in range(m)]
value = x
i = 0
head = 0
while i < n:
    if value not in mod_list:
        mod_list[i] = value
        i += 1
        value = (value**2)%m
    else:
        head = mod_list.index(value)
        break
if i == n:
    print(sum(mod_list[:n]))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print(sum(mod_list[:head]) + sum(mod_list[head:i])*block_num + sum(mod_list[head:head+(n-head)%block_size]))

Fixed submission:
n, x, m = map(int, input().split())
mod_value = [-1 for i in range(2*m)] #余りの値を頭から格納
mod_check = [False for i in range(m)] #余りが現れたか否か
value = x
i = 0
head = 0
while i < n:
    if not mod_check[value]:
        mod_value[i] = value
        mod_check[value] = True
        i += 1
        value = (value**2)%m
    else:
        head = mod_value.index(value)
        break
if i == n:
    print(sum(mod_value[:n]))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print(sum(mod_value[:head]) + sum(mod_value[head:i])*block_num + sum(mod_value[head:head+(n-head)%block_size]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
sum_digit = 0
while n > 0:
    sum_digit += n % 10
    n //= 10
if sum_digit % 9 == 0:
    print("Yes")
else:
    print("No")

Fixed submission:
n = input()
sum_digit = 0
l = len(n)
for i in range(l):
    sum_digit += int(n[i])
if sum_digit % 9 == 0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from sys import exit

x, n = map(int, input().split())
p = list(map(int, input().split()))
for d in range(x+1): #0に達した時点で0を出力して終了するので、大きい側は気にしなくてよい
    for d in [-1, 1]:
        a = x + i*s
        if not a in p:
            print(a)
            exit()

Fixed submission:
x, n = map(int, input().split())
p = [int(i) for i in input().split()]
if n == 0:
    print(x)
else:
    under = over = x
    for num in range(x - min(p) + 2):
        if not (x - num in p):
            under = x - num
            break
    for num in range(max(p) - x + 2):
        if not (x + num in p):
            over = x + num
            break
    if x - under <= over - x:
        print(under)
    else:
        print(over)
Buggy python submission (verdict: Runtime Error):
from math import cos, radians, sqrt

a, b, h, m = map(int, input().split())
angle = radians(h*30 + m / 2- m*6)
print(sqrt(a**2 + b**2 - 2*a*b*cos(angle)))

Fixed submission:
n = int(input())%10
if n in [2, 4, 5, 7, 9]:
    print('hon')
elif n in [0, 1, 6, 8]:
    print('pon')
else:
    print('bon')
Buggy python submission (verdict: Time Limit Exceeded):
N, X, Y = map(int, input().split())
count = [0 for i in range(N)]
dist = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = min(abs(j - i), abs(X - 1 - i) + 1 + abs(Y - 1 - j))
        count[dist[i][j]] += 1
for i in range(1, N):
    print(count[i])

Fixed submission:
N, X, Y = map(int, input().split())
count = [0 for i in range(N)]
dist = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = min(abs(j - i), abs(X - 1 - i) + 1 + abs(Y - 1 - j))
for i in range(N):
    for j in range(i + 1, N):
        count[dist[i][j]] += 1
for i in range(1, N):
    print(count[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
infty = 10 ** 4

def BFS(G, D, u):
    queue = deque()
    queue.append(u)
    visit = [False for k in range(len(D))]
    d = 0
    L = 1
    visit[i] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            D[v] = d
            L -= 1
            for j in G[v]:
                if not visit[j]:
                    queue.append(j)
                    visit[j] = True
                    add_v += 1
        d += 1
        L = add_v
    return D

N, X, Y = map(int, input().split())
G = [[1]]
for i in range(1, N - 1):
    G.append([i - 1, i + 1])
G.append([N - 2])
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)
dist = [[infty for j in range(N)] for i in range(N)]
for i in range(N):
    dist[i] = BFS(G, dist[i], i)
count = [0 for i in range(N)]
for i in range(N):
    for j in range(N):
        count[dist[i][j]] += 1
for i in range(N - 1):
    print(count[i + 1] // 2)

Fixed submission:
N, X, Y = map(int, input().split())
count = [0 for i in range(N)]
dist = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = min(abs(j - i), abs(X - 1 - i) + 1 + abs(Y - 1 - j))
for i in range(N):
    for j in range(i + 1, N):
        count[dist[i][j]] += 1
for i in range(1, N):
    print(count[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
N = len(A)
dictA = {i: A[i] for i in range(len(A))}
dictA_sorted = sorted(dictA.items(), key=lambda x:x[1])
A_sorted = [item[1] for item in dictA_sorted]
sorted_index = [item[0] for item in dictA_sorted]
for count in range(N):
    k = sorted_index.index(count)
    ways = 0
    i = 0
    if k == 0:
        B = A_sorted[1:]
    elif k == N - 1:
        B = A_sorted[:N - 1]
    else:
        B = A_sorted[:k] + A_sorted[k + 1:]
    while i < N - 1:
        head = B[i]
        j = 1
        while j + i < N - 1 and B[j + i] == head:
            j += 1
        ways +=  (j * (j - 1)) // 2
        i += j
    print(ways)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
C = [0 for i in range(N)]
for value in A:
    C[value - 1] += 1
ways_all = 0
for i in range(N):
    ways_all += (C[i] * (C[i] - 1)) // 2
for value in A:
    print(ways_all - C[value - 1] + 1)
Buggy python submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
line = []
for i in range(M):
  line.append([int(i) for i in input().split()])
for i in range(10 ** N):
  i_keta = [i // 100, (i % 100) // 10, i % 10]
  correct = True
  for test in line:
    s = test[0]
    c = test[1]
    if s == 1:
      if N >= 2:
        if i_keta[3 - N] == 0 or i_keta[3 - N] != c:
          correct = False
          break
      elif i_keta[2] != c:
        correct = False
        break
    else:
      if i_keta[s - N + 2] != c:
        correct = False
        break
  if correct:
    if N >= 2 and i_keta[3 - N] != 0:
      print(i)
      sys.exit(1)
    elif N == 1:
      print(i)
      sys.exit(1)
print(-1)

Fixed submission:
from sys import exit
N, M = map(int, input().split())
line = []
for i in range(M):
  line.append([int(i) for i in input().split()])
for i in range(10 ** N):
  i_keta = [i // 100, (i % 100) // 10, i % 10]
  correct = True
  for test in line:
    s = test[0]
    c = test[1]
    if s == 1:
      if N >= 2:
        if i_keta[3 - N] == 0 or i_keta[3 - N] != c:
          correct = False
          break
      elif i_keta[2] != c:
        correct = False
        break
    else:
      if i_keta[s - N + 2] != c:
        correct = False
        break
  if correct:
    if N >= 2 and i_keta[3 - N] != 0:
      print(i)
      exit()
    elif N == 1:
      print(i)
      exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
num = g
d = 2
while num > 1:
    if _is_prime(d):
        flag = True
        while not num % d:
            if flag:
                count += 1
                flag = False
            num = num // d
    d += 1
print(count)

Fixed submission:
def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
num = g
d = 2
while num > 1:
    if _is_prime(d):
        flag = True
        while not num % d:
            if flag:
                count += 1
                num = num // d
                flag = False
            else:
                num = num // d
        d += 1
    else:
        d += 1
print(count)

Fixed submission:
def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
for i in range(2, g + 1):
    if g % i == 0 and _is_prime(i):
        count += 1
print(count)

Fixed submission:
def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
dp = [0] *  (2 * 10 ** 5 + 1)
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for v in range(l, r + 1):
        S.add(v)

dp[1] = 1
MOD = 998244353
for i in range(1, N):
    for v in S:
        if i + v <= N:
            dp[i + v] += dp[i]
            dp[i + v] %= MOD

print(dp[N])



Fixed submission:
N, K = map(int, input().split())
W = [0] * (N + 1)
W[1] = 1

R = []
for i in range(K):
    l, r = map(int, input().split())
    R.append((l, r))

MOD = 998244353
for i in range(1, N):
    for l, r in R:
        a = max(i - r, 0)
        b = i - l
        if b < 0:
            continue
        W[i + 1] += (W[b + 1] - W[a])
        W[i + 1] %= MOD
    W[i + 1] += W[i]
    
print(W[N] - W[N - 1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 10001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    if f == t:
        continue
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 100001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 10001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 100001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A =[0] * 10001
s = 0
for i in map(int, input().split()):
    A[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    A[t] += A[f]
    s += t * A[f]
    s -= f * A[f]
    A[f] = 0
    print(s)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 100001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1


    for i in range(N):
        C[A[i]] -= 1
        ans = 0
        for cnt in C:
            ans +=  (cnt * (cnt - 1)) >> 1

        C[A[i]] += 1
        print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1

    b = 0
    
    for cnt in C:
        b += ((cnt * (cnt - 1)) // 2)

    for i in range(N):
        p = ((C[A[i]] - 1) * (C[A[i]] - 2)) >> 1
        m = (C[A[i]] * (C[A[i]] - 1)) >> 1
        print(b - m + p)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def comb(n, k, MOD = 10 ** 9 + 7):
    if n < k:
        return 0
    if n - k < k:
        k = n - k
    comb = 1
    for x in range(n - k + 1, n + 1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k + 1):
        d = (d * x) % MOD
    comb *= pow(d, MOD - 2, MOD)
    return comb % MOD

def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)
    M = [-1] * (N + 1)

    for i in A:
        C[i] += 1


    for i in range(N):
        C[A[i]] -= 1
        ans = 0
        for cnt in C:
            if M[cnt] == -1:
                value =  comb(cnt, 2)
                ans += value
                M[cnt] = value
            else:
                ans += M[cnt]
        C[A[i]] += 1
        print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1

    b = 0
    
    for cnt in C:
        b += ((cnt * (cnt - 1)) // 2)

    for i in range(N):
        p = ((C[A[i]] - 1) * (C[A[i]] - 2)) >> 1
        m = (C[A[i]] * (C[A[i]] - 1)) >> 1
        print(b - m + p)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def comb(n, k, MOD = 10 ** 9 + 7):
    if n < k:
        return 0
    if n - k < k:
        k = n - k
    comb = 1
    for x in range(n - k + 1, n + 1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k + 1):
        d = (d * x) % MOD
    comb *= pow(d, MOD - 2, MOD)
    return comb % MOD

def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1


    for i in range(N):
        C[A[i]] -= 1
        ans = 0
        for cnt in C:
            ans += comb(cnt, 2)
        C[A[i]] += 1
        print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1

    b = 0
    
    for cnt in C:
        b += ((cnt * (cnt - 1)) // 2)

    for i in range(N):
        p = ((C[A[i]] - 1) * (C[A[i]] - 2)) >> 1
        m = (C[A[i]] * (C[A[i]] - 1)) >> 1
        print(b - m + p)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
    a, b, c = map(int, input().split())
    print('Yes' if 4 * a * b <= (c - a - b) ** 2 else 'No')

Fixed submission:
a, b, c = map(int, input().split())
if a + b < c and 4 * a* b < (c - a- b) ** 2:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
S = [c for c in input()]
N = int(input())
r = 0

for i in range(N):
	values = input().split()
	if values[0] == '1':
		r ^= 1
	else:
		f = int(values[1]) - 1
		if f == r:
			S.insert(0, values[2])
		else:
			S.append(values[2])

if r == 0:
	print(''.join(S))
else:
	print(''.join(S)[::-1])






Fixed submission:
S = [c for c in input()]
N = int(input())
r = 0

B = []

for i in range(N):
	values = input().split()
	if values[0] == '1':
		r ^= 1
	else:
		f = int(values[1]) - 1
		if f == r:
			B.append(values[2])
		else:
			S.append(values[2])

if r == 0:
	print(''.join(B[::-1] + S))
else:
	print(''.join(S[::-1] + B))
Buggy python submission (verdict: Runtime Error):
A = [[int(j) for j in input().split()] for i in range(3)]
N = int(input())
B = [False] * 100

for i in range(N):
    B[int(input())] = True

ans = 'No'
for i in range(3):
    if all([B[v] for v in A[i]]):
        ans = 'Yes'
        break

for j in range(3):
    if all([B[A[i][j]] for i in range(3)]):
        ans = 'Yes'
        break

if B[A[0][0]] == B[A[1][1]] == B[A[2][2]] == True:
    ans = 'Yes'

if B[A[2][0]] == B[A[1][1]] == B[A[0][2]] == True:
    ans = 'Yes'

print(ans)



Fixed submission:
A = [[int(j) for j in input().split()] for i in range(3)]
N = int(input())
B = [False] * 101

for i in range(N):
    B[int(input())] = True

ans = 'No'
for i in range(3):
    if all([B[v] for v in A[i]]):
        ans = 'Yes'
        break

for j in range(3):
    if all([B[A[i][j]] for i in range(3)]):
        ans = 'Yes'
        break

if B[A[0][0]] == B[A[1][1]] == B[A[2][2]] == True:
    ans = 'Yes'

if B[A[2][0]] == B[A[1][1]] == B[A[0][2]] == True:
    ans = 'Yes'

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

S = [0] * M
C = [0] * M

for i in range(M):
    S[i], C[i] = input().split()

ans = -1
for i in range(10 * (N - 1) + 1, 10 * N):
    for s, c in zip(S, C):
        if not str(i)[int(s) - 1] == c:
            break
    else:
        ans = i
        break
    if not ans == -1:
        break


Fixed submission:
N, M = map(int, input().split())

K = [0, -1, -1, -1]
ans = -1
for i in range(M):
    s, c = map(int, input().split())
    if not N == 1 and s == 1 and c == 0:
        break
    if K[s] >= 0 and not K[s] == c:
        break
    K[s] = c
else:
    if K[1] == -1 and N >= 2:
        K[1] = 1
    if K[1] == -1 and N == 1:
        K[1] = 0
    if K[2] == -1:
        K[2] = 0
    if K[3] == -1:
        K[3] = 0

    ans = ''.join(map(str, K[1:N + 1]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
ans = 0
v = n
w = n - 1
memo = [0] * (10 ** 5 + 1)
memo[0] = 1
memo[1] = v * w

ans = 1 + v * w
mod = 10 ** 9 + 7
for i in range(2, min(n,k) + 1):
    v = (v * (n - i + 1)) // i
    w = (w * (n - i)) // i
    ans += v * w
    ans %= mod

print(ans)

Fixed submission:
def comb(n, k, MOD):
    if n < k:
        return 0
    if n - k < k:
        k = n - k
    comb = 1
    for x in range(n - k + 1, n + 1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k + 1):
        d = (d * x) % MOD
    comb *= pow(d, MOD - 2, MOD)
    return comb % MOD

n, k = map(int, input().split())
ans = 0
v = n
w = n - 1

ans = 1 + v * w
mod = 10 ** 9 + 7

for i in range(2, min(n,k) + 1):
    #print(f'v={v} n={n} i={i}')
    v = ((n - i + 1) * v)  * pow(i, mod - 2, mod)
    v %= mod
    w = ((n - i) * w) * pow(i, mod - 2, mod)
    w %= mod
    #print(v, w)
    ans += (v * w) % mod
    ans %= mod



print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H = int(input())
n = 1
while True:
    n += 1
    H = H // 2
    if H == 1:
        break

print(2 ** n - 1)

Fixed submission:
import  math
H = int(input())
k = int(math.log2(H))
print(2 ** (k + 1) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
inf = 10 ** 9
dp = [inf for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])


Fixed submission:
H, N = map(int, input().split())
inf = 10 ** 9
dp = [inf for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
g = math.gcd(A, B)
print(A * B // g)

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


A, B = map(int, input().split())
g = gcd(A, B)

print(A * B // g)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

dic = {}
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if not (S[i],S[j],S[k]) in dic:
                dic[(S[i],S[j],S[k])] = 1

print(len(dic))


Fixed submission:
N = int(input())
S = [int(i) for i in input()]
ans = 0
for i in range(10):
    fp = -1
    for tf in range(N - 2):
        if S[tf] == i:
            fp = tf
            break
    if fp == -1:
        continue

    for j in range(10):
        sp = -1
        for ts in range(fp + 1, N - 1):
            if S[ts] == j:
                sp = ts
                break
        if sp == -1:
            continue

        for k in range(10):
            for tt in range(sp + 1, N):
                if S[tt] == k:

                    ans += 1
                    break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import  deque

N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]
ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1]))
dicans = {}
while len(q) > 0:
    i, l = q.popleft()
    num = 1
    #print(f'頂点{i}に関しての色使い情報{Used[i]}')
    for t in range(ans1 + 1):
        if num in Used[i]:
            num += 1
        else:
            break

    for k in l:
        if k < i:
            continue
        #print(f'頂点{i}から{k}に色{num}を割り当て')
        Used[i].append(num)
        Used[k].append(num)
        dicans[(i, k)] = num
        while True:
            if num in Used[i]:
                num += 1
            else:
                break
        q.append((k, dic[k]))
print(ans1)
for a, b in A:
    print(dicans[(a, b)])


Fixed submission:
from collections import  deque
import time
N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]

ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1], 1))
dicans = {}

while len(q) > 0:
    i, l, c= q.popleft()
    num = c
    for k in l:
        if k < i:
            continue
        num += 1
        if num > ans1:
            num = 1
        dicans[(i, k)] = num
        q.append((k, dic[k], num))

print(ans1)

for a, b in A:
    print(dicans[(a, b)])