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:
import queue
N=int(input())
graph={i+1:[] for i in range(N)}
coloured=[0 for i in range(N+1)]
#↑0から始まってる（ただしkeyはそのまま使える）
node_list=[]

for i in range(N-1):
    node=tuple([int(thing) for thing in input().split(" ")])
    a=node[0]
    b=node[1]
    graph[a].append((b,i))
    graph[b].append((a,i))
# ranking=sorted(range(1,N),key=lambda x:len(graph[x]),reverse=True)

cc=1
ret=["" for i in range(N-1)]
def what_colour(cc,a_bit,b_bit):
    i=1
    while True:
        if (2**i&a_bit!=0) or (2**i&b_bit!=0):
            i=i+1
            continue
        else:
            if i>cc:
                cc=cc+1
            return i,cc
done_v=set()
q=queue.Queue()
q.put(1)
done_v.add(1)

while True:
    if q.empty():
        break
    else:
        i=q.get()
        for thing in graph[i]:
            j = thing[0]
            num = thing[1]

            c, cc = what_colour(cc, coloured[i], coloured[j])
            coloured[i] = coloured[i] + 2 ** c
            coloured[j] = coloured[j] + 2 ** c

            graph[j].remove((i, num))
            ret[num] = c
            if j not in done_v:
                q.put(j)
                done_v.add(j)


print(cc)
for thing in ret:
    print(thing)

    #処理したらgraphから消してcolourdにビットで（2**色）を加算。処理する前にビット積（&が0になるか確かめる）

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    # {node: {target: chain_index}}
    node_relation = {i: {} for i in range(NODE_N)}
    # {index: color}
    chain_color = {i: None for i in range(CHAIN_N)}
    # {node : set(color)}
    node_has_color = {i: set() for i in range(NODE_N)}
    passed = set()

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1
        node_relation[node][target] = i
        node_relation[target][node] = i

    bfs_queue = collections.deque([0])

    max_branch = 0
    while len(bfs_queue) > 0:
        node = bfs_queue.pop()
        leafs = node_relation[node]
        if max_branch < len(leafs):
            max_branch = len(leafs)

        for leaf, index in leafs.items():
            if leaf in passed:
                continue
            color = 1
            # search color
            # while color in node_has_color[node] or color in node_has_color[leaf]:
            while color in node_has_color[node]:
                color += 1
            node_has_color[node].add(color)
            node_has_color[leaf].add(color)
            chain_color[index] = color

            bfs_queue.appendleft(leaf)
            passed.add(node)

    # ret = [max_branch]
    print(max_branch)
    for i in range(CHAIN_N):
        print(chain_color[i])
        # ret.append(chain_color[i])
    # return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    # for r in ret:
    #     print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    # {node: {target: chain_index}}
    node_relation = {i: {} for i in range(NODE_N)}
    # {index: color}
    chain_color = {i: None for i in range(CHAIN_N)}
    # {node : set(color)}
    node_has_color = {i: set() for i in range(NODE_N)}
    passed = set()

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1
        node_relation[node][target] = i
        node_relation[target][node] = i

    bfs_queue = collections.deque([0])

    max_branch = 0
    while len(bfs_queue) > 0:
        node = bfs_queue.pop()
        leafs = node_relation[node]
        if max_branch < len(leafs):
            max_branch = len(leafs)

        for leaf, index in leafs.items():
            if leaf in passed:
                continue
            color = 1
            # search color
            # while color in node_has_color[node] or color in node_has_color[leaf]:
            while color in node_has_color[node]:
                color += 1
            node_has_color[node].add(color)
            node_has_color[leaf].add(color)
            chain_color[index] = color

            bfs_queue.appendleft(leaf)
            passed.add(node)

    ret = [max_branch]
    for i in range(CHAIN_N):
        ret.append(chain_color[i])
    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    # {node: {target: chain_index}}
    node_relation = {i: {} for i in range(NODE_N)}
    # {index: color}
    chain_color = {i: None for i in range(CHAIN_N)}
    # {node : set(color)}
    node_has_color = {i: set() for i in range(NODE_N)}
    passed = set()

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1
        node_relation[node][target] = i
        node_relation[target][node] = i

    bfs_queue = collections.deque([0])

    max_branch = 0
    while len(bfs_queue) > 0:
        node = bfs_queue.pop()
        leafs = node_relation[node]
        if max_branch < len(leafs):
            max_branch = len(leafs)

        for leaf, index in leafs.items():
            if leaf in passed:
                continue
            color = 1
            # search color
            while color in node_has_color[node] or color in node_has_color[leaf]:
                color += 1
            node_has_color[node].add(color)
            node_has_color[leaf].add(color)
            chain_color[index] = color

            bfs_queue.appendleft(leaf)
            passed.add(node)

    ret = [max_branch]
    for i in range(CHAIN_N):
        ret.append(chain_color[i])
    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)

Submission status: Time Limit Exceeded

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

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

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[[0]*N for i in range(N)]
for i in range(N-1):
    arr[val[i][0]-1].add(val[i][1]-1)
    arr[val[i][1]-1].add(val[i][0]-1)
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=set(colall)
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp.pop()
    colarr[min(flag,f)][max(flag,f)]=p
    col[f].add(p)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]
reach={flag}

for i in range(N-1):
    for t in que[i]:
        coltemp=colall^col[t]
        arrtemp=arr[t]^(reach&arr[t])
        que[i+1]=que[i+1] | arrtemp
        reach.add(t)
        for f in arrtemp:
            p=coltemp.pop()
            col[f].add(p)
            colarr[min(t,f)][max(t,f)]=p
print(colmax)
for i in range(N-1):
    print(colarr[val[i][0]-1][val[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import  deque

N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]
ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1]))
dicans = {}
while len(q) > 0:
    i, l = q.popleft()
    num = 1
    #print(f'頂点{i}に関しての色使い情報{Used[i]}')
    for t in range(ans1 + 1):
        if num in Used[i]:
            num += 1
        else:
            break

    for k in l:
        if k < i:
            continue
        #print(f'頂点{i}から{k}に色{num}を割り当て')
        Used[i].append(num)
        Used[k].append(num)
        dicans[(i, k)] = num
        while True:
            if num in Used[i]:
                num += 1
            else:
                break
        q.append((k, dic[k]))
print(ans1)
for a, b in A:
    print(dicans[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def main():
    dg = 10**9
    n=int(input())
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        g[a].append(b*dg+i)
        g[b].append(a*dg+i)
 
    check = [False for _ in range(n)]
    color=[defaultdict(int) for _ in range(n)]
    ans=[0 for _ in range(n-1)]
    que=deque([])
    que.append(0)
    while len(que)>0:
        x = que.popleft()
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i]//dg
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i]%dg]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    dg=10**9
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b*dg+i)
        g[b].append(a*dg+i)
    return n,g
    
def main():
    n,g=graph()
    dg = 10**9
 
    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=deque([])
    que.append(0)
    while len(que)>0:
        x = que.popleft()
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i]//dg
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i]%dg]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    dg=10**9
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b*dg+i)
        g[b].append(a*dg+i)
    return n,g
    
def main():
    n,g=graph()
    dg = 10**9
 
    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i]//dg
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i]%dg]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    dg=10**9
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b*dg+i)
        g[b].append(a*dg+i)
    return n,g
    
def main():
    n,g=graph()
    dg = 10**9

    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic={}
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i]//dg
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if j not in color[x]:
                        ans[g[x][i]%dg]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge["{},{}".format(ab[i][0],ab[i][1])])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    dg=10**9
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b*dg+i)
        g[b].append(a*dg+i)
    return n,g
    
def main():
    n,g=graph()
    dg = 10**9

    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i]//dg
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i]%dg]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 
def getColor(color,x,y,c):
	# print(color[x],color[y])
	if (y,x) in cd:
		cd[(x,y)] = cd[(y,x)]
		return 
	for i in range(1,c+1):
		if i not in color[x] and i not in color[y]:
			color[x].add(i)
			color[y].add(i)
			return i



n = int(input())
d = [0]*(n+1)
E = []
adj = defaultdict(list)
for i in range(n-1):
	x,y = map(int,input().split())
	E.append((x,y))
	adj[x].append(y)
	adj[y].append(x)
	d[x]+=1
	d[y]+=1

c = max(d)
print(c)
cd = {}
color = defaultdict(set)
for k,v in zip(adj.keys(),adj.values()):
	# print(k,v)
	for nbr in v:
		edge = (k,nbr)
		col = getColor(color,k,nbr,c)
		cd[edge] = col

for e in E:
	print(cd[e])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,g=graph()
    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        for i in range(len(g[x])):
            go = g[x][i][0]
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i][1]]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,g=graph()
    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        for i in range(len(g[x])):
            if check[g[x][i][0]]:
                continue
            else:
                que.append(g[x][i][0])
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i][1]]=j
                        color[x][j]=1
                        color[g[x][i][0]][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

# ノードの情報
node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

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)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a

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

max_color_degree = -float("inf")

# 最悪で10 ** 5
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)

    # 最悪で10 ** 5
    for child in next_node_list:
        color = ok_color_list.pop()
        edge_dict[(parent, child)]["color"] = color
    return


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

# 最悪で10 ** 5
for node in next_node_list:
    color = ok_color_list.pop()
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = next_parent_list[:]

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(len(COLOR_SET))
print(color_list_str)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge=[[0 for i in range(n+1)] for j in range(n+1)]
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge[num][G[num][i]]=color
                edge[G[num][i]][num]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge[num][G[num][i]]=color
                edge[G[num][i]][num]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge[ab[i][0]][ab[i][1]])

Submission status: Time Limit Exceeded

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

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

node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

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)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a

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

max_color_degree = -float("inf")

# 最悪で10 ** 5
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)

    # 最悪で10 ** 5
    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"]
ok_color_list = list(COLOR_SET)
next_next_node_list = []

# 最悪で10 ** 5
for node in next_node_list:
    color = ok_color_list.pop(0)
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = next_parent_list[:]

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(len(COLOR_SET))
print(color_list_str)

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 = {}

# 最悪で10 ** 5
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")

# 最悪で10 ** 5
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)

    # 最悪で10 ** 5
    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 = []

# 最悪で10 ** 5
for node in next_node_list:
    color = ok_color_list.pop(0)
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = list(set(next_parent_list))

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(len(COLOR_SET))
print(color_list_str)