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:
from collections import deque
from heapq import heappop
N = int(input())
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b, i))
    V[a].append(b)
    V[b].append(a)

for M in [max(D), max(D)+1]:
    flag = False
    Q = deque([argmax])
    check = [0]*N
    color = [2**M-1 for _ in range(N)]
    C = dict()
    while Q:
        v = Q.popleft()
        check[v] = 1
        for u in V[v]:
            if check[u]:
                continue
            else:
                Q.append(u)
            usable_colors = color[v] & color[u]
            if usable_colors == 0:
                flag = True
                break
            else:
                cnt = 0
                while usable_colors % 2 == 0:
                    usable_colors //= 2
                    cnt += 1

            C[tuple(sorted([u, v]))] = cnt
            color[v] -= 2**cnt
            color[u] -= 2**cnt
        if flag:
            break
    if M == max(D) and flag == False:
        break

ans = [0]*(N-1)  
for a, b, i in T:
    ans[i] = C[(a, b)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set(i for i in range(1, K+1))
    points = Q.popleft()
    p0, p1 = points

    set1 = set(adjm[p0])
    can_use_labels = labels - set1
    use_label = can_use_labels.pop()

    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if p != p0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = []

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

K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set(i for i in range(1, K+1))
    points = Q.popleft()
    p0, p1 = points

    set1 = set(adjm[p0])
    can_use_labels = labels - (set1)
    use_label = can_use_labels.pop()


    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if adjm[p1][p] == 0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = []

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

K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set([i for i in range(1, K+1)])
    points = Q.popleft()
    #print(points)
    p0, p1 = points

    set1 = set(adjm[p0])
    can_use_labels = labels - (set1)
    use_label = can_use_labels.pop()


    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if adjm[p1][p] == 0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = []

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

#print(edges)
#print(ab)
K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

# BFS
Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set([i for i in range(1, K+1)])
    points = Q.popleft()
    #print(points)
    p0, p1 = points

    set1 = set(adjm[p0])
    set2 = set(adjm[p1])
    can_use_labels = labels - (set1 | set2)
    #print('can use:', can_use_labels)
    use_label = can_use_labels.pop()
    #print('use:', use_label)

    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if adjm[p1][p] == 0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
d.append(0)
while d:
    temp=d.pop()
    temp_color=path_color[temp]
    edges=path_num_to_edges[temp]
    for edge in edges:
        new_path_color=1
        tree_edge_flag.add(edge)
        for other_edge,path_num in tree_path[edge]:
            if path_color[path_num]!=None:
                continue
            if other_edge in tree_edge_flag:
                continue
            tree_edge_flag.add(other_edge)
            if new_path_color==temp_color:
                new_path_color+=1
            path_color[path_num]=new_path_color
            new_path_color+=1
            d.append(path_num)


print(max(path_color))
for i in path_color:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)




#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.p_color=0
        self.child=[]
        self.c_color=[]
        self.type=-1
    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[None]
        self.list=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i+1
            self.tree.append(a)
        for i in range(self.node_n-1):
            hen=[int(j) for j in input().split(" ")]
            self.list.append(hen)
            self.tree[hen[0]].child.append(self.tree[hen[1]])
            self.tree[hen[1]].parent=self.tree[hen[0]]
            
        for i in range(1,self.node_n+1):
            node=self.tree[i]
            if node.parent==-1:
                node.type="root"
            elif node.child==[]:
                node.type="leaf"
            else:
                node.type=="other"
        
    def getroot(self):
        return self.tree[1]
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.type=="leaf":
                leaf.append(i)
        return leaf
    
    def gettree(self):
        return self.tree[:]

    
        
    
    
#木の作成
tree=Tree()


#使った色リスト
colorlist=[]


#調べたリスト

colvar=[tree.node_n-int(i) for i in range(tree.node_n) ]
node=tree.getroot()




def haihai(node):

    parentcolor=node.p_color
    children=node.child
    if children==[]:
        pass
    else:

        childcolor=colvar.copy()
        if parentcolor in childcolor:
            childcolor.remove(parentcolor)
        for child in children:
            color=childcolor.pop()
            child.p_color=color
            if color not in colorlist :
                colorlist.append(color)
            haihai(child)
            

haihai(node)


print(len(colorlist))


for j in [tree.tree[i[1]].p_color for i in tree.list]:
    print(j)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)




#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.p_color=0
        self.child=[]
        self.c_color=[]
        self.type=-1
    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[None]
        self.list=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i+1
            self.tree.append(a)
        for i in range(self.node_n-1):
            hen=[int(j) for j in input().split(" ")]
            self.list.append(hen)
            self.tree[hen[0]].child.append(self.tree[hen[1]])
            self.tree[hen[1]].parent=self.tree[hen[0]]
            
        for i in range(1,self.node_n+1):
            node=self.tree[i]
            if node.parent==-1:
                node.type="root"
            elif node.child==[]:
                node.type="leaf"
            else:
                node.type=="other"
        
    def getroot(self):
        return self.tree[1]
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.type=="leaf":
                leaf.append(i)
        return leaf
    
    def gettree(self):
        return self.tree[:]

    
        
    
    
#木の作成
tree=Tree()


#使った色リスト
colorlist=[]


#調べたリスト
# checklist=tree.gettree()
# checklist.pop(0)
# checklist.pop(0)
# print("checklist",[i.name for i in checklist])

colvar=[tree.node_n-int(i) for i in range(tree.node_n) ]
node=tree.getroot()




def haihai(node):
#     print("node",node.name)
    parentcolor=node.p_color
    children=node.child
    if children==[]:
        pass
    else:
#         print("children",[i.name for i in children])
        childcolor=colvar.copy()
        if parentcolor in childcolor:
            childcolor.remove(parentcolor)
        for child in children:
#             print("childname",child.name)
#             checklist.remove(child)
            color=childcolor.pop()
            child.p_color=color
            if color not in colorlist :
                colorlist.append(color)
            haihai(child)
            

haihai(node)

# print(colorlist)

print(len(colorlist))


for j in [tree.tree[i[1]].p_color for i in tree.list]:
    print(j)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A,B = [0]*(N-1),[0]*(N-1)
for i in range(N-1):
    array = list(map(int,input().split()))
    A[i] = array[0]
    B[i] = 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)
for child in sorted(children.keys()):
    used = [False]*100000
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.index(False)+1
        ans[j] = temp
        used[temp-1] = True
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)
for child in sorted(children.keys()):
    used = [False]*100000
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.index(False)+1
        ans[j] = temp
        used[temp-1] = True
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
import numpy as np
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
for child in sorted(children.keys()):
    used = np.zeros((100000),dtype="bool")
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.argmin()+1
        ans[j] = temp
        used[temp-1] = True
ans2 = [ans[b] for b in B]
print(max(ans2))
for a in ans2:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
edges = []
count = np.zeros(N)
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = int(np.max(count))

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]
resolved = set()

for _ in range(N-1):
  id = np.argmax(count)
  count[id] = 0
  id += 1
  for k, [i,j] in enumerate(edges):
    if k in resolved or (i != id and j != id):
      continue
    for l in range(MAX):
      c = l+1
      if c in used[i-1] or c in used[j-1]:
        continue
      used[i-1].add(c)
      used[j-1].add(c)
      color[k] = c
      resolved.add(k)
      break

print(MAX)
for i in color:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
edges = []
count = np.zeros(N)
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = int(np.max(count))

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]
for _ in range(N-1):
  id = np.argmax(count)
  count[id] = 0
  id += 1
  for k, [i,j] in enumerate(edges):
    if (i != id and j != id) or color[k] != 0:
      continue
    for l in range(MAX):
      c = l+1
      if c in used[i-1] or c in used[j-1]:
        continue
      used[i-1].add(c)
      used[j-1].add(c)
      color[k] = c
      break

print(MAX)
for i in color:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
def ABC146D_ColoringEdge():
    N = int(input())

    graph = [[] for i in range(0, N)]
    edge = [0] * (N - 1)
    for i in range(0, N - 1):
        frm, to = list(map(int, input().split()))
        frm -= 1
        to -= 1
        graph[frm].append(i)
        graph[to].append(i)
    
    maxColor = 0
    for node in graph:
        usedColor = []
        maxColor = max(maxColor, len(node))
        for eNo in node:
            if edge[eNo] is not 0:
                usedColor.append(edge[eNo])
        
        nowColor = 1
        for eNo in node:
            if edge[eNo] is 0:
                while nowColor in usedColor:
                    nowColor += 1

                edge[eNo] = nowColor
                usedColor.append(nowColor)

    print(maxColor)
    
    for color in edge:
        print(color)


def main():
    ABC146D_ColoringEdge()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = {1:1}
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette.copy()
    if parent > 0:
        del current_palette[colors[parent]]
    for edge in edges[root]:
        if edge in colors:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette.popitem()[0]
        else:
            color = len(palette) + 1
            palette[color] = 1
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = {1:1}
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette.copy()
    if parent > 0:
        del current_palette[colors[parent]]
    for edge in edges[root]:
        if colors[edge]:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette.popitem()[0]
        else:
            color = len(palette) + 1
            palette[color] = 1
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = [1]
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

for edge in range(1,N):
    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette[:]
    if parent > 0:
        del current_palette[current_palette.index(colors[parent])]
    for edge in edges[root]:
        if colors[edge]:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette[0]
            del current_palette[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = [1]
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

for edge in range(1,N):
    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette[:]
    if parent > 0:
        del current_palette[current_palette.index(colors[parent])]
    for edge in edges[root]:
        if colors[edge]:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette[0]
            del current_palette[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

color_edges(0, 1)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
    for i in ends[root]:
        if i == parent:
            continue
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

"""
for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color
"""

color_edges(0, 1)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Time Limit Exceeded

Solution code:
def solve(n, a, b): 
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0 
        G[v, u] = 0 
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    for u, vs in E.items():
        for v in vs: 
            if G[u, v] != 0:
                continue
            for c in range(1, k+1):
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c 
                    G[v, u] = c 
                    break
    res = [k] 
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
INF = 10**9


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().strip())
a=[0]*(N-1)
b=[0]*(N-1)
flag=[[0 for i in range(N+1)] for j in range(N+1)] #[colors]*points
color=[]

for i in range(len(a)):
    a[i],b[i]=list(map(int,input().strip().split()))

for i in range(len(a)):# for points
    for c in range(len(color)+1):# for colors
        if flag[a[i]][c] == 0 and flag[b[i]][c] == 0:
            flag[a[i]][c]=1
            flag[b[i]][c]=1
            color.append(c)
            break

print(max(color)+1)
for i in color:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input().strip())
a=[0]*(N-1)
b=[0]*(N-1)
flag=[[0 for i in range(N+1)] for j in range(N+1)] #[colors]*points
color=[]
#counter=1

for i in range(len(a)):
    a[i],b[i]=list(map(int,input().strip().split()))

for i in range(len(a)):# for points
    for c in range(N+1):# for colors
        if flag[a[i]][c] == 0 and flag[b[i]][c] == 0:
#            color.append(counter)
            flag[a[i]][c]=1
            flag[b[i]][c]=1
            color.append(c)
            break
#        counter +=1
#        else:
#            counter +=1
#            color.append(counter)
#        flag[a[i]][counter]=1
#        flag[b[i]][counter]=1

print(max(color)+1)
for i in color:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

TopList = []#頂点から最少の色の数を求める
GList = []#i + 1行目の保存
ColorList = []

for i in range(0, N):
    if i != 0:
        GList.append([0, 0])
    TopList.append(0)
    ColorList.append([])

for i in range(0, N - 1):
    A, B = map(int, input().split())
    TopList[A - 1] += 1
    TopList[B - 1] += 1
    GList[i][0] = A
    GList[i][1] = B
print(np.amax(TopList))

AllList = []
for i in range(0, len(GList)):
    MixList = list(set(ColorList[GList[i][0] - 1] + ColorList[GList[i][1] - 1]))
    LackList = list(set(MixList) ^ set(AllList))
    if len(MixList) == 0:
        ColorList[GList[i][0] - 1].append(1)
        ColorList[GList[i][1] - 1].append(1)
        AllList.append(1)
        print(1)
    elif len(LackList) == 0:
        INPUT = np.amax(AllList) + 1
        ColorList[GList[i][0] - 1].append(INPUT)
        ColorList[GList[i][1] - 1].append(INPUT)
        AllList.append(INPUT)
        print(INPUT)
    else:
        INPUT = np.amin(LackList)
        ColorList[GList[i][0] - 1].append(INPUT)
        ColorList[GList[i][1] - 1].append(INPUT)
        AllList.append(INPUT)
        print(INPUT)

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