Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

dp = np.array([[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)], dtype=np.int64)
dp[0][0][0] = 1

for i, e in enumerate(a):
    dp[i+1, :, 0] += dp[i, :, 0]
    dp[i+1, :, 1] += dp[i, :, 0] + dp[i, :, 1]
    dp[i+1, :, 2] += dp[i, :, 0] + dp[i, :, 1] + dp[i, :, 2]

    dp[i+1, e:, 1] += dp[i, :-e, 0] + dp[i, :-e, 1]
    dp[i+1, e:, 2] += dp[i, :-e, 0] + dp[i, :-e, 1]

    dp[i+1, :, :] %= mod

ans = dp[n][s][2]
print(ans)


Fixed submission:
import numpy as np

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

dp = np.array([[0] * 3 for _ in range(s + 1)], dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()
    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = [[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for i, e in enumerate(a):
    for j in range(s + 1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if j + e <= s:
            dp[i+1][j+e][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+e][2] += dp[i][j][0] + dp[i][j][1]

        for k in range(3):
            dp[i+1][j][k] %= mod

ans = dp[n][s][2]
print(ans)


Fixed submission:
import numpy as np

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

dp = np.array([[0] * 3 for _ in range(s + 1)], dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()
    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1

        self.colors[u] = self.BLACK


tree = Tree(adj)
tree.dfs(0)

ev = [i for i, e in enumerate(tree.depths) if e % 2 == 0]
od = [i for i, e in enumerate(tree.depths) if e % 2]

l_ev = len(ev)
l_od = len(od)

mod0 = [e for e in range(1, n + 1) if e % 3 == 0]
mod1 = [e for e in range(1, n + 1) if e % 3 == 1]
mod2 = [e for e in range(1, n + 1) if e % 3 == 2]

ans = [0] * n


def f(li1, li2):
    while li1 and li2:
        i = li1.pop()
        num = li2.pop()
        ans[i] = num


if l_ev > n / 3 and l_od > n / 3:
    f(ev, mod1)
    f(od, mod2)
    f(ev, mod0)
    f(od, mod0)

elif l_ev <= n / 3:
    f(ev, mod0)
    f(od, mod0)
    f(od, mod1)
    f(od, mod2)

else:
    f(od, mod0)
    f(ev, mod0)
    f(ev, mod1)
    f(ev, mod2)

print(*ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1

        self.colors[u] = self.BLACK


tree = Tree(adj)
tree.dfs(0)

ev = [i for i, e in enumerate(tree.depths) if e % 2 == 0]
od = [i for i, e in enumerate(tree.depths) if e % 2]

l_ev = len(ev)
l_od = len(od)

mod0 = [e for e in range(1, n + 1) if e % 3 == 0]
mod1 = [e for e in range(1, n + 1) if e % 3 == 1]
mod2 = [e for e in range(1, n + 1) if e % 3 == 2]

ans = [0] * n


def f(li1, li2):
    while li1 and li2:
        i = li1.pop()
        num = li2.pop()
        ans[i] = num


if l_ev > n / 3 and l_od > n / 3:
    f(ev, mod1)
    f(od, mod2)
    f(ev, mod0)
    f(od, mod0)

elif l_ev <= n / 3:
    f(ev, mod0)
    f(od, mod0)
    f(od, mod1)
    f(od, mod2)

else:
    f(od, mod0)
    f(ev, mod0)
    f(ev, mod1)
    f(ev, mod2)

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

rev = 0
for _ in range(q):
    que = input()
    if que[0] == "1":
        rev ^= 1

    else:
        t, f, c = que.split()
        if rev:
            if f == "1":
                s = s + c
            else:
                s = c + s

        else:
            if f == "1":
                s = c + s
            else:
                s = s + c

if rev:
    print(s[::-1])
else:
    print(s)


Fixed submission:
from collections import deque

s = input()
q = int(input())

s = deque(s)

rev = 0
for _ in range(q):
    que = input()
    if que[0] == "1":
        rev ^= 1

    else:
        t, f, c = que.split()
        if rev:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)

        else:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)

s = list(s)
if rev:
    print(*s[::-1], sep="")
else:
    print(*s, sep="")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

if p == 2 or p == 5:
    ans = 0
    for i, e in enumerate(s, 1):
        if int(e) % p == 0:
            ans += i

    print(ans)

else:
    li = [0]
    for i, e in enumerate(s[::-1], 1):
        li.append((li[-1] + int(e) * 10 ** i) % p)

    c = Counter(li)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2

    print(ans)


Fixed submission:
from collections import Counter

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

if p == 2 or p == 5:
    ans = 0
    for i, e in enumerate(s, 1):
        if int(e) % p == 0:
            ans += i

    print(ans)

else:
    li = [0]
    for i, e in enumerate(s[::-1], 1):
        li.append((li[-1] + int(e) * pow(10, i, p)) % p)

    c = Counter(li)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

from collections import Counter

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

g = [[0] * n for _ in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    g[a][b] = 1
    g[b][a] = 1

csr = csr_matrix(g)
comp, labels = connected_components(csr)

counter = Counter(labels)

ans = [counter[labels[i]] - 1 for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    c -= 1
    d -= 1
    if labels[c] == labels[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)


class Tree:
    WHITE = -2
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u, c):
        if self.colors[u] >= 0:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.dfs(v, c)

        self.colors[u] = c

from collections import Counter

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

tree = Tree(adj)
for i in range(n):
    tree.dfs(i, i)

labels = tree.colors

counter = Counter(labels)

ans = [counter[labels[i]] - 1 for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    c -= 1
    d -= 1
    if labels[c] == labels[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        if x < 10:
            dp[i+1][0] = min(dp[i+1][0], dp[i][j] + x)
        dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 10 - x)

ans = dp[l][0]
print(ans)


Fixed submission:
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10

            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

ans = dp[l][0]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10

            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

ans = dp[l][0]
print(ans)


Fixed submission:
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10

            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

ans = dp[l][0]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


r1, c1, r2, c2 = map(int, input().split())

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
print(ans)


Fixed submission:
def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


r1, c1, r2, c2 = map(int, input().split())

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    for j in range(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)


Fixed submission:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    for j in range(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
m = int(input())
uv = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
ids = [[-1] * n for _ in range(n)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    ids[a][b] = i
    ids[b][a] = i


def dfs(s, g):
    d = [-1] * n
    d[s] = 0
    p = [-1] * n
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    v = g
    ret = 0
    while v != s:
        i = ids[v][p[v]]
        ret += 1 << i
        v = p[v]

    return ret


path = [dfs(u - 1, v - 1) for u, v in uv]
ans = 0
for tpl in product([1, 0], repeat=m):
    coef = 1
    cnt = 0
    for bl, e in zip(tpl, path):
        if bl:
            cnt |= e
            coef *= -1
    ans += pow(2, n - 1 - bin(cnt).count("1")) * coef

print(ans)


Fixed submission:
from itertools import combinations

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
m = int(input())
uv = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
ids = [[-1] * n for _ in range(n)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    ids[a][b] = i
    ids[b][a] = i


def dfs(s, g):
    d = [-1] * n
    d[s] = 0
    p = [-1] * n
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    v = g
    ret = 0
    while v != s:
        i = ids[v][p[v]]
        ret += 1 << i
        v = p[v]

    return ret


def bin_count(tpl):
    sm_or = 0
    for e in tpl:
        sm_or |= e

    return bin(sm_or).count("1")


path = [dfs(u - 1, v - 1) for u, v in uv]
ex = 0
for i in range(1, m + 1):
    for tpl in combinations(path, i):
        ex += pow(2, n - 1 - bin_count(tpl)) * (-1) ** (i % 2 + 1)

ans = pow(2, n - 1) - ex
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt, floor

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


def cnt_div2(x):
    ret = 0
    while x % 2 == 0:
        x //= 2
        ret += 1

    return ret, x


def e_sieve(x):
    li = list(range(2, x + 1))
    primes = []
    while li[0] <= floor(sqrt(x)):
        prime = li[0]
        primes.append(prime)
        li = [e for e in li if e % prime != 0]

    primes += li

    return primes


cnt, _ = cnt_div2(a[0])
for e in a:
    if cnt_div2(e)[0] != cnt:
        print(0)
        exit()

for i, e in enumerate(a):
    a[i] //= 2 ** cnt

primes = e_sieve(max(a))
primes.pop(0)

fact_cnt = [0] * len(primes)

for e in a:
    for i, p in enumerate(primes):
        cnt = 0
        while e % p == 0:
            e //= p
            cnt += 1
        fact_cnt[i] = max(fact_cnt[i], cnt)

lcm = 1
for p, f in zip(primes, fact_cnt):
    lcm *= p ** f

ans = (m // lcm + 1) // 2
print(ans)


Fixed submission:
from fractions import gcd


def cnt_div2(x):
    ret = 0
    while x % 2 == 0:
        ret += 1
        x //= 2

    return ret


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

aa = [e // 2 for e in a]

cnt = cnt_div2(aa[0])
for e in aa:
    if cnt_div2(e) != cnt:
        print(0)
        exit()


def lcm(x, y):
    return x // gcd(x, y) * y


c = 1
for e in aa:
    c = lcm(c, e)

ans = m // c
print((ans + 1) // 2)
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
from collections import Counter
from math import ceil

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

a.sort(reverse=True)
acm = list(accumulate(a))
c = Counter(a)
c = list(c.values())
#print(c)
always_ok = a[p-1]
cnt = 0
j = 0
prev = -1

for i, e in enumerate(a):
    if e != prev:
        cnt += c[j]
        j += 1
        prev = e
    if e >= always_ok:
        continue

    if n - i + p - 1 >= v:
        if e + m >= always_ok:
            continue
        else:
            #print(i, e, "break")
            break

    cnt -= c[j-1]
    #print(i, e)
    left = v - (n - i + p - 1)
    #print(left)
    sm = acm[i-1] - acm[cnt-1]
    #print(sm)
    mx = max(a[p-1], ceil((sm + left * m) / (i - cnt + 1)))
    #print(mx)
    cnt += c[j-1]
    if mx > e + m:
        break

cnt = 0
for ae in a:
    if ae == e:
        break
    cnt += 1

print(cnt)


Fixed submission:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)


def can_be_used(x):
    # x: 0-index
    if x < p:
        return True

    if a[x] + m < a[p-1]:
        return False

    vote_max = (p - 1 + n - x) * m
    for i in range(p-1, x):
        vote_max += a[x] + m - a[i]

    if vote_max < m * v:
        return False

    return True


l = 0
r = n

while r - l > 1:
    mid = (l + r) // 2

    if can_be_used(mid):
        l = mid
    else:
        r = mid

ans = l + 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
MAX = 60

acc = [0] * MAX
ans = [0] * MAX

num = a[0]
for i in range(MAX):
    if num & 1:
        acc[i] = 1
    num >>= 1

for i, e in enumerate(a[1:], 1):
    for j in range(MAX):
        if e & 1:
            ans[j] += i - acc[j]
            acc[j] += 1
        else:
            ans[j] += acc[j]

        e >>= 1

ans_num = 0
for i, e in enumerate(ans):
    ans_num += pow(2, i, mod) * e
    ans_num %= mod

print(ans_num)


Fixed submission:
import numpy as np

MOD = 10 ** 9 + 7

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

ans = 0
for n in range(62):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    mul = x * y
    for _ in range(n):
        mul *= 2
        mul %= MOD
    ans += mul

ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

n = int(input())
s = input()

nums = [str(i) for i in range(10)]

ans = 0
for pat in product(nums, repeat=3):
    i = 0
    for e in s:
        if e == pat[i]:
            i += 1

        if i == 3:
            break

    if i == 3:
        ans += 1

print(ans)


Fixed submission:
from itertools import product

n = int(input())
s = input()
nums = [str(i) for i in range(10)]

cnt = 0
for num in product(nums, repeat=3):
    i = 0
    for e in s:
        if num[i] == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

n = int(input())
s = input()

cnt = 0
for num in product(range(10), repeat=3):
    i = 0
    for e in s:
        if str(num[i]) == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

print(cnt)


Fixed submission:
from itertools import product

n = int(input())
s = input()
nums = [str(i) for i in range(10)]

cnt = 0
for num in product(nums, repeat=3):
    i = 0
    for e in s:
        if num[i] == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict, deque

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = defaultdict(list)
for i, (a, b) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))

k = max([len(li) for li in adj.values()])
print(k)

ans = [-1] * (n - 1)

def dfs(u, p_col):
	col = 1
	for v, i in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1


dfs(0, -1)

print(*ans, sep="\n")


Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = defaultdict(list)
for i, (a, b) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))

k = max([len(li) for li in adj.values()])
print(k)

ans = [-1] * (n - 1)

def dfs(u, p_col):
	col = 1
	for v, i in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1


dfs(0, -1)

print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
m = int(input())
dc = [list(map(int, input().split())) for _ in range(m)]

def zero(n):
    return n - 1, "0"

def one(n):
    ret = 0
    while n // 10:
        q, r = divmod(n, 10)
        n = q + r
        ret += 10 * q
    return ret, "1" * n

def two(n):
    ret = 0
    q, r = divmod(n, 5)
    ret += 5 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "2" * r

def three(n):
    ret = 0
    while n // 4:
        q, r = divmod(n, 4)
        n = q + r
        ret += 4 * q
    return ret, "3" * n

def four(n):
    ret = 0
    q, r = divmod(n, 3)
    ret += 3 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "4" * r

def five(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "5" * r

def six(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "6" * r

def seven(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    five_cnt, fives = five(q)
    ret += five_cnt
    return ret, fives + "7" * r

def eight(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = seven(q)
    ret += one_cnt
    return ret, ones + "8" * r

def nine(n):
    ret = 0
    while n // 2:
        q, r = divmod(n, 2)
        n = q + r
        ret += 2 * q
    return ret, "9" * n

new_dc = []
fs = [zero, one, two, three, four, five, six, seven, eight, nine]
for d, c in dc:
    cnt, s = fs[d](c)
    new_dc.append([cnt, s])

s = ""
cnt = 0
for d, c in new_dc:
    s += c
    cnt += d

while len(s) > 1:
    tmp = int(s[-1]) + int(s[-2])
    s = s[:-2] + str(tmp)
    cnt += 1

print(cnt)


Fixed submission:
m = int(input())
dc = [list(map(int, input().split())) for _ in range(m)]

sm = 0
n = 0
for d, c in dc:
    sm += d * c
    n += c

ans = n - 1 + (sm - 1) // 9
print(ans)