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: Runtime Error

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

ALL = sum(bar_list, [])
c = collections.Counter(ALL)
nodes = [set() for i in range(len(c))]
cols = []
 
K = max(c.values())
print(K)
COLS = set(range(K))
for bar in bar_list:
  used_colors = nodes[bar[0] - 1] | nodes[bar[1] - 1]
  col = list(COLS - used_colors)[0]
  print(col + 1)
  nodes[bar[0] - 1] = nodes[bar[0] - 1] | set([col])
  nodes[bar[1] - 1] = nodes[bar[1] - 1] | set([col])

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N-1)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

paint(tmp[0][0], -1)

print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:

N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            d=1
        mmx = max(mmx, dfs(t, mx, i+d))
        # dfs(t, mx, i)
    return mmx
M = dfs(0, 1, -1)
# print(R)
# print(F)
# print(M)
# for i,f in enumerate(F):
#     print(R[f])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

v_edges = [set() for i in range(N)]

for a, b in ab:
    v_edges[a - 1].add(b - 1)
    v_edges[b - 1].add(a - 1)

# print(v_edges)

n_colors = max([len(e) for e in v_edges])
v_colors = [set() for i in range(N)]
e_colors = [[-1] * (N) for i in range(N - 1)]

print(n_colors)


def DFS(G, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    # print(G, start, visited)

    for u in G[start]:
        if u in visited:
            continue

        for i in range(n_colors):
            if i not in v_colors[u] and i not in v_colors[start]:
                v_colors[u].add(i)
                v_colors[start].add(i)
                e_colors[min(u, start)][max(u, start)] = i
                break
        DFS(G, u, visited)

DFS(v_edges, 0)
# print(e_colors)

for a, b in ab:
    print(e_colors[a - 1][b - 1] + 1)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    #g[b].append(a)

res=[[] for i in range(n)]
#print(g)
fin=[0 for i in range(n)]
def abc(i):
    global res,g
    cnt=1
    for a in g[i]:
        while True:
            if cnt in res[i]:
                cnt+=1
            else:
                break
        res[a].append(cnt)
        res[i].append(cnt)
        fin[a]=cnt
        cnt+=1
        abc(a)
abc(0)
for i in range(1,n):
    print(fin[i])

Submission status: Runtime Error

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(i, prev, t, d, ans):
    if i == 0:
        num = len(t[i])
    else:
        num = len(t[i]) + 1
    x = 1
    if prev == 1:
        x = 2
    for c in t[i]:
        ans[d[i, c]] = x
        num = max(num, solve(c, x, t, d, ans))
        x += 1
        if x == prev:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = np.empty((N, N), i8)
    d.fill(-1)
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        d[a - 1, b - 1] = count
        count += 1
    num = solve(0, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)
        
main()

Submission status: Runtime Error

Solution code:
import collections
import itertools

N = int(input())-1

ab_list = [input().split() for i in range(N)]

counter = collections.Counter(list(itertools.chain.from_iterable(ab_list)))

ans_N = counter.most_common()[0][1]

dct = dict(counter)

new_dct = dict()
for key, value in dct.items():
    new_dct[key] = set(range(ans_N))



def get_element(st):
    for i in st:
        return i


print(ans_N)
for a, b in ab_list:
    remove_color = get_element(new_dct[a] & new_dct[b])
    new_dct[a].remove(remove_color)
    new_dct[b].remove(remove_color)
    print(remove_color + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)


def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color

    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color


print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
AB = []
for _ in range(N-1):
    i = list(map(int, input().split()))
    AB.append((i[0],i[1]))

AB = sorted(AB, key=lambda tup: tup[1])
A = [ab[0] for ab in AB]
B = [ab[1] for ab in AB]
ans = []

for i in range(N-1):
    if not i == 0:
        if A[i] == A[i-1]:
            ans.append(ans[i-1]+1)
        else:
            x = B.index(A[i])
            if ans[x] != 1:
                ans.append(1)
            else:
                ans.append(2)
    else:
        ans.append(1)
    
print(max(ans))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
edge = []
v_edge = [0]*n

for i in range(n-1):
    ai,bi = map(int,input().split())
    edge.append([ai,bi])
    v_edge[ai-1] += 1
    v_edge[bi-1] += 1
    
k = max(v_edge)
print(k)

c_edge = [list(range(1,k+1)) for i in range(n)]

for i in range(len(edge)):
    ai,bi = edge[i]
    c = min(c_edge[ai-1])
    print(c)
    c_edge[ai-1].remove(c)
    c_edge[bi-1].remove(c)

Submission status: Runtime Error

Solution code:

n = int(input())

graph = [[] for i in range(n)]

edges = []
for i in range(n-1):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    #edge = (a, b)
    edge = tuple(sorted([a, b]))
    edges.append(edge)

node_nums = [len(node) for node in graph]
num_color = max(node_nums)
print(num_color)


def coloring(edge_colors, parent_node, cur_node, former_color):
    kid_nodes = graph[cur_node]

    if len(kid_nodes) == 1:
        return edge_colors

    cur_color = 1
    for kid_node in kid_nodes:
        if kid_node == parent_node:
            continue

        if former_color == cur_color:
            cur_color += 1
        edge = tuple(sorted([cur_node, kid_node]))
        edge_colors[edge] = cur_color
        edge_colors = coloring(edge_colors, cur_node, kid_node, cur_color)

        cur_color += 1

    return edge_colors
        

edge_colors = {}
try:
    start_node = node_nums.index(1)
except:
    start_node = 0

kid_nodes = graph[start_node]
#assert len(kid_nodes) == 1
kid_node = kid_nodes[0]
edge = tuple(sorted([start_node, kid_node]))
cur_color = 1
edge_colors[edge] = cur_color
former_color = cur_color

edge_colors = coloring(edge_colors, start_node, kid_node, former_color)

for edge in edges:
    color = edge_colors[edge]
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
l=[[] for i in range(N)]
e=[]
d=[0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    e.append((a,b))
    d[a]=d[a]+1
    d[b]=d[b]+1


K=max(d)
print(K)
last=[set(range(1,K+1)) for i in range(N)]
for a,b in e:
    s=last[a]&last[b]
    n=s.pop()
    print(n)
    last[a].remove(n) 
    last[b].remove(n)

Submission status: Runtime Error

Solution code:
N=int(input());AB=[list(map(int,input().split())) for _ in range(1,N)]
nd=[0 for _ in range(N)]
table = [[] for _ in range(N)]
for a,b in AB:
  table[a-1].append(b)
  nd[a-1]+=1
  nd[b-1]+=1

for _,li in table:
  sort(li)

K=max(nd)
print(K)
co=[0 for _ in range(N)]
for x,li in enumerate(table):
  c=[i for i in range(1,K+1) if i != co[x]]
  for b,y in zip(li,c):
    co[b-1]=y
    print(y)

Submission status: Runtime Error

Solution code:
n=int(input())
node=[[] for _ in range(n)]
c_num=[0 for _ in range(n)]
arr=[]
ans=[0 for _ in range(n-1)]
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    arr.append([a-1,b-1])
    node[a-1].append(b-1)
    node[b-1].append(a-1)
    c_num[a-1]+=1
    c_num[b-1]+=1
c=max(c_num)
c_arr=[[i for i in range(1,c+1)] for _ in range(n)]
print(c)
for i in range(n-1):
    del_num=c_arr[arr[i][0]].pop(0)
    print(del_num)
    ans[i]=del_num
    c_arr[arr[i][1]].remove(del_num)

Submission status: Runtime Error

Solution code:
n = int(input())
tree_i = {}
tree_n = {}
for i in range(n-1):
  a,b = map(int,input().split())
  tree_i[(a,b)] = i
  if a in tree_n:
    tree_n[a].append(b)
  else:
    tree_n[a] = [b]
  if b in tree_n:
    tree_n[b].append(a)
  else:
    tree_n[b] = [a]
max_len = 0
for value in tree_n.values():
  if max_len < len(value):
    max_len = len(value)
print(max_len)
ans = [0 for i in range(n-1)]

def coloring(n_b,n,color_b,tree_i,tree_n):
  nodes = tree_n[n]
  color = 0
  for node in nodes:
    if node ==n_b:
      continue
    if color == color_b:
      color += 1
    a = min(n,node)
    b = max(n,node)
    ans[tree_i[(a,b)]] = color
    coloring(n,node,color,tree_i,tree_n)
    color +=1

coloring(-1,1,-1,tree_i,tree_n)
for i in ans:
  print(i+1)

Submission status: Runtime Error

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[a*N + b] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1]]
cnt = 0
while Q and cnt < N-1:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
        cnt += 1
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Runtime Error

Solution code:
A, B, X = map(int,input().split())
dn = 0
for k in range(28, -1, -1):
    if A*10**(k-1)+B*k <= X:
        dn = k
        break
if dn == 0:
    ans = 0
else:
    ans = min((X-B*dn)//A,10**9)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append([b, i])
  else:
    edges[a] = [[b, i]]
  if b in edges.keys():
    edges[b].append([a, i])
  else:
    edges[b] = [[a, i]]
colors = [0 for i in range(n-1)]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  global edges
  flags[node] = True
  for edge in edges[node]:
    if flags[edge[0]] == False:
      if i != cannot:
        colors[edge[1]] += i
      else:
        i += 1
        colors[edge[1]] += i
      i += 1
      search(edge[0], i-1)
search(n, 0)
print(max(colors))
for i in range(n-1):
  print(colors[i])

Submission status: Runtime Error

Solution code:

n = int(input())

graph = [[] for i in range(n)]

edges = []
for i in range(n-1):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    #edge = (a, b)
    edge = tuple(sorted([a, b]))
    edges.append(edge)

try:
    node_nums = [len(node) for node in graph]
    num_color = max(node_nums)
except:
    num_color = 1
    node_nums = [1]
print(num_color)


def coloring(edge_colors, parent_node, cur_node, former_color):
    kid_nodes = graph[cur_node]

    if len(kid_nodes) == 1:
        return edge_colors

    cur_color = 1
    for kid_node in kid_nodes:
        if kid_node == parent_node:
            continue

        if former_color == cur_color:
            cur_color += 1
        edge = tuple(sorted([cur_node, kid_node]))
        edge_colors[edge] = cur_color
        edge_colors = coloring(edge_colors, cur_node, kid_node, cur_color)

        cur_color += 1

    return edge_colors
        

edge_colors = {}
start_node = node_nums.index(1)
kid_nodes = graph[start_node]
#assert len(kid_nodes) == 1
kid_node = kid_nodes[0]
edge = tuple(sorted([start_node, kid_node]))
cur_color = 1
edge_colors[edge] = cur_color
former_color = cur_color

edge_colors = coloring(edge_colors, start_node, kid_node, former_color)

for edge in edges:
    try:
        color = edge_colors[edge]
    except:
        color = 1
    print(color)

Submission status: Runtime Error

Solution code:

N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            d=1
        mmx = max(mmx,dfs(t, mx, i+d))
        # dfs(t, mx, i)
    return mmx
M = dfs(0, 1, -1)
# print(R)
# print(F)
print(M)
for i,f in enumerate(F):
    print(R[f])

Submission status: Runtime Error

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


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)]


# A
def A():
    s = input()
    if s == 'SUN':
        print(7)
    if s == "MON":
        print(6)
    if s == "TUE":
        print(5)
    if s == "WED":
        print(4)
    if s == "THU":
        print(3)
    if s == "FRI":
        print(2)
    if s == "SAT":
        print(1)
    return


# B
def B():
    al = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
    n = I()
    s = S()
    for i in range(len(s)):
        ni = (al.index(s[i]) + n) % 26
        s[i] = al[ni]
    print(''.join(s))
    return


# C
def C():
    a, b, x = LI()
    l = [a * (10 ** (i - 1)) + b * i for i in range(1, 11)]
    p = 0
    for i in range(10):
        if x < l[i] and i == 0:
            print(0)
            return
        if l[i] <= x and i == 9:
            print(10 ** 9)
            return
        elif l[i] <= x < l[i + 1]:
            p = i + 1
            break
    if (x - b * p) // a >= 10 ** p:
        print(10 ** p - 1)
    else:
        print((x - b * p) // a)
    return


# D
def D():
    n = I()
    ab = [LI() for i in range(n - 1)]
    cnt = [[] for i in range(n + 1)]
    ans = [[0] * (n + 1) for i in range(n + 1)]
    max_c = 1
    for i in range(n - 1):
        cnt[ab[i][0]].append(ab[i][1])

    def rec(ind, p):
        c = 1
        for j in cnt[ind]:
            if c != p:
                ans[ind][j] = c
                c += 1
            else:
                c += 1
                ans[ind][j] = c
                c += 1
            rec(j, c - 1)

    rec(1, 0)
    print(max([max(i) for i in ans]))
    for i in range(n - 1):
        print(ans[ab[i][0]][ab[i][1]])
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()

    return


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

Submission status: Runtime Error

Solution code:
from collections import Counter
l = []
l2 = []
l3 = []
n = int(input())
for i in range(n - 1):
  ll = list(map(int, input().split()))
  a = ll[0]
  b = ll[1]
  l2.append(a)
  l2.append(b)
  l.append(ll)
  l3.append([])
l3.append([])
counter = Counter(l2)
k = max(counter.values())
kk = [i for i in range(1, k+1)]
s = set(kk)
print(k)
for i in range(n - 1):
  a = l[i][0]
  b = l[i][1]
  sss = set(l3[a-1])
  ssss = set(l3[b-1])
  ss = s - sss - ssss
  r = min(ss)
  l3[a-1].append(r)
  l3[b-1].append(r)
  print(r)

Submission status: Runtime Error

Solution code:
n = int(input())
tree_i = {}
tree_n = {}
for i in range(n-1):
  a,b = map(int,input().split())
  tree_i[(a,b)] = i
  if a in tree_n:
    tree_n[a].append(b)
  else:
    tree_n[a] = [b]
  if b in tree_n:
    tree_n[b].append(a)
  else:
    tree_n[b] = [a]
max_len = 0
for value in tree_n.values():
  if max_len < len(value):
    max_len = len(value)
print(max_len)
ans = [0 for i in range(n)]

def coloring(n_b,n,color_b,tree_i,tree_n):
  nodes = tree_n[n]
  color = 0
  for node in nodes:
    if node ==n_b:
      continue
    if color == color_b:
      color += 1
    a = min(n,node)
    b = max(n,node)
    ans[tree_i[(a,b)]] = color
    coloring(n,node,color,tree_i,tree_n)
    color +=1

coloring(-1,1,-1,tree_i,tree_n)
for i in ans:
  print(i+1)

Submission status: Runtime Error

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[a*N + b] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1]]
while Q:
    cur, prev = Q.pop()
    NG = colors[min(cur, prev)*N+max(cur, prev)]
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur])
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Runtime Error

Solution code:
n=int(input())
node=[[] for _ in range(n)]
c_num=[0 for _ in range(n)]
arr=[]
ans=[0 for _ in range(n-1)]
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    arr.append([a-1,b-1])
    node[a-1].append(b-1)
    node[b-1].append(a-1)
    c_num[a-1]+=1
    c_num[b-1]+=1
c=max(c_num)
c_arr=[[i for i in range(1,c+1)] for _ in range(n)]
print(c_num)
for i in range(n-1):
    del_num=c_arr[arr[i][0]].pop(0)
    print(del_num)
    ans[i]=del_num
    c_arr[arr[i][1]].remove(del_num)

Submission status: Runtime Error

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

vector<vector< pair<int, int> >> edge;
int N;

int deg[int(1e5) + 3];
int color[int(1e5) + 3];
int ans[int(1e5) + 3];

int maxAns = 0;

void dfs(int x) {
    int CL = 0;
    for(const pair<int, int> &P : edge[x]) {
        if(color[P.first]) continue;
        //
        do {
            CL++;
        } while(CL == color[x]);
        //
        color[P.first] = CL;
        ans[P.second] = CL;
        maxAns = max(maxAns, CL);
        dfs(P.first);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //
    cin >> N;
    edge.resize( N+1, vector<pair<int, int>> () );
    for(int a, b, i = 1; i < N; i++) {
        cin >> a >> b;
        edge[a].push_back( {b, i} );
        edge[b].push_back( {a, i} );
        deg[a]++;
        deg[b]++;
    }
    for(int i = 1; i <= N; i++)
        if(deg[i] == 1) {
            color[i] = -1;
            dfs(i);
            break;
        }
    //
    printf("%d\n", maxAns);
    for(int i = 1; i < N; i++) printf("%d\n", ans[i]);
}

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[]
root=[[] for i in range(n)] 
for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append((i,b-1))
    root[b-1].append((i,a-1))
c=0
for i in range(n):
    c=max(c,len(root[i]))
print(c)
color=[0]*(n-1)

def dfs(node,par,c):
    if c!=1:
        i=1
    else:
        i=2
    for idx,x in root[node]:
        if x==par:
            continue
        if color[idx]==0:
            color[idx]=i
            dfs(x,node,i)
            i+=1
            if i==c:
                i+=1
dfs(0,-1,0)
for i in range(n-1):
    print(color[i])

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
tree = [0]*n
input_list = [0]*n
 
for i in range(n-1):
    a, b = map(int, input().split())
    input_list[i] = [a, b]
    tree[a-1] = tree[a-1] + 1
    tree[b-1] = tree[b-1] + 1

ans = max(tree)
print(ans)

keyofkey = [[int(i) for i in range(1, ans+1)] for i in range(n)]

for i in range(n-1):
    a, b = input_list[i][0], input_list[i][1]
    key_list = list(set(keyofkey[a-1]) & set(keyofkey[b-1]))
    p = key_list[0]
    keyofkey[a-1].remove(p)
    keyofkey[b-1].remove(p)
    print(p)

Submission status: Runtime Error

Solution code:

n = int(input())

graph = [[] for i in range(n)]

edges = []
for i in range(n-1):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    #edge = (a, b)
    edge = tuple(sorted([a, b]))
    edges.append(edge)

node_nums = [len(node) for node in graph]
num_color = max(node_nums)
print(num_color)


def coloring(edge_colors, parent_node, cur_node, former_color):
    kid_nodes = graph[cur_node]

    if len(kid_nodes) == 1:
        return edge_colors

    cur_color = 1
    for kid_node in kid_nodes:
        if kid_node == parent_node:
            continue

        if former_color == cur_color:
            cur_color += 1
        edge = tuple(sorted([cur_node, kid_node]))
        edge_colors[edge] = cur_color
        edge_colors = coloring(edge_colors, cur_node, kid_node, cur_color)

        cur_color += 1

    return edge_colors
        

edge_colors = {}
start_node = node_nums.index(1)
kid_nodes = graph[start_node]
#assert len(kid_nodes) == 1
kid_node = kid_nodes[0]
edge = tuple(sorted([start_node, kid_node]))
cur_color = 1
edge_colors[edge] = cur_color
former_color = cur_color

edge_colors = coloring(edge_colors, start_node, kid_node, former_color)

for edge in edges:
    try:
        color = edge_colors[edge]
    except:
        color = 1
    print(color)

Submission status: Runtime Error

Solution code:
def func(iro,tree,num,max_color):
  if num not in tree:
    return
  
  my_color = iro[num]
  arr = tree[num]
  
  for i in arr:
    my_color += 1
    iro[i] = my_color % max_color
    func(iro,tree,i,max_color)
    

n = int(input())
tree = {}

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


color = len(tree[1])
for key in tree.keys():
  if key == 1:
    continue
    
  arr = tree[key]
  color = max(len(arr)+1, color)

print(color)

iro = [0] * (n+1)

func(iro,tree,1,color)

for i in b_arr:
  print(iro[i]+1)

Submission status: Runtime Error

Solution code:
n = int(input())

a = [0]*(n-1)
b = [0]*(n-1)

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


d = [0]*n

for i in range(n-1):
    d[a[i]-1]+=1
    d[b[i]-1]+=1

k = max(d)
print(k)


knode = []
for i in range(n):
    knode.append(list(range(1,k+1)))

c = [0]*(n-1)
for i in range(n-1):
    set_a = set(knode[a[i]-1])
    set_b = set(knode[b[i]-1])
    s_union = set_a & set_b
    c[i] = s_union.pop()
    knode[a[i]-1].remove(c[i])
    knode[b[i]-1].remove(c[i])


for i in c:
    print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[]
root=[[] for i in range(n)] 
for i in range(n-1):
    a,b=map(int,input().split())
    ab.append((a-1,b-1))
    root[a-1].append((i,b-1))
    root[b-1].append((i,a-1))
c=0
for i in range(n):
    c=max(c,len(root[i]))
print(c)
color=[0]*(n-1)

def dfs(node,par,c):
    if c!=1:
        i=1
    else:
        i=2
    for idx,x in root[node]:
        if x==par:
            continue
        if color[idx]==0:
            color[idx]=i
            dfs(x,node,i)
            i+=1
dfs(0,0,0)
for i in range(n-1):
    print(color[i])

Submission status: Runtime Error

Solution code:
n = int(input())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append([b, i])
  else:
    edges[a] = [[b, i]]
  if b in edges.keys():
    edges[b].append([a, i])
  else:
    edges[b] = [[a, i]]
colors = [0 for i in range(n-1)]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  global edges
  flags[node] = True
  for edge in edges[node]:
    if flags[edge[0]] == False:
      if i != cannot:
        colors[edge[1]] += i
      else:
        i += 1
        colors[edge[1]] += i
      i += 1
      search(edge[0], i-1)
search(1, 0)
print(max(colors))
for i in range(n-1):
  print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())
tree=[0 for _ in range(N)]
nodes=[]
for _ in range(N-1):
    m = list(map(int, input().split()))
    tree[m[0]-1]+=1
    tree[m[1]-1]+=1
    nodes.append(m)
print(max(tree))
colors = set([i+1 for i in range(max(tree))])
tree_col = [set() for _ in range(N)]
for i in nodes:
    c = (colors-(tree_col[i[0]-1]|tree_col[i[1]-1])).pop()
    tree_col[i[0]-1].add(c)
    tree_col[i[1]-1].add(c)
    print(c)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

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

K = 0
for i in range(N):
    K = max(K, len(repn[i]))
color_set = set([i for i in range(1, K)])
print(K)

q = [(0, K + 1)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    c_set.discard(color)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.pop()
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))

for pair in edge:
    print(color_dict[pair])

Submission status: Runtime Error

Solution code:
N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    E[v].sort()
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
c = 1
for v in range(1, N):
    available = {c: True for c in range(1, K+1)}
    for u in E[v]:
        if v > u:
            e_idx = edge_idx[(u, v)]
            available[edge_color[e_idx]] = False
            continue
        e_idx = edge_idx[(v, u)]
        while not available[c]: c = (c + 1) % K if c + 1 != K else K
        edge_color[e_idx] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(20000)

def decide_col(colors, edges, node, org, excl_color,max_col):
    if len(edges[node]) > 1:
        i = 1
        for elem in edges[node]:
            next_node = elem[0]
            ind = elem[1]
            if next_node != org:
                while i == excl_color:
                    i = i%max_col + 1
                colors[ind] = i
                decide_col(colors, edges, next_node, node, i,max_col)
                i += 1
    

def det_color(N,edges,start,max_col):
    colors = [0]*(N-1)
    i=1
    for elem in edges[start]:
        node = elem[0]
        ind = elem[1]
        colors[ind] = i
        decide_col(colors, edges, node, start, i, max_col)
        i += 1
    return colors
        

N = int(input())
edges = {}
edge_list = []

for i in range(N):
    edges[i] = []
count = [0]*N

for i in range(N-1):
    A, B = map(int,input().split())
    edge_list.append([A-1,B-1])
    edges[A-1].append([B-1,i])
    edges[B-1].append([A-1,i])
    count[A-1] += 1
    count[B-1] += 1

max_col = max(count)
print(max_col)
start_ind = np.argmax(count)
if type(start_ind)==list:
    start = start_ind[0]
else:
    start = start_ind
colors = det_color(N,edges,start,max_col)

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

Submission status: Runtime Error

Solution code:
n = int(input())
ab = []
si = [0 for i in range(n)]
for i in range(n-1):
	a, b = map(int, input().split())
	si[a-1] += 1
	si[b-1] += 1
	ab.append([a, b])
print(max(si))

cl = [[0] for i in range(n)]
for i in range(n-1):
	if cl[ab[i][0]-1][0] == 0 and cl[ab[i][1]-1][0] == 0:
		cl[ab[i][0]-1][0] = 1
		cl[ab[i][1]-1][0] = 1
		print(1)
	else:
		c = [j+1 for j in range(max(si))]
		for j in range(len(cl[ab[i][0]-1])):
			if cl[ab[i][0]-1][j] in c:
				c.remove(cl[ab[i][0]-1][j])
		for j in range(len(cl[ab[i][1]-1])):
			if cl[ab[i][1]-1][j] in c:
				c.remove(cl[ab[i][1]-1][j])
		print(min(c))
		cl[ab[i][0]-1].append(min(c))
		cl[ab[i][1]-1].append(min(c))