Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

Solution code:
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()
print(l)
print(*ret, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1<<32|i)
    g[b-1].append(a-1<<32|i)
    # g[a-1].append((b-1, i))
    # g[b-1].append((a-1, i))


def dfs(cur, pre, prec, g, colors):
    gen = 1
    for e in g[cur]:
        if e>>32 != pre:
            if gen == prec:
                gen += 1
            colors[e&(1<<32)-1] = gen
            dfs(e>>32, cur, gen, g, colors)
            gen += 1

colors = [0] * (n-1)
dfs(0, -1, 0, g, colors)

print(max(colors))
for v in colors:
    print(v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
d = [0]*N
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    d[a-1]+=1
    d[b-1]+=1
    G[a-1].append((i, b-1))
    G[b-1].append((i, a-1))
K = max(d)
ans = [0]*(N-1)
def dfs(v, p, c):
    if G[v] == [p]:
        return 
    nc = 1
    for i, nv in G[v]:
        if nv == p:
            continue
        if nc == c:
            nc+=1
        ans[i] = nc
        dfs(nv, v, nc)
        nc+=1
    return
dfs(0, -1, -1)
print(K)
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

E = [[] for _ in [0]*N]
for i,ab in enumerate(AB):
    a,b = ab
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))

done = [False]*N
done[0] = True
ans = [0]*(N-1)
q = [(0,0)]
while q:
    i,c0 = q.pop()
    c = 1
    for j,ei in E[i]:
        if done[j]:continue
        done[j] = True
        if c==c0: c+=1
        q.append((j,c))
        ans[ei] = c
        c += 1

print(max(ans))
for out in ans:
    print(out)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = defaultdict(lambda : -1)
def solve():
    global d
    def dfs(x,pre,k,m):
        global d
        p = 1
        if pre != -1:
            if x < pre:
                d[(x,pre)] = k
            else:
                d[(pre,x)] = k
        for y in v[x]:
            if p == k:
                p += 1
            if m[y]:continue
            m[y] = 1
            dfs(y,x,p,m)
            p += 1
    n = I()
    v = [[] for i in range(n)]
    e = []
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        e.append((a,b))
        f[a] += 1
        f[b] += 1
    if n == 2:
        print(1)
        print(1)
        return
    m = [0]*n
    m[0] = 1
    dfs(0,-1,0,m)
    print(max(f))
    for x,y in e:
        print(d[(x,y)])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


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

tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
ans = 0
for i in range(n):
    ans = max(ans, len(tree[i]))

memo = {}
for i in range(n-1):
    tmp = tuple(sorted(info[i]))
    memo[tmp] = i

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

q = deque([0])
while q:
    pos = q.pop()
    li = []
    position = []
    used = set([])
    for next_pos in tree[pos]:
        tmp = tuple(sorted([next_pos+1, pos+1]))
        if edge[memo[tmp]] == -1:
            li.append(tmp)
            position.append(next_pos)
        else:
            used.add(edge[memo[tuple(sorted([next_pos+1, pos+1]))]])
    cnt = 1
    for i in li:
        while True:
            if cnt not in used:
                edge[memo[i]] = cnt
                cnt += 1
                break
            else:
                cnt += 1
    for i in position:
        q.append(i)

print(ans)
for i in edge:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

def dfs(node, parent):
    used = {col[(node, parent)]}
    curcol = 1
    for n in edges[node]:
        if n == parent: continue

        while curcol in used: curcol += 1

        col[(node, n)] = curcol
        col[(n, node)] = curcol

        dfs(n, node)

        used.add(curcol)
        
col = {}
start = max(range(1, N+1), key = lambda x : len(edges[x]))

for i, n in enumerate(edges[start]):
    col[(start, n)] = i + 1
    col[(n, start)] = i + 1
    dfs(n, start)



done = set()
print(len(edges[start]))
for e in alledges:
    print(col[e])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

answer = []
append = answer.append
for a,b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])

K = max(answer)
print(K)
print('\n'.join(map(str,answer)))

Submission status: Accepted

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


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

ans = [None]*(n-1)
def rec(cur,color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys

n = int(input())
links = [set() for _ in range(n)]
for i, line in enumerate(sys.stdin):
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add((i, b))
    links[b].add((i, a))

ans = [-1] * (n - 1)
k = max(map(len, links))
q = [(0, -1)]
fixed = set()

while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for i, u in links[v]:
        if ans[i] != -1:
            continue
        ans[i] = color
        q.append((u, color))
        color += 1
        if c == color:
            color += 1

print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
idx = {}
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    idx[(a, b)] = i
    idx[(b, a)] = i

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

stack = [(0, -1)]
seen = [False] * N
while stack:
    v, color = stack.pop()
    seen[v] = True
    c = 0
    for u in graph[v]:
        if seen[u]:
            continue
        c += 1
        if c == color:
            c += 1
        ans[idx[(v, u)]] = c
        stack.append((u, c))
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n = int(input())
E = [[] for _ in range(n)]
C = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int, input().split())
    E[a-1].append([b-1, i])
    E[b-1].append([a-1, i])
c = 1
def dfs(cur, pre, pre_c):
    c = 1
    for e, i in E[cur]:
        if e != pre:
            if c == pre_c:
                c += 1
            C[i] = c
            dfs(e, cur, c)
            c += 1

dfs(0, -1, 0)
print(max(C))
for item in C:
    print(item)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline

N = int(input())
adj = [[] for _ in range(N+1)]
edge = {}
for i in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
    edge[(a, b)] = i
    edge[(b, a)] = i

que = deque()
que.append(1)
seen = [-1] * (N+1)
seen[1] = 0
ans = [0] * (N-1)
while que:
    v = que.pop()
    j = 1
    for u in adj[v]:
        if seen[u] < 0:
            if j == seen[v]:
                j += 1
            seen[u] = j
            ans[edge[(u, v)]] = j
            que.appendleft(u)
            j += 1

print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = defaultdict(set)
ABs = []
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1, b-1
    ABs.append((a,b))
    lines[a].add(b)
    lines[b].add(a)


K = -1
ki = -1
for i in range(N):
    if K < len(lines[i]):
        K = len(lines[i])
        ki = i



colors = [defaultdict(int) for _ in range(N)]

def dfs(s,bs,bk):
    cnt = 0
    for t in lines[s]:
        if t == bs:
            continue
        else:
            if cnt == bk:
                cnt += 1
            colors[s][t] = cnt
            colors[t][s] = cnt
            dfs(t,s,cnt)
            cnt += 1


for i,t in enumerate(lines[ki]):
    colors[ki][t] = i
    colors[t][ki] = i
    dfs(t,ki,i)

print(K)
for a,b in ABs:
    print(colors[a][b]+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge = dd(list)
for i in range(n-1):
    a, b = map(int, input().split())
    edge[i] = [a, b]
    tree[a].add(b)
    tree[b].add(a)

color_record = [0] * (n - 1)
color_num = max([len(val) for val in tree.values()])
print(color_num)
colors = set(list(range(1, color_num+1)))

node_color = dd(set)
for i in range(n-1):
    node1, node2 = edge[i]
    color = colors - node_color[node1] - node_color[node2]
    color = list(color)[0]
    node_color[node1].add(color)
    node_color[node2].add(color)
    color_record[i] = color

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


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


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def dfs(u, p, c, color, tree):
    color[(u, p)] = c
    color[(p, u)] = c

    now = 0
    for v in tree[u]:
        if v == p:
            continue
        if now == c:
            now += 1

        dfs(v, u, now, color, tree)
        now += 1


def solve():
    N = int(input())

    tree = [[] for _ in range(N)]
    edges = []
    for _ in range(N - 1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        tree[A].append(B)
        tree[B].append(A)
        edges.append((A, B))

    color = dict()
    dfs(0, -1, -1, color, tree)

    print(max(color.values()) + 1)
    for e in edges:
        print(color[e] + 1)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
t = [list(map(int, input().split())) for _ in range(n-1)]



hands = [0 for _ in range(n+1)]
for a, b in t:
    hands[a] += 1
    hands[b] += 1

number_of_colors = max(*hands)

def next_color(i):
    return i+1 if i < number_of_colors else 1



class edge():
    def __init__(self, en):
        self.ends = en
        self.color = 0

    def set_color(self, co):
        self.color = co

class nord():
    def __init__(self, tr):
        self.parent = tr
        self.edges = []

    def add(self, ed):
        self.edges.append(ed)

    def set_color(self, previous_color):
        co = next_color(previous_color)
        for ed in self.edges:
            if ed.color == 0:
                ed.set_color(co)
                for i in ed.ends:
                    no = self.parent.nords[i-1]
                    if self is not no:
                        no.set_color(co)
                co = next_color(co)

class tree():
    def __init__(self):
        self.nords = []

    def add_nord(self, no):
        self.nords.append(no)

    def add_edge(self, ed):
        for i in ed.ends:
            self.nords[i-1].add(ed)

    def set_color(self):
        self.nords[0].set_color(0)


tr = tree()
for _ in range(n):
    no = nord(tr)
    tr.add_nord(no)

e_tree = []
for en in t:
    ed = edge(en)
    e_tree.append(ed)
    tr.add_edge(ed)

tr.set_color()

print(number_of_colors)
for e in e_tree:
    print(e.color)

Submission status: Runtime Error

Solution code:
from collections import OrderedDict
# import matplotlib.pyplot as plt
# import networkx as nx

def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


def show_tree(tree, edge_labels):
    graph = nx.Graph()
    labels = {}
    for i, s in enumerate(tree):
        for d in s:
            # graph.node(str(s))
            # graph.node(str(d))
            graph.add_edge(i, d)
            labels[(i, d)] = edge_labels[get_key(i, d)]

    pos = nx.spring_layout(graph)
    # print(graph)
    nx.draw_networkx(graph, pos=pos)
    nx.draw_networkx_edge_labels(graph, pos, labels)
    # nx.draw_networkx_edge_labels(graph, pos)
    plt.show()



N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

ans = OrderedDict()
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()

    ans[get_key(in1, in2)] = 0


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [edge_colors[k] for k in ans.keys()]

print(max(ans))
[print(a) for a in ans]

# [print(k, v) for k, v in edge_colors.items()]

# show_tree(tree, edge_colors)

Submission status: Runtime Error

Solution code:
from collections import OrderedDict
import matplotlib.pyplot as plt
import networkx as nx

def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


def show_tree(tree, edge_labels):
    graph = nx.Graph()
    labels = {}
    for i, s in enumerate(tree):
        for d in s:
            # graph.node(str(s))
            # graph.node(str(d))
            graph.add_edge(i, d)
            labels[(i, d)] = edge_labels[get_key(i, d)]

    pos = nx.spring_layout(graph)
    # print(graph)
    nx.draw_networkx(graph, pos=pos)
    nx.draw_networkx_edge_labels(graph, pos, labels)
    # nx.draw_networkx_edge_labels(graph, pos)
    plt.show()



N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

ans = OrderedDict()
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()

    ans[get_key(in1, in2)] = 0


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [edge_colors[k] for k in ans.keys()]

print(max(ans))
[print(a) for a in ans]

# [print(k, v) for k, v in edge_colors.items()]

# show_tree(tree, edge_colors)

Submission status: Runtime Error

Solution code:
from collections import OrderedDict


def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [i for k, i in edge_colors.items()]
print(max(ans))
[print(a) for a in ans]

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    global visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    global color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print("\n".join(map(str, color_list)))

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<vector<int>> G(n);
    vector<pair<int,int>> vp;
    for (int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
        vp.emplace_back(a,b);
    }

    int k=0;
    vector<int> c(n,0);
    map<pair<int,int>,int> i;
    queue<int> que;
    vector<int> seen(n,0);
    seen[0]=1;
    que.push(0);

    while(!que.empty()){
        int v=que.front();
        que.pop();
        k=max(k,(int)G[v].size());
        int col=1;
        for (int nv:G[v]){
            if (seen[nv]==1) continue;
            if (col==c[v]) col++;
            c[nv]=i[make_pair(v,nv)]=i[make_pair(nv,v)]=col;
            col++;
            seen[nv]=1;
            que.push(nv);
        }
    }
    cout<<k<<endl;
    for (auto p:vp) cout<<i[p]<<endl;
    return 0;

}

Submission status: Runtime Error

Solution code:
N = int(input())

class vertex:
  def __init__(self,i):
    self.__i = i
    self.__e = []
    self.__d = 0
    self.__nei = []
  def add_e(self, e):
    self.__e.append(e)
    self.__d += 1
    self.__nei.append(e.get_pair_v(self.__i))
  def get_e(self):
    return self.__e
  def get_d(self):
    return self.__d
  def get_i(self):
    return self.__i
  def get_n(self):
    return self.__nei
  
class edge:
  def __init__(self, i, a, b):
    self.__i = i
    self.__c = -1
    self.__v = dict()
    self.__v[a] = b
    self.__v[b] = a
  def get_pair_v(self, a):
    return self.__v[a]
  def get_c(self):
    return self.__c
  def set_c(self, a):
    if self.__c == -1:
      self.__c = a
      return True
    else:
      return False
  def get_i(self):
    return self.__i
    
class tree:
  def __init__(self,N):
    self.__v = [vertex(i) for i in range(N+1)]
    self.__e = []
    self.__max_d = 0
    self.__max_v_idx = 0
    
  def add_e(self,i, a, b):
    ed = edge(i, a, b)
    self.__e.append(ed) 
    self.__v[a].add_e(ed)
    self.__v[b].add_e(ed)
  
  def reload_max_d(self):
    for i in self.__v:
      if i.get_d() > self.__max_d:
        self.__max_d = i.get_d()
        self.__max_v_idx = i.get_i()
        
  def painting(self):
    v = self.__max_v_idx
    edges = self.__v[v].get_e()
    for i, ver in enumerate(edges):
      ver.set_c(i+1)
      self.change_c(ver.get_pair_v(v),ver)   
    
  def change_c(self, idx, prev_e):
    edges = self.__v[idx].get_e()
    edges.remove(prev_e)
    offset = 0
    prev_e_c = prev_e.get_c()
    if not edges:
      return
    for ver in edges:
      offset += 1
      if offset == prev_e_c:
        offset += 1
      if ver.set_c(offset):
        self.change_c(ver.get_pair_v(idx),ver)   
  
  def show_max_d(self):
    print(self.__max_d)
    
  def show_colors(self):
    for i in self.__e:
      print(i.get_c()) 

t = tree(N)
for i in range(N-1):
  temp = list(map(int, input().split()))
  t.add_e(i, temp[0], temp[1])
t.reload_max_d()
t.painting()
t.show_max_d()
t.show_colors()

Submission status: Runtime Error

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

color = [None]*(N-1)
SIZE = 1
def dfs(i, prev):
    global SIZE
    colors = list(range(1, SIZE+1))
    if prev:
        colors.remove(prev)
    for j, n in edges[i]:
        if not color[n]:
            if not colors:
                SIZE += 1
                color[n] = SIZE
            else:
                color[n] = colors.pop()
            dfs(j, color[n])
dfs(0, None)
print(SIZE)
for n in range(N-1):
    print(color[n])

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([b,i])
        edge[b].append([a,i])
    color = [0] * (N-1)
    def dfs(s,p,c):
        tmp_c = 1
        for v, num in edge[s]:
            if v == p:
                continue
            if tmp_c == c:
                tmp_c += 1
            color[num] = tmp_c
            dfs(v,s,tmp_c)
            tmp_c += 1
    dfs(0,-1,0)
    print(max(color))
    for c in color:
        print(c)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    edge = [-1] * (N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append((b, i))
        G[b].append((a, i))

    max_deg = max(len(G[i]) for i in range(N))

    def dfs(s, c=-1, p=-1):
        # 行きがけ順処理
        cur_color = 1
        for (v, i) in G[s]:
            if v == p:
                continue
            if c == cur_color:
                cur_color += 1
            edge[i] = cur_color
            dfs(v, edge[i], s)
            cur_color += 1
        # 帰りがけ順処理

    dfs(0)

    print(max_deg)
    for i in range(N-1):
        print(edge[i])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = []

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

def dfs(prev, now):
    if visited[now]:
        return
    visited[now] = 1
    numOfEdges[now] = len(graph[now])
    for adj in graph[now]:
        if adj == prev:
            continue
        dfs(now, adj)

dfs(-1, 0)
maxColor = max(numOfEdges)
print(maxColor)

for e in edges:
    a, b = e
    x, y = numOfEdges[a], numOfEdges[b]

    print(max(x, y))

    if x > y:
        numOfEdges[a] -= 1
    elif y > x:
        numOfEdges[b] -= 1
    else:
        numOfEdges[a] -= 1
        numOfEdges[b] -= 1

Submission status: Runtime Error

Solution code:
n=int(input())
ans_list=[[0]*(n+1) for i in range(n+1)]
kotaezyun=[]
renketu=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int, input().split())
    renketu[a].append(b)
    kotaezyun.append([a,b])

from collections import deque
que=deque()

que.append(1)

iro=[-1]*(n+1)
iro[1]=0
irokazu=0

tansaku_moto=[1]

while que:
    tansaku_moto=que.popleft()
    ironuri=1
    for tansaku_saki in renketu[tansaku_moto]:
        if ironuri==iro[tansaku_moto]:
            ironuri+=1
        ans_list[tansaku_moto][tansaku_saki]=ironuri
        iro[tansaku_saki]=ironuri
        que.append(tansaku_saki)
        irokazu=max(irokazu,ironuri)
        ironuri+=1
        
print(irokazu)
for i in range(n-1):
    print(ans_list[kotaezyun[i][0]][kotaezyun[i][1]])