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: Time Limit Exceeded

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

ans=[[0 for i in range(n)]for j in range(n)]
from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

print(ma)
for i in range(n-1):
	print(ans[ab[i][0]][ab[i][1]])

Submission status: Time Limit Exceeded

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

check=[False]*n
ans=[[0 for i in range(n)]for j in range(n)]

from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

print(ma)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	maxd=0
	edges=[0]
	degree=[0 for i in range(n+1)]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		edges.append(0)
		dic[(a,b)]=i+1
		degree[a]+=1
		degree[b]+=1
		maxd=max(maxd,max(degree[a],degree[b]))
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	#print(dic)
	#print(adj)
	for i in range(1,n+1):
		for j in adj[i]:
			edges[dic[(i,j)]]=available[i][0]
			available[j].remove(available[i][0])
			available[i].pop(0)
	print(maxd)
	for i in range(1,len(edges)):
		if i==len(edges)-1:
			print(edges[i],end="")
		else:
			print(edges[i])	

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	maxd=0
	edges=[0]
	degree=[0 for i in range(n+1)]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		edges.append(0)
		dic[(a,b)]=i+1
		degree[a]+=1
		degree[b]+=1
		maxd=max(maxd,max(degree[a],degree[b]))
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	#print(dic)
	#print(adj)
	for i in range(1,n+1):
		for j in adj[i]:
			if (i,j) in dic:
				#print(dic[(i,j)])
				if(edges[dic[(i,j)]]==0):
					edges[dic[(i,j)]]=available[i][0]
					available[j].remove(available[i][0])
					available[i].pop(0)
					
			if (j,i) in dic:
				if(edges[dic[(j,i)]]==0):
					edges[dic[(j,i)]]=available[j][0]
					available[i].remove(available[j][0])
					available[j].pop(0)
	print(maxd)
	for i in range(1,len(edges)):
		if i==len(edges)-1:
			print(edges[i],end="")
		else:
			print(edges[i])	

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	maxd=0
	edges=[0]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		adj[b].append(a)
		edges.append(0)
		dic[(a,b)]=i+1
		if(maxd<len(adj[a])):
			maxd=len(adj[a])
			indx=a
		if(maxd<len(adj[b])):
			maxd=len(adj[b])
			indx=b
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	for i in range(1,n+1):
		for j in adj[i]:
			if (i,j) in dic:
				if(edges[dic[(i,j)]]==0):
					edges[dic[(i,j)]]=available[i][0]
					available[j].remove(available[i][0])
					available[i].pop(0)
					
			if (j,i) in dic:
				if(edges[dic[(j,i)]]==0):
					edges[dic[(j,i)]]=available[j][0]
					available[i].remove(available[j][0])
					available[j].pop(0)
	print(maxd)
	for i in range(1,len(edges)):
		if i==len(edges)-1:
			print(edges[i],end="")
		else:
			print(edges[i])	

main()

Submission status: Time Limit Exceeded

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

from collections import deque

def main():
    input_buffer = """
    """
    #8
    #1 2
    #2 3
    #2 4
    #2 5
    #4 7
    #5 6
    #6 8
    
    INPUT = list(reversed(input_buffer.strip().splitlines()))
    if INPUT:
        n = int(INPUT.pop())
        edges = [0] * (n-1)
        for i in range(n-1):
            edges[i] = tuple(map(int, INPUT.pop().split()))
    else:
        n = int(input())
        edges = [0] * (n-1)
        for i in range(n-1):
            edges[i] = tuple(map(int, input().split()))
        
    
    adjacency_list = [[] for i in range(n+1)]
    for edge in edges:
        adjacency_list[edge[0]].append(edge[1])
        adjacency_list[edge[1]].append(edge[0])
    
    
    max_order = max(len(i) for i in adjacency_list)
    root = 0
    for i in range(0, n+1):
        if len(adjacency_list[i]) == max_order:
            root = i
                 
    
    node_history = set()
    edge_dict = dict()
    node_deque = deque()
    
    
    node_deque.append(root)
    while len(node_deque):
        current_node = node_deque.popleft()
        undef_edges = []
        kinds = {i for i in range(1, max_order + 1)}
        
        for a in adjacency_list[current_node]:
            if a not in node_history:
                node_history.add(a)
                node_deque.append(a)
                
            if current_node < a:
                temp_edge = (current_node, a)
            else:
                temp_edge = (a, current_node)    
            
            if temp_edge in edge_dict.keys():
                kinds.remove(edge_dict[temp_edge])
            else:
                undef_edges.append(temp_edge)
                
        for undef_edge in undef_edges:
            kind = min(kinds)
            edge_dict[undef_edge] = kind
            kinds.remove(kind)
    
    
    print(max_order)
    for e in edges:
        print(edge_dict[e])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from collections import deque

input_buffer = """

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

INPUT = list(reversed(input_buffer.strip().splitlines()))
if INPUT:
    n = int(INPUT.pop())
    edges = [0] * (n-1)
    for i in range(n-1):
        edges[i] = tuple(map(int, INPUT.pop().split()))
else:
    n = int(input())
    edges = [0] * (n-1)
    for i in range(n-1):
        edges[i] = tuple(map(int, input().split()))
    

adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)
root = 0
for i in range(0, n+1):
    if len(adjacency_list[i]) == max_order:
        root = i
             

node_history = set()
edge_dict = dict()
node_deque = deque()


node_deque.append(root)
while len(node_deque):
    current_node = node_deque.popleft()
    undef_edges = []
    kinds = {i for i in range(1, max_order + 1)}
    
    for a in adjacency_list[current_node]:
        if a not in node_history:
            node_history.add(a)
            node_deque.append(a)
            
        if current_node < a:
            temp_edge = (current_node, a)
        else:
            temp_edge = (a, current_node)    
        
        if temp_edge in edge_dict.keys():
            kinds.remove(edge_dict[temp_edge])
        else:
            undef_edges.append(temp_edge)
            
    for undef_edge in undef_edges:
        kind = min(kinds)
        edge_dict[undef_edge] = kind
        kinds.remove(kind)


print(max_order)
for e in edges:
    print(edge_dict[e])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(1,max(used)+2))-used)
        ans[j] = temp
        used.add(temp)
ans2 = [ans[b] for b in B]
print(max(ans2))
for a in ans2:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(1,max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
print("\n".join(str(ans[b]) for b in B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({0,ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
print("\n".join(str(ans[b]) for b in B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(1,max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
for b in B:
    print(ans[b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({0,ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
for b in B:
    print(ans[b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
list = []
for i in range(n-1): #因数注意！
    M = input()    
    m = M.split()
    p = [int(i) for i in m] #1列の数列をリスト化
    p = p + [i]
    list.append(p) #list(行列)
color = [0 for i in range(n-1)] #各辺の色
maxcolor = 1
N = deque([[1,0]]) #頂点と使用されている色
delete = deque() #listから探索済みの辺を削除する
while len(list) != 0:
    a = N.popleft()
    b = 0
    for i, value in enumerate(list):
        if value[0] == a[0]:
            b = b + 1
            if b == a[1]:
                b = b + 1
            N.append([value[1],b])
            color[value[2]] = b
            delete.append(i)
            if maxcolor < b:
                maxcolor = b
        elif value[1] == a[0]:
            b = b + 1
            if b == a[1]:
                b = b + 1
            N.append([value[0],b])
            color[value[2]] = b
            delete.append(i)
            if maxcolor < b:
                maxcolor = b
    else:
        c = 0
        while len(delete) != 0:
            c = c + 1
            d = delete.popleft()
            del list[d-c+1]
print(maxcolor)
for i in color:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
list = []
for i in range(n-1): #因数注意！
    M = input()    
    m = M.split()
    p = [int(i) for i in m] #1列の数列をリスト化
    p = p + [i]
    list.append(p) #list(行列)
color = [0 for i in range(n-1)] #各辺の色
maxcolor = 1
N = deque([[1,0]]) #頂点と使用されている色
delete = deque() #listから探索済みの辺を削除する
while len(N) != 0:
    a = N.popleft()
    b = 0
    if len(list) != 0:
        for i, value in enumerate(list):
            if value[0] == a[0]:
                b = b + 1
                if b == a[1]:
                    b = b + 1
                N.append([value[1],b])
                color[value[2]] = b
                delete.append(i)
                if maxcolor < b:
                    maxcolor = b
            elif value[1] == a[0]:
                b = b + 1
                if b == a[1]:
                    b = b + 1
                N.append([value[0],b])
                color[value[2]] = b
                delete.append(i)
                if maxcolor < b:
                    maxcolor = b
        else:
            c = 0
            while len(delete) != 0:
                c = c + 1
                d = delete.popleft()
                del list[d-c+1]
print(maxcolor)
for i in color:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
list = []
for i in range(n-1): #因数注意！
    M = input()    
    m = M.split()
    p = [int(i) for i in m] #1列の数列をリスト化
    p = p + [i]
    list.append(p) #list(行列)
color = [0 for i in range(n-1)] #各辺の色
maxcolor = 1
N = deque([[1,0]]) #頂点と使用されている色
delete = deque() #listから探索済みの辺を削除する
while len(N) != 0:
    a = N.popleft()
    b = 0
    for i, value in enumerate(list):
        if value[0] == a[0]:
            b = b + 1
            if b == a[1]:
                b = b + 1
            N.append([value[1],b])
            color[value[2]] = b
            delete.append(i)
            if maxcolor < b:
                maxcolor = b
        elif value[1] == a[0]:
            b = b + 1
            if b == a[1]:
                b = b + 1
            N.append([value[0],b])
            color[value[2]] = b
            delete.append(i)
            if maxcolor < b:
                maxcolor = b
    else:
        c = 0
        while len(delete) != 0:
            c = c + 1
            d = delete.popleft()
            del list[d-c+1]
print(maxcolor)
for i in color:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
import numpy as np
R_children = ddict(set)
R_parents = ddict(set)
for ab in AB:
    R_children[ab[0]].add(ab[1])
    R_parents[ab[1]].add(ab[0])
ans = [0] * (N-1)
for i in range(N-1):
    used = set()
    for parent in R_parents[AB[i][0]]:
        color = ans[np.where(np.array(AB)[:,1]==AB[i][0])[0][0]]
        if color != 0:
            used.add(color) 
    for child in R_children[AB[i][1]]:
        color = ans[np.where(np.array(AB)[:,1]==child)[0][0]]
        if color != 0:
            used.add(color) 
    for child in R_children[AB[i][0]]:
        color = ans[np.where(np.array(AB)[:,1]==child)[0][0]]
        if color != 0:
            used.add(color) 
    if used == set():
        ans[i] = 1
    else:
        ans[i] = min(set(range(1,max(used)+2)) - used)
print(max(ans))
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        if self.next_colors[v] != c:
            return
        cnt = 1
        while cnt in self.colors_hash[v]:
            cnt += 1
        self.next_colors[v] = cnt
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])

Submission status: Time Limit Exceeded

Solution code:
class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        cnt = 1
        while cnt in self.colors_hash[v]:
            cnt += 1
        self.next_colors[v] = cnt
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])

Submission status: Time Limit Exceeded

Solution code:
class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
    
    def get_color(self, v):
        for i in range(1, N):
            if not i in self.colors_hash[v]:
                return i
        return N


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])

Submission status: Time Limit Exceeded

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

from collections import deque

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

# 使われていない色を保持する
nodes = [deque([i for i in range(1, n)]) for j in range(n)]

tree = {}
for edge in sorted(edges):
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b

    color = nodes[a-1].popleft()
    tree[(a, b)] = color
    nodes[b-1].remove(color)

print(max(tree.values()))
for edge in edges:
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b
    print(tree[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

l=[[] for j in range(n)]
m=[0]
t=[]

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

    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)
    """
    while True:
        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1
"""
    t.append(buf+1)
    m.append(i+1)
print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

l=[[] for j in range(n)]
m=[e for e in range(n-1)]
t=[]

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

    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)

    t.append(buf+1)

print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

l=[[] for j in range(n)]
m=[e for e in range(n-1)]
t=[]

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

    buf = min(list(set(m)^set(l[a]+l[b])))
    l[a].append(buf)
    l[b].append(buf)
    """
    while True:
        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1
"""
    t.append(buf+1)

print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
vertex_neighbor_vertices = {}  # 各頂点と、その頂点に隣接する頂点リストのマップ
vertex_colors = {}  # 各頂点と、その頂点を端点に持つ辺に塗られた色セットのマップ
sides = []  # 辺情報（(a_i, b_i)のタプル形式で、順番を保持）
side_color = {}  # 辺とその辺に塗られた色のマップ


def add_neighbors(start, end):
    neighbors_of_s = set()
    if start in vertex_neighbor_vertices:
        neighbors_of_s = vertex_neighbor_vertices[start]
    else:
        vertex_neighbor_vertices[start] = neighbors_of_s
    neighbors_of_s.add(end)


def init_colors(vertex):
    colors = set()
    if vertex not in vertex_colors:
        vertex_colors[vertex] = colors


def get_unused_color(colors_of_sv, colors_of_ev):
    for i in range(1, N + 1):
        if (i not in colors_of_sv) and (i not in colors_of_ev):
            return i


for i in range(N - 1):
    s, e = map(int, input().split())
    sides.append((s, e))
    add_neighbors(s, e)
    add_neighbors(e, s)
    init_colors(s)
    init_colors(e)

max_color_num = 0
max_neighbor_vertex = 0
for k, v in vertex_neighbor_vertices.items():
    if len(v) > max_color_num:
        max_color_num = len(v)
        max_neighbor_vertex = k

print(max_color_num)

# 辺を最も多く持つ頂点を起点に、幅優先探索で辺を色付けしていく
visited = set()
q = deque([max_neighbor_vertex])

while q:
    vertex = q.popleft()
    visited.add(vertex)
    # 色付け
    for neighbor in vertex_neighbor_vertices[vertex]:
        if neighbor in visited:
            continue
        q.append(neighbor)
        color = get_unused_color(vertex_colors[vertex], vertex_colors[neighbor])
        vertex_colors[vertex].add(color)
        vertex_colors[neighbor].add(color)
        side_color[(vertex, neighbor)] = color

for s, e in sides:
    color = 0
    if (s, e) in side_color:
        color = side_color[(s, e)]
    else:
        color = side_color[(e, s)]
    print(color)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

def get_color(id1, id2):
    return edge_colors_dict[(min(id1, id2), max(id1, id2))]

def set_color(color, id1, id2):
    node_list[id1-1].adj_color_dict[id2] = color
    node_list[id2-1].adj_color_dict[id1] = color
    edge_colors_dict[(min(id1, id2), max(id1, id2))] = color

class Node:

    def __init__(self, id, adj_id_list, adj_color_dict):
        self.id = id
        self.adj_id_list = adj_id_list
        self.adj_color_dict = adj_color_dict
    
    def get_min_color(self):
        exist_colors = []
        for color in self.adj_color_dict.values():
            if color != -1:
                exist_colors.append(color)
        color = 1
        while True:
            if not(color in exist_colors):
                return color
            else:
                color += 1

N = int(input())
adj_dict = defaultdict(list)
edge_colors_dict = {}
a, b = [], []
for i in range(N-1):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    adj_dict[ai].append(bi)
    adj_dict[bi].append(ai)
    edge_colors_dict[(ai, bi)] = -1

# node_list[id-1]で, idのnodeにアクセス可能.
node_list = []
for id in range(1, N+1):
    adj_id_list = adj_dict[id]
    adj_color_dict = {}
    for adj_id in adj_id_list:
        adj_color_dict[adj_id] = -1
    node = Node(id, adj_id_list, adj_color_dict)
    node_list.append(node)

open_list = deque()
open_list.append(1)
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    cur_node = node_list[cur_id-1]
    for adj_id in cur_node.adj_id_list:
        if get_color(cur_id, adj_id) == -1:
            open_list.append(adj_id)
            new_color = cur_node.get_min_color()
            set_color(new_color, cur_id, adj_id)

print(len(set(edge_colors_dict.values())))
for (ai, bi) in zip(a, b):
    print(edge_colors_dict[(ai, bi)])

Submission status: Time Limit Exceeded

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, p):
    used_color = node.edge_color
    for e in node.edge:
        if e != p:
            # 子のノードを取得
            child = tree[e]
            child_used_color = child.edge_color

            # このnodeと子のノードでまだ使っていない色を特定
            unused_colors = colors - (used_color | child_used_color)
            if len(unused_colors) == 0:
                color_num = max(colors) + 1
                colors.add(color_num)
            else:
                color_num = min(unused_colors)

            # このノードと、子のノードに使用ずみの色をマーク
            node.edge_color.add(color_num)
            child.edge_color.add(color_num)

            # 答えを記録
            if a < b:
                ans['{0} {1}'.format(node.num, child.num)] = color_num
            else:
                ans['{0} {1}'.format(child.num, node.num)] = color_num

            # 掘る
            dfs(child, node.num)


N = int(input())
ans = {}
colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)

# print("edges:{}".format(edges))
print(len(colors))
# print(ans)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))

Submission status: Time Limit Exceeded

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, p):
    used_color = node.edge_color
    for e in node.edge:
        if e != p:
            # 子のノードを取得
            child = tree[e]
            child_used_color = child.edge_color

            # このnodeと子のノードでまだ使っていない色を特定
            unused_colors = colors - (used_color | child_used_color)
            if len(unused_colors) == 0:
                color_num = max(colors) + 1
                colors.add(color_num)
            else:
                color_num = min(unused_colors)

            # このノードと、子のノードに使用ずみの色をマーク
            node.edge_color.add(color_num)
            child.edge_color.add(color_num)

            # 答えを記録
            ans['{a} {b}'.format(a=node.num, b=child.num)] = color_num
            ans['{a} {b}'.format(a=child.num, b=node.num)] = color_num

            # 掘る
            dfs(child, node.num)


N = int(input())
ans = {}
colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    inp = input()
    edges.append(inp.rstrip('\n'))
    a, b = map(int, inp.split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)

dfs(tree[1], -1)

# print("edges:{}".format(edges))
print(len(colors))
# print(ans)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph = [[] for i in range(N)]
basho = {}
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    sab = str(a) + '-' + str(b)
    sba = str(b) + '-' + str(a)
    basho[sab] = i
    basho[sba] = i
#print(basho)
#print(graph)
maxi = 0
root = -1
for i in range(N):
    leni = len(graph[i])
    maxi = max(leni, maxi)
    if maxi == leni:
        root = i

K = maxi
visited = [False for i in range(N)]
color = [0 for i in range(N)]
bashocolor = [0 for i in range(N-1)]
def bfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while Q:
        v = Q.pop()
        clist = [i for i in range(1, K+1)]
        clist = list(set(clist) - set([color[v]]))
        now = 0
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                color[u] = clist[now]
                now += 1
                nnn = str(v) + '-' + str(u)
                bashocolor[basho[nnn]] = color[u]
                Q.append(u)
bfs(root)
print(K)
for i in range(N-1):
    print(bashocolor[i])