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

class Node:
    def __init__(self, val):
        self.val = val
        self.adj = []
        self.pec = 0

n = int(input())
ab = []
nodes = [None] * n
cntMap = {}

def addCount(v1):
    if v1 not in cntMap:
        cntMap[v1] = 1
    else:
        cntMap[v1] += 1

for i in range(n-1):
    v1, v2 = map(int, input().split())
    addCount(v1)
    addCount(v2)
    ab.append([v1, v2])
    nodeAidx = v1-1
    nodeBidx = v2-1
    nodeA = None
    nodeB = None
    if nodes[nodeAidx] is None:
        nodeA = Node(v1)
        nodes[nodeAidx] = nodeA
    else:
        nodeA = nodes[nodeAidx]
    if nodes[nodeBidx] is None:
        nodeB = Node(v2)
        nodes[nodeBidx] = nodeB
    else:
        nodeB = nodes[nodeBidx]
    nodeA.adj.append(nodeB)

#print(ab)
#print(nodes)
root = nodes[0]
nodes[1].pec = 1
q = deque()
q.append(root)

temp = list(cntMap.values())
temp.sort()
maxV = temp[-1]
used = set()
edgeMap = {}

print(maxV)

while q:
    used.clear()
    node = q.popleft()
    pec = node.pec
    used.add(pec)

    for i in range(len(node.adj)):
        a = node.adj[i]
        for j in range(1, maxV+1):
            if j not in used:
                a.pec = j
                used.add(j)
                break

        edgeMap[(node.val, a.val)] = a.pec
        q.append(a)

for i in range(n-1):
    key = (ab[i][0], ab[i][1])
    print(edgeMap[key])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
e = []
queue = deque([])
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(temp)
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
ans = [[0] * N for _ in range(N)]
def bfs(x):
    for i in G[x]:
        if ans[x][i] ==0 and ans[i][x] == 0:
            queue.append(i)
            for k in range(1,N):
                if k not in nuc[x] and k not in nuc[i]:
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    break
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m[0]][m[1]])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])

a_list = []
b_list = []
edge_dict = {}
edge_list = []

for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

# ルートを探す
root = list(set(a_list) - set(b_list))[0]

node_dict = {}
for node_id in list(set(a_list) | set(b_list)):
    node_data = dict(node_id=node_id, parent=None, children=[])
    node_dict[node_id] = node_data

for edge in edge_list:
    p, c = edge
    node_dict[p]["children"].append(c)
    node_dict[c]["parent"] = p

max_color_degree = -float("inf")
for k, v in node_dict.items():
    d = len(v["children"])
    # 親がいない場合は、親の数も含める
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_SET = set(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color_set = set([parent_edge_color])
    ok_color_list = list(COLOR_SET - ng_color_set)

    for child in next_node_list:
        color = ok_color_list.pop(0)
        edge_dict[(parent, child)]["color"] = color
    return


parent = root
next_node_list = node_dict[root]["children"]
ng_color_set = set()
ok_color_list = list(COLOR_SET - ng_color_set)
next_next_node_list = []

for child in next_node_list:
    color = ok_color_list.pop(0)
    edge_dict[(parent, child)]["color"] = color
    next_next_node_list += node_dict[child]["children"]

while next_node_list:
    next_next_node_list = []
    for child in next_node_list:
        color_edge(child)
        next_next_node_list += node_dict[child]["children"]
    next_node_list = next_next_node_list

color_list = []
for edge in edge_list:
    a, b = edge
    color_list.append(edge_dict[(a, b)]["color"])

ans = "\n".join([str(x + 1) for x in color_list])

print(len(COLOR_SET))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
e = []
queue = deque([])
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(temp)
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
ans = [[0] * N for _ in range(N)]
def bfs(x):
    for i in G[x]:
        if ans[x][i] ==0 and ans[i][x] == 0:
            queue.append(i)
            for k in range(N):
                if k not in nuc[x] and k not in nuc[i]:
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    break
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m[0]][m[1]])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[]
l1=[[] for i in range(n+1)]
d=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l1[a].append(b)
  l1[b].append(a)
  l.append([a,b])
max1=0
for i in l1:
  if max1<len(i):
    max1=len(i)
def dfs(x,y):#xは頂点yは入ってくる色
  l2=l1[x]
  now=1
  for i in range(len(l2)):
    if d[x][l2[i]]!=0:
      pass
    else:                
      if now==y:
        now+=1
      d[x][l2[i]]=now
      d[l2[i]][x]=now
      dfs(l2[i],now)
      now+=1
print(max1)
dfs(1,0)
for i in range(len(l)):
  print(d[l[i][0]][l[i][1]])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b,i))
    graph[b-1].append((a,i))
    
ans = [0]*(N-1)
ten_col =[[] for i in range(N)]

def dfs(start,now):
    new_col = 1
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            if new_col in ten_col[now-1]:
                new_col += 1
            ten_col[now-1].append(new_col)
            ten_col[future-1].append(new_col)
            ans[i] = new_col
            new_col += 1

            dfs(now,future)
            
dfs(-1,1)
print(max(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

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

me = 0
for i in range(n):
    me = max(me, len(e[i]))
print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
edges = [tuple([int(i) for i in input().split()]) for _ in range(n - 1)]
graph = [0] + [[] for _ in range(n)]

for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

max_color_index = 1
def bfs(graph, dist, queue, colors, color_map):
    global max_color_index
    while queue:
        current = queue.pop(0)
        children = graph[current]
        for child in children:
            if dist[child] != -1:
                continue
            else:
                dist[child] = dist[current] + 1

                color_index = colors[current].index(0, 1)
                max_color_index = max(max_color_index, color_index)
                colors[current][color_index] = child
                colors[child][color_index] = current

                e = (min(child, current), max(child, current))
                if e not in color_map:
                    color_map[e] = color_index

                queue.append(child)

dist = [0] + [-1] * n
dist[1] = 0
queue = [1]
# First level index: source
# Second level index: color
# Value: dest
colors = [0] + [[0] * (n + 1) for _ in range(n)]
color_map = {}
bfs(graph, dist, queue, colors, color_map)

print(max_color_index)
for e in edges:
    print(color_map[e])

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

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


def dfs(node, pc):
    colors = set()
    colors.add(pc)

    for to, idx in edge[node]:
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            dfs(to, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [[] for _ in range(N+1)]
    edges = [[-1]*(N+1) for _ in range(N+1)]
    
    ## 全てのNodeは親は一つだけ

    for i in range(N-1):
        h[a[i]].append((b[i],i))
        h[b[i]].append((a[i],i))
        edges[a[i]][b[i]] = i
        edges[b[i]][a[i]] = i

    queue = deque([1])

    ## 頂点iの親を格納
    parents = [-1]*(N+1)
    parents[1] = 0

    while queue:
        q = queue.pop()

        for child,_ in h[q]:
            if child != q and parents[child] == -1:
                parents[child] = q
                queue.append(child)

    answer = [0]*(N-1)
    max_color = max(len(a) for a in h)
    queue = deque([1])

    while queue:
        color = 1 
        q = queue.popleft()
        parent_edge = edges[parents[q]][q]
        ng_color = answer[parent_edge]
        
        for node, j in h[q]:
            ##もう埋まっているか、親と一緒
            if answer[j] > 0 or q == node:
                continue
            
            if color==ng_color:
                color += 1    

            answer[j] = color
            color+=1
            queue.append(node)

    print(max_color)
    for a in answer:
        print(a)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a_list=[]
b_list=[]
graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b,i))
    graph[b-1].append((a,i))
    
ans = [0]*(N-1)
ten_col =[[] for i in range(N)]
def dfs(start,now):
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            new_col = 1
            while new_col in ten_col[now-1]:
                new_col += 1
            ten_col[now-1].append(new_col)
            ten_col[future-1].append(new_col)
            ans[i] = new_col

            dfs(now,future)
            
dfs(-1,1)
print(max(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a_list=[]
b_list=[]
graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b,i))
    graph[b-1].append((a,i))
    
ans = [0 for i in range(N-1)]
ten_col = [[] for i in range(N)]
def dfs(start,now):
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            new_col = 1
            while new_col in ten_col[now-1]:
                new_col += 1
            ten_col[now-1].append(new_col)
            ten_col[future-1].append(new_col)
            ans[i] = new_col

            dfs(now,future)
            
dfs(-1,1)
print(max(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [[] for _ in range(N+1)]
    edges = [[-1]*(N+1) for _ in range(N+1)]
    
    ## 全てのNodeは親は一つだけ

    for i in range(N-1):
        h[a[i]].append((b[i],i))
        h[b[i]].append((a[i],i))
    
    ## node二つ与えたときにその間の辺
    for i in range(N-1):
        edges[a[i]][b[i]] = i
        edges[b[i]][a[i]] = i

    queue = deque([1])

    ## 頂点iの親を格納
    parents = [-1]*(N+1)
    parents[1] = 0

    while queue:
        q = queue.pop()

        for child,_ in h[q]:
            if child != q and parents[child] == -1:
                parents[child] = q
                queue.append(child)

    answer = [0]*(N-1)
    max_color = max(len(a) for a in h)
    queue = deque([1])

    while queue:
        color = 1 
        q = queue.popleft()
        parent_edge = edges[parents[q]][q]
        ng_color = answer[parent_edge]
        
        for node, j in h[q]:
            ##もう埋まっているか、親と一緒
            if answer[j] > 0 or q == node:
                continue
            
            if color!=ng_color or q == 1:
                answer[j] = color
            else:
                color+=1
                answer[j] = color
            color+=1

            queue.append(node)

    print(max_color)
    for a in answer:
        print(a)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a_list=[]
b_list=[]
graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b,i))
    graph[b-1].append((a,i))
    
ans = [0 for i in range(N-1)]
ten_col = [[] for i in range(N)]
def dfs(start,now):
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            new_col = 1
            while True:
                if new_col not in ten_col[now-1]:
                    ten_col[now-1].append(new_col)
                    ten_col[future-1].append(new_col)
                    ans[i] = new_col
                    break
                else:
                    new_col += 1
            dfs(now,future)
            
dfs(-1,1)
print(max(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [[] for _ in range(N+1)]
    edges = [[-1]*(N+1) for _ in range(N+1)]
    
    ## 全てのNodeは親は一つだけ

    for i in range(N-1):
        h[a[i]].append((b[i],i))
        h[b[i]].append((a[i],i))
    
    ## node二つ与えたときにその間の辺
    for i in range(N-1):
        edges[a[i]][b[i]] = i
        edges[b[i]][a[i]] = i

    queue = deque([1])

    ## 頂点iの親を格納
    parents = [-1]*(N+1)
    parents[1] = 0

    while queue:
        q = queue.pop()

        for child,_ in h[q]:
            if parents[child] == -1:
                parents[child] = q
                queue.append(child)


    answer = [0]*(N-1)
    max_color = max(len(a) for a in h)
    color = list(range(1,max_color+1))
    queue = deque([1])

    while queue:
        color_index = 0 
        q = queue.popleft()

        parent = parents[q]
        parent_edge = edges[parent][q]
        
        for node, j in h[q]:
            ##もう埋まっているか、親と一緒
            if answer[j] > 0 or q == node:
                continue
            
            if answer[parent_edge] != color[color_index] or q == 1:
                answer[j] = color[color_index]
            else:
                color_index+=1
                answer[j] = color[color_index]
            color_index+=1

            queue.append(node)


    print(max_color)
    for a in answer:
        print(a)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a_list=[]
b_list=[]

for i in range(N-1):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)

graph = [[] for i in range(N)]
for i in range(N-1):
    graph[a_list[i]-1].append((b_list[i],i))
    graph[b_list[i]-1].append((a_list[i],i))
    
ans = [0 for i in range(N-1)]
ten_col = [[] for i in range(N)]
def dfs(start,now):
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            new_col = 1
            while True:
                if new_col not in ten_col[now-1]:
                    ten_col[now-1].append(new_col)
                    ten_col[future-1].append(new_col)
                    ans[i] = new_col
                    break
                else:
                    new_col += 1
            dfs(now,future)
            
dfs(-1,1)
print(max(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():

    """
    # color: 親と自らを繋ぐ辺の色
    # now: 現在地
    """
    def dfs(color,now):
        # 現在地が葉のとき
        if not now in a:
            return

        # 現在地から伸びる辺のインデックス
        index = [i for i in range(N-1) if now == a[i]]

        # 子ノードに伸びる辺を色塗り
        number = 1
        for i in index:
            if number == color:
                number += 1
            K[i] = number
            # 子ノードで色塗り開始
            dfs(number, b[i])
            number += 1

    N = int(input())
    a = [0] * (N-1)
    b = [0] * (N-1)
    for i in range(N-1):
        a[i],b[i] = map(int,input().split())
    # 辺の色
    K = [0] * (N-1)
    dfs(0,min(a))
    print(len(set(K)))
    for i in K:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if ec[x[0]] == 0 and v in x[1]]:
        for c in range(1, N):
            if c not in colors:
                ec[idx] = c
                colors.add(c)
                break

        nv = e[0] if e[1] == v else e[1]
        dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=[1]

while stack:
    a=stack[-1]
    if not P[a]:
        stack.pop()
        continue
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        P[b].remove(a)
        if P[b]:
            stack.append(b)
        break
    P[a].remove(b)


print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Submission status: Time Limit Exceeded

Solution code:
import queue
N = int(input())
br = []
alist = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    br.append([a, b])
    alist[a].append(b)
    alist[b].append(a)

q = queue.Queue()
ans = dict()
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[str(sorted([n[0], nxt]))] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
for k in br:
    print(ans[str(k)])

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in enumerate(edge):
        if v not in e:
            continue
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = [True] * N
    colors[pc] = False

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for idx_c, c in enumerate(colors):
                if c:
                    ec[idx] = idx_c
                    colors[idx_c] = False
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():

    """
    # color: 親と自らを繋ぐ辺の色
    # now: 現在地
    """
    def dfs(color,now):
        # 現在地が葉のとき
        if not now in a:
            return

        # 現在地から伸びる辺のインデックス
        index = [i for i in range(N-1) if now == a[i]]

        # 子ノードに伸びる辺を色塗り
        number = 1
        for i in range(len(index)):
            if number == color:
                number += 1
            K[index[i]] = number
            # 子ノードで色塗り開始
            dfs(number, b[index[i]])
            number += 1

    N = int(input())
    a = [0] * (N-1)
    b = [0] * (N-1)
    for i in range(N-1):
        a[i],b[i] = map(int,input().split())
    # 辺の色
    K = [0] * (N-1)
    dfs(0,min(a))
    print(len(set(K)))
    for i in K:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

ans = [1]*(N-1)
q = collections.deque([(id, 0)])
print(max_e)
ans = [[0]*N for i in range(N)]
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        ans[x][y] = i
        ans[y][x] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

for a, b in ab:
    print(ans[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import Counter
 
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
 
 
n = int(input())
 
arr = []
idx = 0
max = 0
for i in range(n - 1):
    arr.append([])
    arr[i] = [int(x) for x in input().split()]
    idx = 1
    t = 0
    while True and len(arr) > 1:
        if ((arr[i][0] == arr[t][0]) or (arr[i][0] == arr[t][1]) or (arr[i][1] == arr[t][0]) or (arr[i][1] == arr[t][1])) and idx == arr[t][2]:
            idx += 1
            t = 0
        else:
            t += 1
        if t == len(arr) - 1:
            break
    arr[i].append(idx)
    if max < idx:
        max = idx

 
print(max)
for i in range(len(arr)):
    print(arr[i][2])

Submission status: Time Limit Exceeded

Solution code:
import sys, math

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

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        for tsugi in G[ima]:
            t = 1
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
#隣接リスト
adjacent_list = [[] for i in range(n+1)]
#入力されたデータを保存しておくやつ
data = []
#最終的に色を入れておくやつ。
#edgedata[12] => 1->2の辺の色を入れておく
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#つながってるノードが一番多いやつを保存しておく
max_node = 0
#探索が終わったやつを入れる
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i
#kには色の種類を入れる
k = len(adjacent_list[max_node])
#print("k => {}".format(k))
def dfs(node, num):
    #隣接リストの中身を、つながってるノード順にソート
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    #さっきつかったいろは使わないようにする
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        #まだ見てなかったら、dfsを掛ける
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            #小さいほうから大きいほうに文字を並べ、ハッシュに値を保存
            #print("{}".format(color_list))
            #print("c_i =>{}  node =>{}".format(c_i,node))

            edgedata[(s, t)] = color_list[c_i]
            #color_list[c_i]は使ったので、使った色として引数で渡す。
            dfs(i, color_list[c_i])
            #この色は使ったから、一個ずらす
            c_i += 1
#一番のノードを根とし、dfsをかける
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])
#output k

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())

#n_list = [[] for i in range(N)]
d = [0] * N
connect = [[-1 for i in range(N)] for j in range(N)]
for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    connect[a][b] = i
    connect[b][a] = i
    d[a] += 1
    d[b] += 1

max_index = -1
max_degree = -1
for i in range(N):
    if d[i] > max_degree:
        max_degree = d[i]
        max_index = i

colors = [0] * (N-1)

root = max_index

def paint(node, parent_edge_id):
    tmp_color = 1
    for i in range(N):
        edge_id = connect[node][i]
        if edge_id == -1:
            continue
        if edge_id != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge_id] = tmp_color
            paint(i, edge_id)
            tmp_color += 1

    
try:
    paint(root, -1)
except TypeError:
    print(0)
print(max_degree) # color num    a
for i in range(N-1):
    print(colors[i])