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 
import sys
sys.setrecursionlimit(3000)

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)

Submission status: Runtime Error

Solution code:
import collections 

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)

Submission status: Runtime Error

Solution code:
'''input
6
1 2
1 3
1 4
1 5
1 6
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import defaultdict
import resource
import sys

resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def get_source():
	for i in graph:
		return i


def make(first, second):
	return str(first) + ' ' + str(second)


def dfs(node, visited, color, medges, mx_c):
	visited[node] = True
	c = 1
	for i in graph[node]:
		if i not in visited:
			if color[node] == c:
				c += 1
			color[i] = c
			medges[make(node, i)] = c
			medges[make(i, node)] = c
			mx_c[0] = max(mx_c[0], c)
			c += 1
			dfs(i, visited, color, medges, mx_c)


# main starts
graph = defaultdict(list)
n = int(input().strip())
edges = []
for _ in range(n - 1):
	u, v = list(map(int, input().split()))
	graph[u].append(v)
	graph[v].append(u)
	edges.append([u, v])

s = get_source()
color = dict()
visited = dict()
color[s] = 0
medges = dict()
mx_c =[0]
dfs(s, visited, color, medges, mx_c)

print(mx_c[0])
for i, j in edges:
	print(medges[make(i, j)])

Submission status: Runtime Error

Solution code:
'''input
6
1 2
1 3
1 4
1 5
1 6
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import defaultdict


def get_source():
	for i in graph:
		return i


def make(first, second):
	return str(first) + ' ' + str(second)


def dfs(node, visited, color, medges, mx_c):
	visited[node] = True
	c = 1
	for i in graph[node]:
		if i not in visited:
			if color[node] == c:
				c += 1
			color[i] = c
			medges[make(node, i)] = c
			medges[make(i, node)] = c
			mx_c[0] = max(mx_c[0], c)
			c += 1
			dfs(i, visited, color, medges, mx_c)


# main starts
graph = defaultdict(list)
n = int(input().strip())
edges = []
for _ in range(n - 1):
	u, v = list(map(int, input().split()))
	graph[u].append(v)
	graph[v].append(u)
	edges.append([u, v])

s = get_source()
color = dict()
visited = dict()
color[s] = 0
medges = dict()
mx_c =[0]
dfs(s, visited, color, medges, mx_c)

print(mx_c[0])
for i, j in edges:
	print(medges[make(i, j)])

Submission status: Runtime Error

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

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


# BFS
colors = {}
root = 0 # 頂点1が存在することが問題文中で保証されてるからここを根ノードとしよう
root_child0, _ = es[root][0]
colors[(root,root_child0)] = 1
K = 0
queue = [root]
visited = [0]*n
visited[root] = 1

ans_color = [0]*(n-1)

while queue:
    v = queue.pop(0)
    visited[v] = 1

    color = 1
    parent, _ = es[v][0] # vがrootの時は変なことになるけど後で弾くから大丈夫
    color_parent = colors[(v, parent)]

    for to, j in es[v]:
        if visited[to]: continue
        queue.append(to)

        if color == color_parent and v != root:
            color += 1

        colors[(v,to)] = color
        colors[(to,v)] = color

        ans_color[j] = color

        K = max(K, color)
        color += 1


print(K)
print(*ans_color, sep='\n')

Submission status: Runtime Error

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

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


# BFS
colors = {}
root = 0 # 頂点1が存在することが問題文中で保証されてるからここを根ノードとしよう
root_child0, _ = es[root][0]
colors[(root,root_child0)] = 0
color_parent = 0
K = 0
queue = [root]
visited = [0]*n
visited[root] = 1

ans_color = [0]*(n-1)

while queue:
    v = queue.pop(0)
    visited[v] = 1

    color = 1
    parent, _ = es[v][0] # vがrootの時は変なことになるけど後で弾くから大丈夫
    color_parent = colors[(v, parent)]

    for to, j in es[v]:
        if visited[to]: continue
        queue.append(to)

        if color == color_parent and v != root:
            color += 1

        colors[(v,to)] = color
        colors[(to,v)] = color

        ans_color[j] = color

        K = max(K, color)
        color += 1


print(K)
print(*ans_color, sep='\n')

Submission status: Runtime Error

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

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


# BFS
root = 0 # 頂点1が存在することが問題文中で保証されてる
colors = {}
colors[(0,1)] = 0
color_parent = 0
K = 0
queue = [root]
visited = [0]*n
visited[root] = 1

ans_color = [0]*(n-1)

while queue:
    v = queue.pop(0)
    visited[v] = 1

    color = 1
    parent, _ = es[v][0]
    color_parent = colors[(v, parent)]

    for to, j in es[v]:
        if visited[to]: continue
        queue.append(to)

        if color == color_parent and v != root:
            color += 1

        colors[(v,to)] = color
        colors[(to,v)] = color

        ans_color[j] = color

        K = max(K, color)
        color += 1


print(K)
print(*ans_color, sep='\n')

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab2 = [[] for i in range(n)]
for i in range(n-1):
  ab2[ab[i][0]-1].append([ab[i][1]-1, i])
  ab2[ab[i][1]-1].append([ab[i][0]-1, i])
coloring = [0]*(n-1)

def f(x, y, z):
  c = 0
  for i in ab2[x]:
    if i[0] != y:
      c += 1
      if c == z:
        c += 1
      coloring[i[1]] = c
      x1 = i[0]
      y1 = x
      z1 = c
      f(x1, y1, z1)

f(0, None, None)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab2 = [[] for i in range(n)]
for i in range(n-1):
  ab2[ab[i][0]-1].append([ab[i][1]-1, i])
  ab2[ab[i][1]-1].append([ab[i][0]-1, i])
coloring = [0]*(n-1)
uc = [set() for i in range(n)]

def f(x, y):
  for i in ab2[x]:
    if i[0] != y:
      c = 1
      while c in uc[x]:
        c += 1
      coloring[i[1]] = c
      uc[x].add(c)
      uc[i[0]].add(c)
      x1 = i[0]
      y1 = x
      f(x1, y1)

f(0, 0)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Runtime Error

Solution code:
N = int(input())
s = [input() for i in range(N-1)]
a = []
b = []
for ab in s:
    sab = ab.split(" ")
    a.append(int(sab[0]))
    b.append(int(sab[1]))

a.extend(b)
nodeList=set(a)
nodes = []
edgeList = []
for name in nodeList:
    nodes.append(Node(name))
    
i = 0
for ai,bi in zip(a, b):
    edgei = Edge(ai,bi,i)
    i += 1
    edgeList.append([i,edgei])
    for node in nodes:
        if node.getName() == ai or node.getName() == bi:
            node.init_edge(edgei)
for node in nodes:
    edges = node.edges
    colors = []
    i = 0
    for edge in edges:
        colors.append(edge.color)
        colors = list(set(colors))
    for edge in edges:
        if edge.color == -1:
            while True:
                if i in colors:
                    i += 1
                else:
                    break
            edge.setColor(i)
            colors.append(i)
allcolors = []
for node in nodes:
    edges = node.edges
    for edge in edges:
        allcolors.append(edge.getColor())
allcolors = set(allcolors)
print(len(allcolors))
for el in edgeList:
    print(el[1].getColor()+1)

Submission status: Runtime Error

Solution code:
N = int(input())
s = [input() for i in range(N-1)]
a = []
b = []
for ab in s:
    sab = ab.split(" ")
    a.append(int(sab[0]))
    b.append(int(sab[1]))

a.extend(b)
nodeList=set(a)
nodes = []
edgeList = []
for name in nodeList:
    nodes.append(Node(name))
i = 0
for ai,bi in zip(a, b):
    edgei = Edge(ai,bi,i)
    i += 1
    edgeList.append([i,edgei])
    for node in nodes:
        if node.getName() == ai or node.getName() == bi:
            node.init_edge(edgei)
for node in nodes:
    edges = node.edges
    colors = []
    i = 0
    for edge in edges:
        colors.append(edge.color)
        colors = list(set(colors))
    for edge in edges:
        if edge.color == -1:
            while True:
                if i in colors:
                    i += 1
                else:
                    break
            edge.setColor(i)
            colors.append(i)
allcolors = []
for node in nodes:
    edges = node.edges
    for edge in edges:
        allcolors.append(edge.getColor())
allcolors = set(allcolors)
print(len(allcolors))
for el in edgeList:
    print(el[1].getColor()+1)

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [list(map(int, (str(i)+' '+input()).split())) for i in range(n-1)]
coloring = [0]*(n-1)
uc = [set() for _ in range(n)]

def f(x, y):
  for i in ab:
    x1 = i[1]+i[2]-x
    if x == i[1] or x == i[2] and y != x1:
      c = 1
      while c in uc[x-1]:
        c += 1
      uc[x-1].add(c)
      uc[x1-1].add(c)
      coloring[i[0]] = c
      f(x1, x)
f(1, 0)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [set(map(int, input().split())) for i in range(n-1)]
coloring = [0]*(n-1)
uc = [set() for _ in range(n)]

def f(x):
  for i in ab:
    if x in i:
      c = 1
      while c in uc[x-1]:
        c += 1
      y = sum(i)-x
      uc[x-1].add(c)
      uc[y-1].add(c)
      num = ab.index(i)
      coloring[num] = c
      ab[num] = set()
      f(y)
f(1)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
count = [0]*n
for i in range(n-1):
  count[ab[i][0]-1] += 1
  count[ab[i][1]-1] += 1
color = max(count)
print(color)
uc = [[0]*color for i in range(n)]
for i in range(n-1):
  j = 0
  while (uc[ab[i][0]-1][j] | uc[ab[i][1]-1][j]):
    j+=1
  else:
    print(j+1)
    uc[ab[i][0]-1][j] = 1
    uc[ab[i][1]-1][j] = 1

Submission status: Runtime Error

Solution code:
import copy
N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)

deg=[len(v) for v in G]
K=max(deg)
Q=copy.copy(G[0])
X=[0]
C=[0]*N
color_map={}
while Q!=[]:
    v=Q.pop(0)
    X.append(v)
    colors=list(range(1,K+1))
    for u in G[v]:
        if C[u] in colors:
            colors.remove(C[u])
        for w in G[u]:
            if C[w] in colors:
                colors.remove(C[w])
        if u not in X:
            Q.append(u)
    color=copy.copy(colors[0])
    C[v]=color
    p=list(set(X)&set(G[v]))[0]
    color_map[(min(p,v),max(p,v))]=color

print(K)
for e in E:
    print(color_map[e])

Submission status: Runtime Error

Solution code:
N=int(input())
ab=[list(map(int, input().split())) for i in range(N-1)]
link=[[] for i in range(N+1)]
for i in range(0, N-1):
  link[ab[i][0]].append([ab[i][1], i])
  link[ab[i][1]].append([ab[i][0], i])
  
out=[0]*(N-1)
def f(num, prenum=0, prec=0):
  postc=1
  for postnum, linknum in link[num]:
    if postnum==prenum:
      continue
    if postc==prec:
      postc+=1
      
    out[linknum]=postc
    f(postnum, num, postc)
    postc+=1
    
f(1)

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

Submission status: Runtime Error

Solution code:
def colorize(current_node, adjacents, colors, from_color, k):
    
    # そのノードから繋がるエッジを辿っていく
    count = 0
    for edge, node in adjacents[current_node]:

        # 既に塗られていたら無視
        if colors[edge]!=None:
            continue
        
        count += 1
        colors[edge] = (from_color+count)%k
        colorize(node, adjacents, colors, colors[edge], k)
        
N = int(input())
adjacents = {i+1:[] for i in range(N)}

for i in range(N-1):
    a,b = [int(e) for e in input().split(" ")]
    
    adjacents[a].append( [i+1,b] )
    adjacents[b].append( [i+1,a] )

# 一番隣接エッジ数が多いノード
most_edge =sorted(adjacents, key=lambda d:len(adjacents[d]))[-1]
k = len(adjacents[most_edge])

colors = {i+1:None for i in range(N-1)}

colorize(1, adjacents, colors, -1, k)

print(k)

for color in colors.values():
    print(color+1)

Submission status: Runtime Error

Solution code:
def colorize(current_node, adjacents, colors, from_color, k):
    
    # そのノードから繋がるエッジを辿っていく
    count = 0
    for edge, node in adjacents[current_node]:

        # 既に塗られていたら無視
        if colors[edge]!=None:
            continue
        
        count += 1
        colors[edge] = (from_color+count)%k
        colorize(node, adjacents, colors, colors[edge], k)
        
N = int(input())
adjacents = {i:[] for i in range(N)}

for i in range(N-1):
    a,b = [int(e) for e in input().split(" ")]
    
    adjacents[a].append( [i+1,b] )
    adjacents[b].append( [i+1,a] )

# 一番隣接エッジ数が多いノード
most_edge =sorted(adjacents, key=lambda d:len(adjacents[d]))[-1]
k = len(adjacents[most_edge])

colors = {i+1:None for i in range(N-1)}

colorize(1, adjacents, colors, -1, k)

print(k)

for color in colors.values():
    print(color+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        par[nowNode] = parentNode
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**5+10)

n = int(input())
visited = set()
g = {}
idx = {}
color = {}
for i in range(n-1):
    a,b = map(int, input().split())
    idx[i] = (a,b)
    if a not in g:
        g[a] = []
    g[a].append(b)
    if b not in g:
        g[b] = []
    g[b].append(a)

def dfs(v,c):
    cc = 0
    for u in g[v]:
        if u in visited:
            continue
        visited.add(u)

        cc += 1
        while cc==c:
            cc += 1
        a,b = min(u,v),max(u,v)
        color[(a,b)] = cc
        
        dfs(u,cc)
visited.add(1)
dfs(1,0)

print(max(*color.values()))
for i in range(n-1):
    print(color[idx[i]])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
B = [e[1] for e in edges] 

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

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Submission status: Runtime Error

Solution code:
from collections import deque
 
N, *AB = map(int, open(0).read().split())
B = AB[1::2]
 
E = [[] for _ in range(N)]
for a, b in zip(*[iter(AB)] * 2):
    E[a-1].append(b-1)

Q = deque([0])
C = [0] * (N)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += c == C[v]
        C[u] = c
        Q.append(u)

print(max(C)+1)
for b in B:
    print(C[b]+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
    colors[(x-1, y-1)] = 0
use_color = max(len(x) for x in tree)

queue, passed = deque([0]), set()
while queue:
    x = queue.popleft()
    passed.add(x)
    pallet = [i for i in range(use_color)][::-1]
    for y in tree[x]:
        if y in passed:
            if (x, y) in colors:
                pallet.remove(colors[(x, y)])
            elif (y, x) in colors:
                pallet.remove(colors[(y, x)])
            continue
        if (x, y) in colors:
            colors[(x, y)] = pallet.pop()
        elif (y, x) in colors:
            colors[(y, x)] = pallet.pop()
        queue.append(y)

print(use_color)
for c in colors.values():
    print(c+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
    colors[(x-1, y-1)] = 0
use_color = max(len(x) for x in tree)

queue, passed = deque([0]), set()
while queue:
    x = queue.popleft()
    passed.add(x)
    pallet = [i for i in range(use_color)][::-1]
    for y in tree[x]:
        if y in passed:
            if (x, y) in colors:
                pallet.remove(colors[(x, y)])
            if (y, x) in colors:
                pallet.remove(colors[(y, x)])
            continue
        colors[(x, y)] = pallet.pop()
        queue.append(y)

print(use_color)
for c in colors.values():
    print(c+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], dict()
for x, y in edges:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
    colors[(x-1, y-1)] = 0
use_color = max(len(x) for x in tree)

queue, passed = deque([0]), set()
while queue:
    x = queue.popleft()
    passed.add(x)
    pallet = [i for i in range(use_color)][::-1]
    for y in tree[x]:
        if y in passed:
            if (x, y) in colors:
                pallet.remove(colors[(x, y)])
            if (y, x) in colors:
                pallet.remove(colors[(y, x)])
            continue
        colors[(x, y)] = pallet.pop()
        queue.append(y)

print(use_color)
for c in colors.values():
    print(c+1)

Submission status: Runtime Error

Solution code:
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

# numpy and scipy are available for use
import numpy
import scipy
#https://atcoder.jp/contests/abc146/tasks/abc146_d
#D - Coloring Edges on Tree
"""
this version has ac in all but 2 cases...
"""

# reads a single line
N = gi()
cs = {}
nbls = [[] for i in range(N)]  #[] * N won't work
ans = 0
il = []

for i in range(1, N):
    a = gi() - 1
    b = gi() - 1
    nbls[a].append(b)
    nbls[b].append(a)
    il.append((min(a, b), max(a, b)))


def color(v, p):
    #print(v, p)
    ecs = []
    tos = []
    for u in nbls[v]:
        e = (min(u, v), max(u, v))
        if e in cs:
            ecs.append(cs[e])
        else:
            tos.append(e)

    ecs.sort()

    can_cs = []

    prev_c = ecs[0] - 1
    while len(can_cs) < len(tos) and prev_c > 0:
        can_cs.append(prev_c)
        prev_c -= 1

    for i in range(1, len(ecs)):
        prev_c = ecs[i] - 1
        while prev_c > ecs[i - 1] and len(can_cs) < len(tos):
            can_cs.append(prev_c)
            prev_c -= 1

    next_c = ecs[-1] + 1
    while len(can_cs) < len(tos):
        global ans
        ans += 1
        can_cs.append(next_c)
        next_c += 1
    i = 0
    for to in tos:
        cs[to] = can_cs[i]
        i += 1

    for u in nbls[v]:
        if u != p:
            color(u, v)


for u in nbls[0]:
    e = (0, u)
    ans += 1
    cs[e] = ans

color(0, -1)

print(ans)
for e in il:
    print(cs[e])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n+1)]

for index, _ in enumerate(range(n-1)):
    a, b = map(int, input().split())
    graph[a-1].append([b-1, index])


ans = [None] * (n-1)

def paint(curr_v, parent_color):
    child_color = 1
    for next_v, index in graph[curr_v]:
        # if child_color same as parent_color, then child_color has count up.
        if child_color == parent_color:
            child_color += 1


        ans[index] = child_color

        # child_color will be parent_color for next child.
        paint(next_v, child_color) 
        child_color += 1

# start root node
paint(0, 0) 
print(max(ans))
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

ans = [0] * (N-1)

def dfs(v, p=-1, c=-1): #親p(はじめはいないので-1), 子がv, 親の色も渡す必要あり
    # 子が次の子孫をグラフから探す
    global ans
    next_v = edges[v]
    cnt = 1 # num of colors
    for u,i in next_v:
        # 子孫の中には親もいて、それは除外
        if u == p: continue
        # 子供に対しては自分が親となり、同様のことをする
        if cnt == c:
            cnt += 1
        ans[i] = cnt      
        cnt += 1
        dfs(u, v, ans[i])


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

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

ans = [0] * (N-1)

def dfs(v, p=-1, c=-1): #親p(はじめはいないので-1), 子がv, 親の色も渡す必要あり
    # 子が次の子孫をグラフから探す
    global ans
    next_v = edges[v]
    cnt = 1 # num of colors
    for u,i in next_v:
        # 子孫の中には親もいて、それは除外
        if u == p: continue
        # 子供に対しては自分が親となり、同様のことをする
        if cnt == c:
            cnt += 1
        ans[i] = cnt      
        cnt += 1
        dfs(u, v, ans[i])

dfs(0)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
es = [[] for _ in range(n)]

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

ans = [0] * (n-1) 

def coloring(vi,prev_color):
  color = 1    
  for to,i in es[vi] :
    if color == prev_color:
      color += 1        
    ans[i] = color     
    coloring(to,color)
    color += 1
    
coloring(0,0)

print(max(ans))
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
#要素数nのdicを作成
n = int(input())
dic = {}

#使用可能な色を取得
def getcolor(a):
  global colordic
  return min(colordic[a])
#使用した色を格納
def delcolor(a,c):
  global colordic
  colordic[a].remove(c)
for i in range(n):
  dic[i+1] = set()

data = []
for i in range(n-1):
  data.append(input().split())
#辺から隣接点の追加
for value in data:
  a = int(value[0])
  b = int(value[1])
  dic[a].add(b)
  dic[b].add(a)

#最大次数を取得
ma = 0
for key,val in dic.items():
  if len(val) > ma:
    ma = len(val)

color = [int(s) for s in range(1,ma+1)]
#print(data)
#print(dic)
print(ma)
colordic = {}
for i in range(n):
  colordic[i+1] = set(color)

#データでループ
for col in data:
  a = int(col[0])
  b = int(col[1])
  mina = getcolor(a)
  minb = getcolor(b)
  usecolor = max(mina,minb) 
  print(usecolor)
  delcolor(a,usecolor)
  delcolor(b,usecolor)

Submission status: Runtime Error

Solution code:
#要素数nのdicを作成
n = int(input())
dic = {}

#使用可能な色を取得
def getcolor(a):
  global colordic
  if len(colordic[a]) == 0:
    return 0
  else:
    return min(colordic[a])
#使用した色を格納
def delcolor(a,c):
  global colordic
  colordic[a].remove(c)
for i in range(n):
  dic[i+1] = set()

data = []
for i in range(n-1):
  data.append(input().split())
#辺から隣接点の追加
for value in data:
  a = int(value[0])
  b = int(value[1])
  dic[a].add(b)
  dic[b].add(a)

#最大次数を取得
ma = 0
for key,val in dic.items():
  if len(val) > ma:
    ma = len(val)

color = [int(s) for s in range(1,ma+1)]
#print(data)
#print(dic)
print(ma)
colordic = {}
dicdata = [int(s) for s in range(1,n+1)]
for i in range(n):
  colordic[i+1] = set(dicdata)

#データでループ
for col in data:
  a = int(col[0])
  b = int(col[1])
  mina = getcolor(a)
  minb = getcolor(b)
  usecolor = max(mina,minb) 
  print(usecolor)
  delcolor(a,usecolor)
  delcolor(b,usecolor)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

def input():
    return sys.stdin.readline()[:-1]

n = int(input())
l = np.zeros((n,n))
l_ = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    l[a,b] = 0.1
    l_.append((a,b))
L = l + l.T
s = np.sum(L,axis=0)
def search(l,idx,c):
    return np.all(l[idx[0],] != c) and np.all(l[:,idx[1]] != c)
idxs = np.where(l==0.1)
C = 1
for i,j in zip(idxs[0],idxs[1]):
    idx = (i,j)
    c = 1
    while True:
        if search(L,idx,c):
            L[idx] = c
            L[idx[::-1]] = c
            break
        else:
            c += 1
    if c > C:
        C = c
print(C)
for i in l_:
    print(int(L[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
l = np.zeros((n,n))
l_ = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    l[a,b] = 0.1
    l_.append((a,b))
L = l + l.T
s = np.sum(L,axis=0)
def search(l,idx,c):
    #if c in l[idx[0],] or c in l[:,idx[1]]:                                                
    #if np.any(l[idx[0],] == c) or np.any(l[:,idx[1]] == c):                                
    #    return False                                                                       
    #else:                                                                                  
    #    return True                                                                        
    return np.all(l[idx[0],] != c) and np.all(l[:,idx[1]] != c)
idxs = np.where(l==0.1)
C = 1
for i,j in zip(idxs[0],idxs[1]):
    idx = (i,j)
    c = 1
    while True:
        if search(L,idx,c):
            L[idx] = c
            L[idx[::-1]] = c
            break
        else:
            c += 1
    if c > C:
        C = c
print(C)
for i in l_:
    print(int(L[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
l = np.zeros((n,n))
l_ = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    l[a,b] = 0.1
    l_.append((a,b))
#print(l)                                                                                   
L = l + l.T
s = np.sum(L,axis=0)
#min_color = np.max(s)                                                                      
def search(l,idx,c):
    if c in l[idx[0],] or c in l[:,idx[1]]:
        return False
    else:
        return True
idxs = np.where(l==0.1)
C = 1
for i,j in zip(idxs[0],idxs[1]):
    idx = (i,j)
    c = 1
    while True:
        if search(L,idx,c):
            L[idx] = c
            L[idx[::-1]] = c
            break
        else:
            c += 1
    if c > C:
        C = c
print(C)
#print(L)                                                                                   
#idxs_ = np.where(l > 0)                                                                    
#for i,j in zip(idxs_[0],idxs_[1]):                                                         
#    print(int(L[(i,j)]))                                                                   
for i in l_:
    print(int(L[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
l = np.zeros((n,n))
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    l[a,b] = 0.1
#print(l)                                                                                   
l_ = l.T
L = l+l_
s = np.sum(L,axis=0)
#min_color = np.max(s)                                                                      
c = 1

def search(l,idx,c):
    if c in l[idx[0],] or c in l[:,idx[1]]:
        return False
    else:
        return True
idxs = np.where(l==0.1)
C = 1
for i,j in zip(idxs[0],idxs[1]):
    idx = (i,j)
    c = 1
    while True:
        if search(L,idx,c):
            L[idx] = c
            L[idx[::-1]] = c
            break
        else:
            c += 1
    if c > C:
        C = c
print(C)
#print(L)                                                                                   
idxs_ = np.where(L*l*10 >= 1)
for i,j in zip(idxs_[0],idxs_[1]):
    print(int(L[(i,j)]))