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:

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:
    color = edge_colors[edge]
    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)
    done = 0
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            done=1
        mx = max(mx,dfs(t, mx, i+done))
        # dfs(t, mx, i)
    return mx
mx = dfs(0, 1, -1)
# print(R)
# print(F)
print(mx)
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 - 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]:
                idx = ab.index([min(u, start) + 1, max(u, start) + 1])
                e_colors[idx] = i
                v_colors[u].add(i)
                v_colors[start].add(i)
                # print(v_colors, e_colors)
                break
        DFS(G, u, visited)

DFS(v_edges, 0)

for color in e_colors:
    print(color + 1)

Submission status: Runtime Error

Solution code:
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
typedef pair<int,int> pii;
vector<pii> G[MAXN];
int n,col[MAXN];
void dfs(int u, int fa, int tocol){
    int cnt = G[u].size()-(fa!=0);
    stack<int> stk;
    for(int i = 1; cnt; i++){
        if(i!=tocol){
            stk.push(i);
            cnt--;
        }
    }
    for(auto p : G[u]){
        int v = p.first;
        if(v==fa) continue;
        col[p.second] = stk.top();
        stk.pop();
        dfs(v,u,col[p.second]);
    }
}
int main(){
    ____();
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(make_pair(v,i));
        G[v].push_back(make_pair(u,i));
    }
    dfs(1,0,0);
    cout << *max_element(col+1,col+n) << endl;
    for(int i = 1; i < n; i++) cout << col[i] << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

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 = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    ab[a].append([b, i])
    ab[b].append([a, i])
re = [False] * n
ed = [0]*(n-1)


def c(i=0, used=-1):
    global re, ed
    if re[i]:
        return 0
    re[i] = True
    k = 1
    for j in ab[i]:
        if re[j[0]]:
            continue
        if k == used:
            k += 1
        ed[j[1]] = k
        c(j[0], k)
        k += 1


c()
print(max(ed))
print(" ".join([str(i) for i in ed]))

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=[1 for i in range(n)]
#print(g)

def abc(i):
    global res,g
    cnt=1
    for a in g[i]:
        if cnt==res[i]:
            cnt+=1
        #print(a)
        #cnt+=1
        #if a==6:
            #print(g[i],i,cnt,res[i])
        res[a]=cnt
        cnt+=1
        abc(a)
abc(0)
for i in res:
    print(i)

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())
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 = list(colors-(tree_col[i[0]-1]|tree_col[i[1]-1]))[0]
    tree_col[i[0]-1].add(c)
    tree_col[i[1]-1].add(c)
    print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))


ans = max(count)
c = 1



def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i not in pr:
            if c == col:
                c+=1
            x, y = sorted([i, idx])
            color[(x, y)] = c
            dfs(i, (x, y))
        c+=1

color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Submission status: Runtime Error

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

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

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

print(col)
for a, b in ed:
    color = min(cand-nodes[a]-nodes[b])
    print(color)
    nodes[a].add(color)
    nodes[b].add(color)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

G = defaultdict(list)

v = [-1 for _ in range(N - 1)]

for i, (a, b) in enumerate(ab):
    G[a].append((b, i))
    G[b].append((a, i))

def check(p, trg, pc):
    # print(p, trg, pc)
    c = 0
    for next_, vi in G[trg]:
        if next_ != p:
            if c == pc:
                c += 1
            check(trg, next_, c)
            if vi in v:
                v[vi] = c
            c += 1

check(0, 1, -1)
print(len(set(v)))
for c in v:
    print(c + 1)

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)]
stack = [1]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  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:
a, b, x = map(int, input().split())
keta = 10
if a*int("1"+"0"*9) + b*10 <= x:
    #print(a*int("1"+"0"*9) + b*10)
    print("1"+"0"*9)
else:
    keta-=1
    while keta > 0:
        if a*int("1"+"0"*(keta-1)) + b*keta > x:
            #print(a*int("1"+"0"*(keta-1)) + b*keta)
            keta-=1
        else:
            sub_no_b = x - b*keta
            #print("keta",keta,"sub_no_b",sub_no_b)
            print(sub_no_b//a)
            break
if keta == 0:
    print("0")

Submission status: Runtime Error

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

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

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

print(col)
for a, b in ed:
    color = min(cand-nodes[a]-nodes[b])
    print(color)
    nodes[a].add(color)
    nodes[b].add(color)

Submission status: Runtime Error

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

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def p(tt, parent):
    children = tt[parent]
    for i in range(len(children)):
        if children[i][0] == parent:
            children.remove(children[i])
            break

    res = {parent: children}
    for c, ii in children:
        tt[c].remove((parent, ii))
        res = {**res, **p(tt, c)}
    return res


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tt = defaultdict(list)

    for i, (a, b) in enumerate(ab):
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa
        a, b = b, a
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa

    tree = p(tt, 0)
    # print(tree)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tt[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*((N+2)*(10**5))
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = [i for i in range(1,K+1)]
    if(used_color!=0):
        available_color.remove(used_color)
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        col = available_color.pop()
        next_stk.append((next,col))

        colors[next*(10**5)+n] = col
        colors[n*(10**5)+next] = col
    stk = next_stk + stk
    seen.add(n)

print(K)
for edge in A:
    a,b = edge
    col = colors[a*(10**5)+b]
    print(col)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
a = []
b = []
for i in range(N-1):
    a.append(ab[i][0])
for i in range(N-1):
    b.append(ab[i][1])
    
ab_max = []
for i in range(N-1):
    ab_max.append(a[i])
    ab_max.append(b[i])
c = collections.Counter(ab_max)    
    
ans = max(c.values())

print(ans)

l = [i for i in range(1, N+1)]

ndic = {}
for i in range(1, N+1):
    ndic[i] = l[:]

for i in range(N-1):
    p = max(ndic[a[i]][0], ndic[b[i]][0])
    print(p)
    ndic[a[i]].remove(p)
    ndic[b[i]].remove(p)

Submission status: Runtime Error

Solution code:
import numpy as np

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:
                if i == excl_color:
                    i = i%max_col + 1
                colors[ind] = i
                decide_col(colors, edges, next_node, node, i,max_col)
    

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())
dp = [0] * n
dp_matrix = [[0]*n for i in range(n)]

a, b = map(int, input().split())
dp[a - 1] = 1
dp[b - 1] = 1
dp_matrix[a - 1][0] = 1
dp_matrix[b - 1][0] = 1
max_color = 1

ans = list()
ans.append(1)
for i in range(1, n - 1):
    a, b = map(int, input().split())
    dp[a - 1] += 1
    dp[b - 1] += 1
    max_color = max(max_color, max(dp[a - 1], dp[b - 1]))
    for j in range(max_color):
        if dp_matrix[a - 1][j] == 0 and dp_matrix[b - 1][j] == 0:
            dp_matrix[a - 1][j] = 1
            dp_matrix[b - 1][j] = 1
            ans.append(j+1)
            break

print(max(ans))
for i in range(n - 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = [[] for i in range(N+2)]
    for i in range(N-1):
        g[a[i]].append(b[i])
        g[b[i]].append(a[i])

    gcc = [len(i) for i in g]
    k = max(gcc)
    gc = [[j for j in range(1,k+1)] for i in g]
    
    
    ans = []
    for i in range(N-1):
        # print(gc, gc[a[i]])
        x = gc[a[i]].pop()
        ans.append(x)
        # gc[a[i]]
        gc[b[i]].remove(x)

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

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
bar_list = []
for i in range(N-1):
  b = list(map(int, input().split() ) )
  bar_list.append(b)
ALL = sum(bar_list, [])
c = collections.Counter(ALL)
nodes = [set() for i in range(len(c))]
cols = []

K = max(c.values())
ans = []

COLS = set(range(8))
for bar in bar_list:
  used_colors = nodes[bar[0] - 1] | nodes[bar[1] - 1]
  col = list(COLS - used_colors)[0]
  ans.append(col + 1)
  nodes[bar[0] - 1] = nodes[bar[0] - 1] | set([col])
  nodes[bar[1] - 1] = nodes[bar[1] - 1] | set([col])

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

Submission status: Runtime Error

Solution code:
N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] != 0:
      CU.add(CE[(min(u,v),max(u,v))])
  CC = []
  for cc in range(1,maxc+1):
    if cc not in CU:
      CC.append(cc)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N*(10**5)+10)
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = [i for i in range(1,K+1)]
    if(used_color!=0):
        available_color.remove(used_color)
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        col = available_color.pop()
        next_stk.append((next,col))

        colors[next*(10**5)+n] = col
        colors[n*(10**5)+next] = col
    stk = next_stk + stk
    seen.add(n)

print(K)
for edge in A:
    a,b = edge
    col = colors[a*(10**5)+b]
    print(col)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

        nodes = defaultdict(int)

        K = 0
        for a, b in ab:
            nodes[a] += 1
            nodes[b] += 1
            K = max([K, nodes[a], nodes[b]])

        print(K)
        color = defaultdict(set)
        all = set(range(1, K + 1))
        for a, b in ab:
            nokori = all - (color[a] | color[b])
            c = min(nokori)
            print(c)
            color[a].add(c)
            color[b].add(c)


# Run main
if __name__ == '__main__':
    AtCoder().main()

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)
    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]
e1, e2 = sorted([start_node, kid_node])
edge = (e1, e2)
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())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
vis=[False for i in range(n+1)]
def dfs(node,lastco=-1):
    tmp=lastco
    for v in G[node]:
        if not vis[v]:
            tmp+=1
            co[v]=tmp%k
            vis[v]=True
            if node==edge[v][0]:
                dfs(edge[v][1],co[v])
            else:
                dfs(edge[v][0],co[v])

dfs(root)
print(k)
for i in range(n-1):
    print(co[i]+1)

Submission status: Runtime Error

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

from collections import defaultdict
g = defaultdict(list)
for i in range(len(ab)):
    g[ab[i][0]].append(ab[i][1])
    g[ab[i][1]].append(ab[i][0])

k = 0
for key in g.keys():
    k = max(k, len(g[key]))
print(k)

from bisect import bisect_left

ans_d = dict()
for key in g.keys():
    ans_d[key] = [0] * len(g[key])

used_all = dict()
for key in g.keys():
    used_all[key] = []

for key in g.keys():
    used = used_all[key]

    unused = []
    for j in range(1, k+1):
        idx = bisect_left(used, j)
        if idx < len(used) and used[idx] == j:
            continue
        else:
            unused.append(j)
    # print(unused)

    idx = 0
    for j in range(len(g[key])):
        if ans_d[key][j] == 0:
            ans_d[key][j] = unused[idx]

            target = g[key][j]
            idx2 = bisect_left(g[target], key)
            ans_d[target][idx2] = unused[idx]
            used_all[key].append(unused[idx])
            used_all[target].append(unused[idx])
            idx += 1

# print(ans_d)

for i in range(len(ab)):
    idx = bisect_left(g[ab[i][0]], ab[i][1])
    print(ans_d[ab[i][0]][idx])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

G = defaultdict(list)

v = [-1 for _ in range(N - 1)]

for i, (a, b) in enumerate(ab):
    G[a].append((b, i))
    G[b].append((a, i))

def check(p, trg, pc):
    # print(p, trg, pc)
    c = 0
    for next_, vi in G[trg]:
        if next_ != p:
            if c == pc:
                c += 1
            check(trg, next_, c)
            v[vi] = c
            c += 1

check(0, 1, -1)
print(len(set(v)))
for c in v:
    print(c + 1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> G;
vector<int> colors;
unordered_map<int64_t, int> edge_index_map;

int64_t V(int64_t a, int64_t b) {
  if (a > b) swap(a, b);
  return a << 20 | b;
}

int64_t EdgeIndex(int64_t a, int64_t b) { return edge_index_map[V(a, b)]; }

void dfs(int from, int to, int color) {
  colors[EdgeIndex(from, to)] = color;

  int next_color = 1;
  if (next_color == color) next_color++;
  for (int v : G[to]) {
    if (v == from) continue;

    dfs(to, v, next_color);

    next_color++;
    if (next_color == color) next_color++;
  }
}

int main() {
  int N;
  cin >> N;
  G.resize(N);
  colors = vector<int>(N, 0);
  for (int i = 0; i < N - 1; i++) {
    int64_t A, B;
    cin >> A >> B;
    A--;
    B--;
    if (A > B) swap(A, B);
    G[A].push_back(B);
    G[B].push_back(A);
    edge_index_map[V(A, B)] = i;
  }

  int K = 0;
  for (int v = 0; v < N; v++) {
    K = max(int(G[v].size()), K);
  }

  dfs(0, G[0][0], 1);
  dfs(G[0][0], 0, 1);

  cout << K << endl;
  for (int i = 0; i < N - 1; i++) {
    cout << colors[i] << endl;
  }

  return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

G = defaultdict(list)

v = [-1 for _ in range(N - 1)]

for i, (a, b) in enumerate(ab):
    G[a].append((b, i))
    G[b].append((a, i))

def check(p, trg, pc):
    # print(p, trg, pc)
    c = 0
    for next_, vi in G[trg]:
        if next_ != p:
            if c == pc:
                c += 1
            check(trg, next_, c)
            v[vi] = c
            c += 1

# print(G)

check(0, 1, 0)
print(len(set(v)))
for c in v:
    print(c + 1)

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)
    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
        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]
e1, e2 = sorted([start_node, kid_node])
edge = (e1, e2)
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:
import collections

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

all = sum(bar_list, [])
c = collections.Counter(all)
nodes = [set() for i in range(len(c))]
cols = []

K = max(c.values())
ans = []

COLS = set(range(8))
for bar in bar_list:
    used_colors = nodes[bar[0]-1] | nodes[bar[1]-1]
    col = list(COLS - used_colors)[0]
    ans.append(col+1)
    nodes[bar[0] - 1] = nodes[bar[0]-1] | set([col])
    nodes[bar[1] - 1] = nodes[bar[1]-1] | set([col])

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

Submission status: Runtime Error

Solution code:
n=int(input())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
def dfs(node,pa=-1):
    #print(node)
    tmp=0
    if pa>=0:
        tmp=co[pa]
    for v in G[node]:
        if pa not in edge[v]:
            #print("??",v)
            tmp+=1
            co[v]=tmp%k+1
            if node==edge[v][0]:
                dfs(edge[v][1],node)
            else:
                dfs(edge[v][0],node)

dfs(root)
print(k)
for i in range(n-1):
    print(co[i])

Submission status: Runtime Error

Solution code:
N=int(input())
edges = [0 for i in range(N)]
edge_l = [[] for i in range(N)]
cols = [0 for i in range(N)]
out = 0
seen = [False for i in range(N)]

def paint(cur, parC):
  curC = 1
  seen[cur] = True
  for e in edge_l[cur]:
    if not seen[e[0]]:
      if curC == parC:
        curC+=1
      cols[e[1]] = curC
      paint(e[0], cols[cur])
      curC+=1

for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a]+=1
  edges[b]+=1
  edge_l[a].append([b,i])
  edge_l[b].append([a,i])
  out = max(out,edges[a],edges[b])
print(out)
paint(0,0)
for i in range(N-1):
  print(cols[i])

Submission status: Runtime Error

Solution code:
N=int(input())

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

def bfs(x, c, b):
    if seen[x]:
        return
    seen[x] = True
    if b!=-1:
        global k
        color[b] = c
        k = max(k,c)
    t = 1
    for i,b in G[x]:
        if t==c:
            t+=1
        if not(seen[i]):
            bfs(i,t,b)
            t+=1

seen = [False]*N
color = [0]*N
k=0
bfs(0, 0, -1)


print(k)
print(*color[:-1],sep='\n')