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

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = {color for color in range(1, k + 1)}
usedcolor_sets = [set() for _ in range(N)]
colored = {}

for v in range(N):
  unused_colors = colors - usedcolor_sets[v]  
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = unused_colors.pop()
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor_sets[edge].add(color)

print(k)

for a, b in edges:
  print(colored[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
#color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
color =0
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            #color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
#color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            #color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
#color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            #color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100010)


class Tree:
    def __init__(self, root):
        self.__root = root
        self.__children = {root: []}
        self.__parent = {root: -1}

    def get_root(self):
        return self.__root

    def get_children(self, node):
        return self.__children[node]

    def add_child(self, node, child):
        self.__children[node].append(child)
        self.__children[child] = []
        self.__parent[child] = node

    def get_parent(self, node):
        return self.__parent[node]


N = int(input())

tree = Tree(1)

colors_dict = {1: -1}
colors = 0

input_list = []
li = []
for n in range(N - 1):
    a, b = map(int, input().split())
    input_list.append([a, b])
    try:
        tree.add_child(a, b)
    except:
        try:
            tree.add_child(b, a)
        except:
            li.append([a, b])
while True:
    if li == []:
        break
    a, b = li.pop(0)
    try:
        tree.add_child(a, b)
    except:
        try:
            tree.add_child(b, a)
        except:
            li.append([a, b])

li2 = [1]
while True:
    if li2 == []:
        break
    node = li2.pop()
    children = tree.get_children(node)
    l = len(children)
    if l == 0:
        continue
    col = 1
    i = 0
    while True:
        if i >= l:
            break
        if col == colors_dict[node]:
            col += 1
            continue
        child = children[i - 1]
        colors_dict[child] = col
        colors = max(colors, col)
        i += 1
        col += 1
        li2.append(child)

print(colors)
for edge in input_list:
    a, b = edge
    if tree.get_parent(b) == a:
        print(colors_dict[b])
    else:
        print(colors_dict[a])

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    def __init__(self, root):
        self.__root = root
        self.__children = {root: []}
        self.__parent = {root: -1}

    def get_root(self):
        return self.__root

    def get_children(self, node):
        return self.__children[node]

    def add_child(self, node, child):
        self.__children[node].append(child)
        self.__children[child] = []
        self.__parent[child] = node

    def get_parent(self, node):
        return self.__parent[node]


N = int(input())
tree = Tree(1)
input_list = []
li = []
for n in range(N - 1):
    a, b = map(int, input().split())
    input_list.append([a, b])
    try:
        tree.add_child(a, b)
    except:
        try:
            tree.add_child(b, a)
        except:
            li.append([a, b])
while True:
    if li == []:
        break
    a, b = li.pop(0)
    try:
        tree.add_child(a, b)
    except:
        try:
            tree.add_child(b, a)
        except:
            li.append([a, b])

colors_dict = {}

def color(node, colors):
    children = tree.get_children(node)
    l = len(children)
    if l == 0:
        return colors
    if node == tree.get_root():
        for i in range(l):
            colors_dict[children[i]] = i + 1
            colors = max(colors, i + 1, color(children[i], colors))
        return colors
    col = 1
    i = 0
    while True:
        if i >= l:
            break
        if col == colors_dict[node]:
            col += 1
            continue
        colors_dict[children[i]] = col
        colors = max(colors, col, color(children[i], colors))
        i += 1
        col += 1
    return colors
colors = color(1, 0)
print(colors)
for edge in input_list:
    a, b = edge
    if tree.get_parent(b) == a:
        print(colors_dict[b])
    else:
        print(colors_dict[a])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
for val in AB:
    x, y = val
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
#print(dijkstra_heap(0))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)

colors = [[0]*N for _ in range(N)]
color_list = list(range(1, mledge+1))

que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for edgei in edge[index]:
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[edgei][index] = color
                colors[index][edgei] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for ab in AB:
    a, b = ab
    print(colors[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
for val in AB:
    x, y = val
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
#print(dijkstra_heap(0))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)

color = [[0]*N for _ in range(N)]
color_set = set(range(1, mledge+1))

stack = deque()
stack.append([root])
while stack[0]:
    nstack = []
    cstack = stack.pop()
    #print('cstack:', cstack)
    for index in cstack:
        seen[index] = 1
        for edgei in edge[index]:
            if seen[edgei] == 0:
                nstack.append(edgei)
                ncolor = (color_set - set(color[index])).pop()
                color[edgei][index] = ncolor
                color[index][edgei] = ncolor
    stack.append(nstack)

#pri(color)

for ab in AB:
    a, b = ab
    print(color[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

N = int(input())
count = [[] for _ in range(N)]
inputs = []

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

K = 0
for c in count:
    K = max(K, len(c))
print(K)

def dfs(root, count):
    done = [-1 for _ in range(N)]
    done[root] = 0
    info = []
    d = deque([root])
    r = d.pop()
    childs = count[r]
    tmp = 1
    for c in childs:
        if done[c] == -1:
            d.append([c, r, tmp])
            tmp += 1
            done[c] += 1
    while d:
        data = d.pop()
        info.append(data)
        childs = count[data[0]]
        tmp = 1
        for c in childs:
            if done[c] == -1:
                if tmp != data[2]:
                    d.append([c, data[0], tmp])
                else:
                    tmp += 1
                    d.append([c, data[0], tmp])
                tmp += 1
                done[c] += 1
    return info

info = dfs(0, count)
info_new = [[sorted([i[0], i[1]]), i[2]] for i in info]

for i in inputs:
    for k in info_new:
        if i == k[0]:
            print(k[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    if len(connected[temp[0]-1]) > 1:
        used = deque(range(1,colors+1))
        used.remove(ans[temp[1]])
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                ans[edge[1]] = used.popleft()
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    used = deque(range(1,colors+1))
    used.remove(ans[temp[1]])
    if len(connected[temp[0]-1]) > 1:
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                ans[edge[1]] = used.popleft()
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


# v-v2間の色をぬる
def dfs(v, parent):
    # v-parent間で使用済みの色は使えない
    if v < parent:
        palette = [i for i in range(k, 0, -1) if i != colors[(v, parent)]]
    else:
        palette = [i for i in range(k, 0, -1) if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        if v2 < v:
            colors[(v2, v)] = color
        else:
            colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v

def dfs(v, parent):
    palette = [i for i in range(1, k+1) if i != colors[(v, parent)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v, v2)] = color
        colors[(v2, v)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
a_max = 0
class Node:
    def __init__(self):
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c


def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node() for _ in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    # a_max = 0

    def s_node(node_num, prev_c):
        global a_max
        el = nodes[node_num-1].edge

        # print("node_num:{} el:{}".format(node_num, el))
        if len(el)>0:
            if prev_c not in range(1,len(el)+1):
                c_list = range(1,len(el)+1)
                a_max = max(a_max, len(el))
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
                a_max = max(a_max, len(el)+1)
            
            # print("c_list:{} prev_c:{}".format(c_list, prev_c))

            for node_n, c_ in zip(el, c_list):
                # 親の頂点に対する処理
                nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
                # 子の頂点に対する処理
                nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
                s_node(node_n, c_)

    s_node(1,0)

    print(a_max)
    # ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans = (nodes[ai-1].color[bi])
        else:
            ans = (nodes[bi-1].color[ai])
        print(ans)
    # print(max(ans))
    # [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c




def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node(num+1) for num in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    def s_node(node_num, prev_c):
        el = nodes[node_num-1].edge
        # print("node_num:{} el:{}".format(node_num, el))
        if len(el)>0:
            if prev_c not in range(1,len(el)+1):
                c_list = range(1,len(el)+1)
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
            
            # print("c_list:{} prev_c:{}".format(c_list, prev_c))

            for node_n, c_ in zip(el, c_list):
                # 親の頂点に対する処理
                nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
                # 子の頂点に対する処理
                nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
                s_node(node_n, c_)

    s_node(1,0)


    ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans.append(nodes[ai-1].color[bi])
        else:
            ans.append(nodes[bi-1].color[ai])

    print(max(ans))
    [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

Solution code:
# Problem D - Coloring Edges on Tree

from collections import deque

# input
N = int(input())
node_list = {} # 隣接リストの作成
color_count_list = [0]*(N+1)
ans_list = []
for i in range(N-1):
    a, b = map(int, input().split())
    if a in node_list:
        node_list[a].append(b)
    else:
        node_list[a] = [b]
    color_count_list[a] += 1
    color_count_list[b] += 1
    ans_list.append([a, b])

# initialization
color_list = [[0]*(N+1) for i in range(N+1)]
color_max_count = max(color_count_list)

# bfs search
visit_queue = deque([[-1, 1]]) # [[既に使った色], 遷移ノード]
while len(visit_queue)>0:
    p = visit_queue.popleft()

    used_color = p[0]
    if p[1] in node_list:
        nodes = node_list[p[1]]
        nodes_len = len(nodes)
        color_num = 1
        if nodes_len>=1:
            coloring_count = 0
            while coloring_count<nodes_len:
                if color_num==used_color:
                    color_num += 1
                    continue
                color_list[p[1]][nodes[coloring_count]] = color_num
                color_list[nodes[coloring_count]][p[1]] = color_num
                # queue insert
                visit_queue.append([color_num, nodes[coloring_count]])
                # color update
                coloring_count += 1
                color_num += 1

# output
print(color_max_count)
for a in ans_list:
    print(color_list[a[0]][a[1]])

Submission status: Time Limit Exceeded

Solution code:
# Problem D - Coloring Edges on Tree

# input
N = int(input())
node_list = {} # 隣接リストの作成
color_count_list = [0]*(N+1)
ans_list = []
for i in range(N-1):
    a, b = map(int, input().split())
    if a in node_list:
        node_list[a].append(b)
    else:
        node_list[a] = [b]
    color_count_list[a] += 1
    color_count_list[b] += 1
    ans_list.append([a, b])

# initialization
color_list = [[0]*(N+1) for i in range(N+1)]
color_max_count = max(color_count_list)

# bfs search
visit_queue = [[-1, 1]] # [[既に使った色], 遷移ノード]
while len(visit_queue)>0:
    p = visit_queue.pop(0)

    used_color = p[0]
    if p[1] in node_list:
        nodes = node_list[p[1]]
        nodes_len = len(nodes)
        color_num = 1
        if nodes_len>=1:
            coloring_count = 0
            while coloring_count<nodes_len:
                if color_num==used_color:
                    color_num += 1
                    continue
                color_list[p[1]][nodes[coloring_count]] = color_num
                color_list[nodes[coloring_count]][p[1]] = color_num
                # queue insert
                visit_queue.append([color_num, nodes[coloring_count]])
                # color update
                coloring_count += 1
                color_num += 1

# output
print(color_max_count)
for a in ans_list:
    print(color_list[a[0]][a[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
E = {}
A = []
for _ in range(N-1):
    a,b = map(int,input().split())
    A.append((a,b))
    G[a].append(b)
    G[b].append(a)
    E[(a,b)] = 0
hist = [0 for _ in range(N+1)]
heap = deque([1])
c = 1
for y in G[1]:
    E[(1,y)]=c
    c += 1
K = c-1
hist[1]=1
while heap:
    x = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            K = max(K,len(G[y]))
            col = [0 for _ in range(K+1)]
            for z in G[y]:
                if y<z:
                    col[E[(y,z)]]=1
                else:
                    col[E[(z,y)]]=1
            cur = 1
            for z in G[y]:
                if y<z and E[(y,z)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(y,z)]=i
                            col[i]=1
                            cur = i+1
                            break
                elif z<y and E[(z,y)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(z,y)]=i
                            col[i]=1
                            cur = i+1
                            break
            heap.append(y)
            hist[y]=1
print(K)
for e in A:
    print(E[e])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge = [[] for _ in range(N + 1)]
E = [-1] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))

cmax = max(len(e) for e in edge)
cand = set(i for i in range(cmax))
seenV = [-1] * (N + 1)
seenE = [-1] * N
node = [(1, cand)]
seenV[1] = 1
while node:
    s, color = node.pop()
    x = 0
    for t, i in edge[s]:
        if seenV[t] != -1:
            continue
        if seenE[i] != -1:
            continue
        seenV[t] = 1
        c = list(color)[x]
        seenE[i] = c
        node.append((t, cand - {c}))
        x += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(u, p):
    que = deque([])
    que.append((u, p))

    while que:
        (v, p) = que.popleft()
        pnum = c[p][v]
        if pnum != 1:
            nnum = 1
        else:
            nnum = pnum+1

        for nv in G[v]:
            if nv == p:
                continue
            c[v][nv] = nnum
            maxc[0] = max(maxc[0], nnum)
            if nnum + 1 == pnum:
                nnum += 2
            else:
                nnum += 1
            que.append((nv,v))
    return


n = int(input())
G = [[]*(n+1) for _ in range(n+1)]
ab = []
for i in range(n-1):
    a, b = map(int, input().split())
    ab.append((a, b))
    G[a].append(b)
    G[b].append(a)
G[1].append(0)
G[0].append(1)

c = [[-1]*(n+1) for _ in range(n+1)]
c[0][1] = float('inf')
maxc = [-float('inf')]
bfs(1, 0)

print(maxc[0])
for a, b in ab:
    print(c[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(u, p):
    que = deque([])
    que.append((u, p))

    while que:
        (v, p) = que.popleft()
        pnum = c[p][v]
        if pnum != 1:
            nnum = 1
        else:
            nnum = pnum+1

        for nv in G[v]:
            if nv == p:
                continue
            c[v][nv] = nnum
            maxc[0] = max(maxc[0], nnum)
            if nnum + 1 == pnum:
                nnum += 2
            else:
                nnum += 1
            que.append((nv,v))
    return


n = int(input())
G = [[]*(n+1) for _ in range(n+1)]
ab = []
for i in range(n-1):
    a, b = map(int, input().split())
    ab.append((a, b))
    G[a].append(b)
    G[b].append(a)
G[1].append(0)
G[0].append(1)

c = [[-1]*(n+1) for _ in range(n+1)]
c[0][1] = float('inf')
maxc = [-float('inf')]
bfs(1, 0)

print(maxc[0])
for a, b in ab:
    print(c[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
    path = sorted(path, key=lambda x: x[1])
    path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
from queue import deque
q = deque([])
q.append(0)
ma = 0
while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
import queue
q = queue.Queue()
q.put(0)
ma = 0
while not q.empty():
    nord = q.get()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.put(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)