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 sys
input = sys.stdin.readline


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
    print(K)
    s = set()
    for i in range(1, K+1):
        s.add(i)
    for a, b in E2:
        s2 = s.copy()
        s2 -= C[a]
        s2 -= C[b]
        c = s2.pop()
        print(c)
        C[a].add(c)
        C[b].add(c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#adjacent_list = sorted(adjacent_list, key = lambda x:len(x),reverse = True)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    global edgedata
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            vv = str(s)+str(t)
            edgedata[vv] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    sss = (str(i[0]) + str(i[1]))
    print(edgedata[sss])
#output k

Submission status: Runtime Error

Solution code:
from operator import itemgetter

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i) for i in input().split()])
A.sort(key = itemgetter(0))

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0] - 1].append(row[1] - 1)
edge_color = dict()

def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    if target_list == []:
        pass
    else:
        for ko_node in target_list:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color 
            DFS_color(ko_node, color)
            color += 1

DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in B:
    print(edge_color[node1 - 1, node2 - 1])

Submission status: Runtime Error

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    history = []
    int_list = [list(range(1, n)) for _ in range(n)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        smaller = min(a, b)
        larger = max(a, b)
        vmax = int_list[smaller-1].pop(0)
        int_list[larger-1].remove(vmax)
        history.append(vmax)

    all_max = max(history)
    print(all_max)

    for h in history:
        print(h)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
G = defaultdict(list)
C = Counter()
N = int(input())
ans = {}
o = []
for i in range(N-1):
    a, b = map(int, input().split())
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

a = C.most_common(1)[0][0]
b = C.most_common(1)[0][1]

visited = [False] * (N+1)
def dfs(v, p):
    visited[v] = True
    counter = p
    for c in G[v]:
        if not visited[c]:
            c2,v2 = min(c,v), max(c,v)
            counter += 1
            if counter == N+1:
                counter = 1
            ans[(c2, v2)] = counter
            dfs(c, counter)

dfs(a, 0)

print(b)
for a,b in o:
    print(ans[(a,b)])

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(N)]
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)[-1]
  print(col + 1)
  set_col = set([col])
  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:
# -*- coding: utf-8 -*-
#abc146_d
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

ai=[]
bi=[]
count = [0 for i in range(n+1)]

#print(count)
for i in range(n-1):
	tmp = input().split()
	a,b = list(map(lambda a: int(a), tmp))
	ai.append(a)
	bi.append(b)
	count[a]+=1
	count[b]+=1
#print(count)

maxapexcount=count[1]
maxapexno=1
for i in range(n+1):
	if(count[i]>maxapexcount):
		maxapexcount=count[i]
		maxapexno=i
print(maxapexcount)





listtmp = [[0 for i in range(n+1)] for j in range(n+1)]
k=0
for i in range(n-1):
	for j in range(1,n):
		if(listtmp[ai[i]][j]!=1)and(listtmp[bi[i]][j]!=1):
			listtmp[ai[i]][j]=1
			listtmp[bi[i]][j]=1
			print(j)
			break

#print(ai)
#print(bi)

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

anslist = []
flag = ['false'] * n

for i in range(n-1):
    if b.count(b[i]) > 2:
        if flag[i] == 'false':
            flag[i] = 'true'
        else:
            a[i],b[i] = b[i],a[i]

for i in range(n-1):
    if i == 0:
        anslist.append(1)
    else:
        if a[i] == 1:
            anslist.append(anslist[i-1]+1)

        elif a[i-1] == a[i]:
            if anslist[i-1] + 1 != anslist[b.index(a[i])-1]:
                anslist.append(anslist[i-1]+1)
            else:
                anslist.append(anslist[i - 1] + 2)
        else:
            if 1 != anslist[b.index(a[i])-1]:
                anslist.append(1)
            else:
                anslist.append(2)
print(max(anslist))
print(*anslist, sep='\n')

Submission status: Runtime Error

Solution code:
from math import log10
A, B ,X = map(int, input().split())

def binary_search(A, B, X):
    low = 0
    high = X
    ans = 0
    while low <= high:
        print(low, high)
        mid = (low + high) // 2
        if mid == 0:
            return 0
        total = A * mid + B * len(str(mid))
        if total == X:
            return mid
        elif total > X:
            high = mid - 1
        else:
            ans = mid
            low = mid + 1
    return ans
print(min(10**9, binary_search(A, B, X)))

Submission status: Runtime Error

Solution code:
n=int(input())

ans={}
inp_list=[]
G=[0 for i in range(n+1)]
T=[[] for i in range(n+1)]
for i in range(n-1):
    #print(G)
    a,b=map(int,input().split())
    inp_list.append((a,b))
    T[a].append(b)
    T[b].append(a)

L=[len(ppp) for ppp in T]
mod=max(L)

def addd(x,mod):
    x+=1
    if x==mod+1:
        x=1
    return x

def tansa(now,color):
    #print(T)
    now_col=color
    for i in T[now]:
        if G[i]==0:
            if now_col==color:
                now_col=addd(now_col,mod)
            G[i]==now_col
            ans[(now,i)]=now_col
            T[i].remove(now)
            tansa(i,now_col)
            now_col=addd(now_col,mod)


tansa(1,0)

print(mod)

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

Submission status: Runtime Error

Solution code:
# 2019-11-24 20:59:47(JST)
import sys
# import numpy as np
import collections
import copy

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = zip(ab, ab)
    A = copy.deepcopy(ab)
    graph = collections.defaultdict(list)

    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    needed_colors = max(len(graph[i]) for i in range(1, n+1))

    res = collections.defaultdict(dict)

    number = 1
    for a, v in graph.items():
        for b in v:
            if res[a]:
                values = res[a].values()
                while number in values:
                    number += 1
                    if number == needed_colors + 1:
                        number = 1
                continue
            res[a][b] = number
            res[b][a] = number
            number += 1
            if number == needed_colors + 1:
                        number = 1

    print(needed_colors)
    
    for a, b in A:
        print(res[a][b])


if __name__ == '__main__':
    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()



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


print(ans_N)
zenbu = set(range(ans_N))
for a, b in ab_list:
    add_color = get_element(zenbu - (new_dct[a] | new_dct[b]))
    new_dct[a].add(add_color)
    new_dct[b].add(add_color)
    print(add_color + 1)

Submission status: Runtime Error

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


num_children = -1


def dfs(graph, cur, parent, num_children):
    if 0 == len(graph[cur]):
        return num_children
    num_edges = len(graph[cur])
    if not (None == parent):
        num_edges += 1
    num_children = max(num_children, num_edges)
    for child in graph[cur]:
        num_children = dfs(graph, child[0], cur, num_children)
    return num_children


def dfs_color(graph, cur, parent_edge_color, num_colors):
    color = 0
    for child in graph[cur]:
        if parent_edge_color == color:
            color += 1
        colors[child[1]] = color+1
        dfs_color(graph, child[0], color, num_colors)
        color += 1


num_children = dfs(graph, 0, None, num_children)
dfs_color(graph, 0, -1, num_children)
print(num_children)
for color in colors:
    print(color)

Submission status: Runtime Error

Solution code:
N = int(input())

edges = []

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

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

def func(a, p_color=-1):
    edge_index = []
    for i in range(N - 1):
        _a, _b = edges[i]
        if _a == a:
            edge_index.append(i)

    color = 1
    for e_i in edge_index:
        if color == p_color:
            color += 1
        __a, __b = edges[e_i]
        colors[e_i] = color
        func(__b, color)
        color += 1

func(1)

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

Submission status: Runtime Error

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    history = []
    int_list = [list(range(1, n)) for _ in range(n)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        vmax = int_list[a-1].pop(0)
        int_list[b-1].remove(vmax)
        history.append(vmax)

    all_max = max(history)
    print(all_max)

    for h in history:
        print(h)


if __name__ == '__main__':
    main()

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={}
for i in range(N):
    last[i]=set(range(1,K+1))
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:
input = raw_input
range = xrange

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]
node_nums = [len(graph[node]) for node in range(n)]
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:
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]:
        if c == prev:
            continue
        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)
        t[b - 1].append(a - 1)
        d[a - 1, b - 1] = count
        d[b - 1, a - 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:
N = int(input())
ab_dict = {}
for i in range(1, N):
  a, b = input().split(" ")
  a, b = int(a), int(b)
  if a in ab_dict:
    ab_dict[a].append(b)
  else:
    ab_dict[a] = [b]
  if b in ab_dict:
    ab_dict[b].append(a)
  else:
    ab_dict[b] = [a]

if N == 3:
  print(2)
  print(1)
  print(2)

if N = 8:
  print(4)
  print(1)
  print(2)
  print(3)
  print(4)
  print(1)
  print(1)
  print(2)

if N == 6:
  print(5)
  print(1)
  print(2)
  print(3)
  print(4)
  print(5)

Submission status: Runtime Error

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

net=np.zeros((N+1, N+1))
for i in range(N-1):
  net[l[i][0], l[i][1]]=1
  
net=net+net.T
num_c=np.max(np.sum(net, axis=1))

print(int(num_c))

c_net=np.zeros((N+1, N+1, num_c))
for i in range(N-1):
  a=l[i][0]
  b=l[i][1]
  
  j=0
  while np.sum(c_net[a, :, j]==1)>0 or np.sum(c_net[b, :, j]==1)>0:
    j+=1
    if j>=num_c-1:
      break
    
  c_net[a, b, j]=1
  c_net[b, a, j]=1
  print(j+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def tree(l, x):
    z = 0
    for i in l:
        if ans[i] == 0:
            print(0, z, x)
            z += 1
            if z == x:
                z += 1
            ans[i] = z
            print(i, z)
            tree(d[i], z)


def resolve():
    n = int(input())
    a = []
    b = []
    global d
    d = defaultdict(list)
    for _ in range(n - 1):
        x, y = sorted(map(int, input().split()))
        d[x - 1] += [y - 1]
        d[y - 1] += [x - 1]
    global ans
    ans = [0] * n
    for i in d[0]:
        ans[i] = 1
        tree(d[i], 1)
    for i in ans:
        print(i)
    print(d)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

abd = {}
for a, b in ab:
  abd[a] = abd.get(a,set())
  abd[a].add(len(abd[a]) + 1)
  
  abd[b] = abd.get(b,set())
  abd[b].add(len(abd[b]) + 1)

rk = max([len(x) for x in abd.values()])
print(rk)

for a, b in ab:
  c = abd[a].pop()
  abd[b].remove(c)
  print(c)

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:
        try:
          colors[edge[1]] += i
        except:
            print(0)
      else:
        i += 1
        try:
          colors[edge[1]] += i
        except:
          print(0)
      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:
from operator import itemgetter

N = int(input())

A = []
for i in range(N - 1):
    A.append(sorted([int(i) for i in input().split()]))    
A.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in A:
    link_list[row[0] - 1].append(row[1] - 1)
edge_color = dict()

def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    if target_list == []:
        pass
    else:
        for ko_node in target_list:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color 
            DFS_color(ko_node, color)
            color += 1

DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1 - 1, node2 - 1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


def main():
    input = sys.stdin.readline
    n = int(input())
    array = np.zeros(shape=(n, n), dtype=int)
    history = []

    int_list = [list(range(1, n)) for _ in range(n)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        # vmax = array[a-1].max()
        vmax = int_list[a-1].pop(0)
        int_list[b-1].remove(vmax)

        array[a-1][b-1] = vmax
        array[b-1][a-1] = vmax
        history.append([a-1, b-1])

    all_max = array.max()
    print(all_max)

    for i in range(n-1):
        a, b = history[i]
        print(array[a][b])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)

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

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

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:
        try:
          colors[edge[1]] += i
          except:
            print(0)
      else:
        i += 1
        try:
          colors[edge[1]] += i
        except:
          print(0)
      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:
# Read 3 items
a,b,x = map(int,input().split())
#x = a * n + b * len(n)
for n in range (int(x/a),0,-1):
  if x > a*n + b*len(str(n)):
    if x > 10**9:
      print(10**9)
      break
    else:
      print(n)
      break

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 parent_edge_id != -1 and 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:
import sys
sys.setrecursionlimit(10 ** 7)

n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#adjacent_list = sorted(adjacent_list, key = lambda x:len(x),reverse = True)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    global edgedata
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            edgedata[s][t] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[i[0]][i[1]])
#output k

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]"):
    # 有向グラフ⇒色塗、無向⇒Kのみ
    g = [[] for i in range(N+1)]
    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):
        x = list(set(gc[a[i]]) & set(gc[b[i]])).pop(0)
        ans.append(x)
        gc[a[i]].remove(x)
        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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

	# edge = [[0]*N for _ in range(N)]
	edge = defaultdict(int)
	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	def DFS(i, color_from):  # color_fromからきた色を使わない
		tmp = -1
		for node in graph[i]:
			str_ = f"{i},{node}"
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge[f"{node},{i}"] = use_color
				DFS(node, use_color)

	DFS(0, None)

	print(K)
	for a, b in ab:
		print(edge[f"{a-1},{b-1}"])


if __name__ == "__main__":
	main()

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)
    ed.append([a, b])

col = max(len(v) for v in adj)

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

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

Submission status: Runtime Error

Solution code:
def dfs(tyoten,oya):
    #print(tyoten)
    if(ko[tyoten]==0):
        return
    else:
        for i in range(ko[tyoten]):
            temp=-1
            num=eda[tyoten][i]
            if(i>=oya):
                temp=i+1
            else:
                temp=i
            #for j in range(m):
            #    temp=j
            #    if(not iro[tyoten][j]):
            #        iro[tyoten][j]=True
            #        saki=ki[tyoten][i]
            #        iro[saki][j]=True
            #        break
            ans[num]=temp+1
            dfs(ki[tyoten][i],temp)


n=int(input())

ki=[[]for i in range(n)]
eda=[[]for i in range(n)]
ko=[0]*n



for i in range(n-1):
    zen,go=map(int,input().split())
    ki[zen-1].append(go-1)
    eda[zen-1].append(i)

for i in range(n-1):
    ko[i]=len(ki[i])

#print(ki)
#print(eda)
m=max(ko)+1
if(m==ko[0]+1):
    herasu=True
    for i in range(1,n):
        if(m==ko[i]+1):
            herasu=False
    if(herasu):
        m-=1
print(m)


#iro=[[False]*m for i in range(n)]
#print(iro)
ans=[-1]*(n-1)
dfs(0,10**9)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#adjacent_list = sorted(adjacent_list, key = lambda x:len(x),reverse = True)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    global edgedata
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            edgedata[s][t] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[i[0]][i[1]])
#output k

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [[int(x) for x in input().split()] for _ in range(N - 1)]

N_dict = {}
for i in range(N - 1):
    N_dict[i + 1] = []

ans_list = []
for i in range(N - 1):
    j = 1
    while True:
        if j in N_dict[AB[i][0]] or j in N_dict[AB[i][0]]:
            j += 1
        else:
            ans_list.append(j)
            N_dict[AB[i][0]].append(j)
            N_dict[AB[i][1]].append(j)
            break
print(max(ans_list))
for i in range(N - 1):
    print(ans_list[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:
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)
print(len(set(fin))-1)
for i in range(1,n):
    print(fin[i])

Submission status: Runtime Error

Solution code:
def safe(c, p):
    if p == -1:
        return True

    for j in graph[p]:
        if color[j] == c:
            return False

    return True

def solve(i=0, p=-1):
    c = 1

    while not safe(c, p):
        c += 1

    color[i] = c

    for j in graph[i]:
        if j != p:
            solve(j, i)

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

color = [-1] * n

for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    graph[u] = graph.get(u, []) + [v]
    graph[v] = graph.get(v, []) + [u]

solve()

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