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 sys
from collections import deque
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('input.txt')
input = sys.stdin.readline

def dfs(G, C, v):
	seen[v] = True
	global colors

	for idx, next in enumerate(G[v]):
		# print('今の状態',v, next, seen[next])
		if seen[next]:
			continue

		# color の割り当て
		# colors でループし、C[v]およびC[next]のなかで使われていなければセット
		for color in colors:
			# print('チェックするcolor',color)
			# print('対象の辺で使われているcolor', C[v], C[next])

			# どちらもで使われていない色であればセット
			if not C[v].count(color) and not C[next].count(color):
				# print('既存の', color, 'の色をセット')
				C[v][idx] = color
				next_color_index = G[next].index(v)
				C[next][next_color_index] = color
				break
			
		# colors 全てC[v]で使用済みであれば、新しいものを払い出し
		if C[v][idx] == 0:
			# print('新しい', colors[-1]+1, 'の色をセット')
			C[v][idx] = colors[-1]+1
			next_color_index = G[next].index(v)
			C[next][next_color_index] = colors[-1]+1
			colors.append(C[v][idx])

		dfs(G, C, next)

N = int(input())
G = [[] for _ in range(N)]
O = []
for _ in range(N-1):
	a,b = MAP()
	G[a-1].append(b-1)
	G[b-1].append(a-1)
	O.append([a-1,b-1])

C = [[0]*len(g) for g in G]
seen = [False for _ in range(N)]
colors = deque([1])

for i in range(N):
	if not seen[i]:
		dfs(G, C, i)

print(len(colors))
for o in O:
	i = o[0]
	j = G[i].index(o[1])
	print(C[i][j])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('input.txt')
input = sys.stdin.readline

def dfs(G, C, v):
	seen[v] = True
	global colors

	for idx, next in enumerate(G[v]):
		# print('今の状態',v, next, seen[next])
		if seen[next]:
			continue

		# color の割り当て
		# colors でループし、C[v]およびC[next]のなかで使われていなければセット
		for color in colors:
			# print('チェックするcolor',color)
			# print('対象の辺で使われているcolor', C[v], C[next])

			# どちらもで使われていない色であればセット
			if not C[v].count(color) and not C[next].count(color):
				# print('既存の', color, 'の色をセット')
				C[v][idx] = color
				next_color_index = G[next].index(v)
				C[next][next_color_index] = color
				break
			
		# colors 全てC[v]で使用済みであれば、新しいものを払い出し
		if C[v][idx] == 0:
			# print('新しい', colors[-1]+1, 'の色をセット')
			C[v][idx] = colors[-1]+1
			next_color_index = G[next].index(v)
			C[next][next_color_index] = colors[-1]+1
			colors.append(C[v][idx])

		dfs(G, C, next)

N = int(input())
G = [[] for _ in range(N)]
O = []
for _ in range(N-1):
	a,b = MAP()
	G[a-1].append(b-1)
	G[b-1].append(a-1)
	O.append([a-1,b-1])

C = [[0]*len(g) for g in G]
seen = [False for _ in range(N)]
colors = [1]

for i in range(N):
	if not seen[i]:
		dfs(G, C, i)

print(len(colors))
for o in O:
	i = o[0]
	j = G[i].index(o[1])
	print(C[i][j])

Submission status: Time Limit Exceeded

Solution code:
# D - Coloring Edges on Tree
N = int(input())
A = [0] * N
A = [A.copy() for _ in range(N)]
edge_list = [0 for _ in range(N - 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge_list[i] = (a, b)
    A[a - 1][b - 1] = A[b - 1][a - 1] = 1
    
K = max([sum(l) for l in A])
print(K)

color_list = set(i + 1 for i in range(K))
color_list = [color_list.copy() for _ in range(N)]
for i in range(N - 1):
    a, b = edge_list[i]
    color = min(color_list[a - 1] & color_list[b - 1])
    print(color)
    color_list[a - 1].remove(color)
    color_list[b - 1].remove(color)

Submission status: Time Limit Exceeded

Solution code:
# D - Coloring Edges on Tree
N = int(input())
A = [[0] * N for _ in range(N)]
edge_list = [(0, 0) for _ in range(N - 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge_list[i] = (a, b)
    A[a - 1][b - 1] = A[b - 1][a - 1] = 1
    
K = max([sum(l) for l in A])
print(K)

color_list = [set(i + 1 for i in range(K)) for _ in range(N)]
for i in range(N - 1):
    a, b = edge_list[i]
    color = min(color_list[a - 1] & color_list[b - 1])
    print(color)
    color_list[a - 1].remove(color)
    color_list[b - 1].remove(color)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        j=min(np.setdiff1d(z,c))

        #for j in range(1,n+1):
        #for j in q:
            #if j not in c:
        ans[p]+=j
        x[a].add(j)
        x[b].add(j)
        #    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        j=min(z-c)

        #for j in range(1,n+1):
        #for j in q:
            #if j not in c:
        ans[p]+=j
        x[a].add(j)
        x[b].add(j)
        #    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        j=min(z-c)

        #for j in range(1,n+1):
        #for j in q:
            #if j not in c:
        ans[p]+=j
        x[a].add(j)
        x[b].add(j)
        #    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        q=sorted(list(z-c))

        #for j in range(1,n+1):
        for j in q:
            if j not in c:
                ans[p]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        for j in range(1,n+1):
            if j not in c:
                ans[p]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        for j in range(1,n+1):
            if j not in c:
                ans[p]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [{0} for i in range(n)]

ans = [0] * n
a = 0
b = 0
sp = {i for i in range(n)}
for i in range(1,n):
    a,b = list(map(int,input().split()))
    ans[i] = min(sp-(s[a-1]|s[b-1]))

    s[a-1].add(ans[i])
    s[b-1].add(ans[i])

print(max(ans))
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [{i for i in range(1,n+1)}for j in range(n)]

ans = [0] * n
a = 0
b = 0

for i in range(1,n):
    ab = list(map(int,input().split()))
    a = int(ab[0])
    b = int(ab[1])
    ans[i] = min(s[a-1] & s[b-1])

    s[a-1].remove(ans[i])
    s[b-1].remove(ans[i])

print(max(ans))
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
        if i != parent:
            if color == used_color:
                color += 1
            abmap[num][i] = color
            abmap[i][num] = color
            coloring(i,num,color)
            color += 1

coloring(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
        if i == parent:
            continue
        else:
            if color == used_color:
                color += 1
            abmap[num][i] = color
            abmap[i][num] = color
            coloring(i,num,color)
            color += 1

coloring(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Time Limit Exceeded

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
        if i == parent:
            continue
        else:
            if color == used_color:
                color += 1
            abmap[num][i] = color
            abmap[i][num] = color
            coloring(i,num,color)
            color += 1

coloring(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Time Limit Exceeded

Solution code:
#d
def main():
    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())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = collections.deque([(1,0)])
    #while q:
    for _ in range(n):
        x,parent = q.popleft()
        if parent!=0:
            for j in range(k):
                if not j in used_colors[parent-1]:
                    current_color=j
                    break
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))   
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#d
def main():
    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())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = collections.deque([(1,0)])
    #while q:
    for _ in range(n):
        x,parent = q.popleft()
        if parent!=0:
            current_color=list(set(color_list)-set(used_colors[parent-1]))[0]
            
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))   
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
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-1)
alen=[0]*N
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    alen[i]=len(arr[i])
    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()
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            C=set(range(1,alen[t]+1))
            coltemp=C^(C&col[t])
            que[i+1]=que[i+1] | arrtemp
            for f in arrtemp:
                p=coltemp.pop()
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline

def main():
  N=int(input())
  L=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(N-1)]
  
  E=[[] for _ in range(N)]
  for a,b in L:
      E[a].append(b)
      E[b].append(a)
  dic={(a,b):-1 for a,b in L}
  q=deque([0])
  Ec=[set() for _ in range(N)]
  while q:
      v=q.popleft()
      for to in E[v]:
          min_v,max_v=(v,to) if v<=to else (to,v)
          if dic[(min_v,max_v)]!=-1:
              continue
          c_i=1
          while c_i in Ec[v]:c_i+=1
          Ec[v].add(c_i);Ec[to].add(c_i)
          dic[(min_v,max_v)]=c_i
          q.append(to)
  
  print(max(dic.values()))
  for p in L:
    print(dic[p])

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline


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

E=[[] for _ in range(N)]
for a,b in L:
    E[a].append(b)
    E[b].append(a)
dic={(a,b):-1 for a,b in L}
q=deque([0])
Ec=[set() for _ in range(N)]
while q:
    v=q.popleft()
    for to in E[v]:
        min_v,max_v=(v,to) if v<=to else (to,v)
        if dic[(min_v,max_v)]!=-1:
            continue
        c_i=1
        while c_i in Ec[v]:c_i+=1
        Ec[v].add(c_i);Ec[to].add(c_i)
        dic[(min_v,max_v)]=c_i
        q.append(to)

print(max(dic.values()))
for p in L:
    print(dic[p])

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.buffer.readline
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-1)
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
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()
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    
    col[f].add(p)
    arr[f].remove(flag)
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=set(arr[t])
        if len(arrtemp)>0:
            
            que[i+1]=que[i+1] | arrtemp
            for f in arrtemp:
                p=coltemp.pop()
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
        reach.add(t)
print(colmax)
for i in range(N-1):
    print(colarr[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]

tree = {i:[] for i in range(1, N+1)}
for a, b in ab:
    tree[a].append(b)
    tree[b].append(a)

stree = sorted(tree.items(), key=lambda x: -len(x[1]))
print(len(stree[0][1]))
start = stree[0][0]

colormap = {i:[0]*(N+1) for i in range(1, N+1)}
from collections import deque
q = deque([start])
visited = {start}
while q:
    n = q.popleft()
    for p in tree[n]:
        if p in visited:
            continue
        i = 1
        while True:
            if i not in colormap[n] and i not in colormap[p]:
                colormap[n][p] = i
                colormap[p][n] = i
                break
            i += 1
        if p not in visited:
            q.append(p)
            visited.add(p)

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

Submission status: Time Limit Exceeded

Solution code:
#d
def main():
    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())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = collections.deque([(1,0)])
    #while q:
    for _ in range(n):
        x,parent = q.pop()
        if parent!=0:
            current_color=list(set(color_list)-set(used_colors[parent-1]))[0]
            
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))   
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import random
# 幅優先探索の問題。キューを使う。
class Graph():
    def __init__(self):
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
    
    def edge_num(self, node):
        return len(self.edges[node])
    
    def set_weight(self, from_node, to_node, weight):
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
    
    def has_node_weight(self,node):
        node_set = set()
        for x in self.edges[node]:
            node_set.add(self.weights[(node,x)])
        return node_set

    def done(self):
        if min(self.weights) > 0:
            return True
        else:
            return False

N = int(input())
A = [0]*N
B = [0]*N

g = Graph()

for i in range(N-1):
    A[i], B[i]  = map(int,input().split())
    A[i], B[i] = A[i]-1, B[i]-1
    g.add_edge(A[i], B[i],-1)

edgenum = [0]*N
for n in range(N):
    edgenum[n] = g.edge_num(n)

K = max(edgenum)
K_root = edgenum.index(K)
que = list()
visited = list()

que.append(K_root)

while que != []:
    node = que.pop()
    visited.append(node)
    color = [g.weights[(node, x)] for x in g.edges[node] if g.weights[(node, x)] != -1]
    k = 1
    while k in color:
        k += 1
    for end in [x for x in g.edges[node] if x not in visited]:
        que.append(end)
        g.set_weight(node,end,k)
        k += 1
        while k in color:
            k += 1

def output():
    print(K)
    for i in range(N-1):
        print(g.weights[(A[i], B[i])])
    
output()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def solve(num,pr,used):
    global tree
    global abmap
    cnt = 1
    nodes = tree[num]
    for i in nodes:
        if i == pr:
            continue
        else:
            if cnt == used:
                cnt += 1
            abmap[num][i] = cnt
            abmap[i][num] = cnt
            solve(i,num,cnt)
            cnt += 1

solve(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

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)]
ans = {}
queue = deque([])
e = []
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(tuple(temp))
    ans[(temp[0],temp[1])] = 0
    ans[(temp[1],temp[0])] = 0
    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 = []
#答え
def bfs(x):
    k = 1
    for i in G[x]:
        if ans[(x,i)] ==0:
            queue.append(i)
            flag = 1
            while flag:
                if k not in nuc[x]:         
                    ans[(x,i)] = k
                    ans[(i,x)] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    flag = 0
                else:
                    k += 1
                
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m])

Submission status: Time Limit Exceeded

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def solve(num,pr,used):
    global tree
    global abmap
    cnt = 1
    nodes = tree[num]
    for i in nodes:
        if i == pr:
            continue
        else:
            if cnt == used:
                cnt += 1
            abmap[num][i] = cnt
            abmap[i][num] = cnt
            solve(i,num,cnt)
            cnt += 1

solve(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Time Limit Exceeded

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

tree = {}
for i in ab:
        tree[i[0]] = []
        tree[i[1]] = []
for i in ab:
    tree[i[0]].append(i[1])
    tree[i[1]].append(i[0])

def trsum(tree,n):
    sum = 0
    for i in range(1,n+1):
        sum = max(sum,len(tree[i]))
    return sum

print(trsum(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def solve(num,pr,used):
    global tree
    global abmap
    cnt = 1
    nodes = tree[num]
    for i in nodes:
        if i == pr:
            continue
        else:
            if cnt == used:
                cnt += 1
            abmap[num][i] = cnt
            abmap[i][num] = cnt
            solve(i,num,cnt)
            cnt += 1

solve(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

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):
    k = 1
    for i in G[x]:
        if ans[x][i] ==0:
            queue.append(i)
            flag = 1
            while flag:
                if k not in nuc[x]:         
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    flag = 0
                else:
                    k += 1
                
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:
import collections
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:
            return i,max(cc,i)
done_v=set()
q=collections.deque()
q.append(node[0])
done_v.add(node[0])

while q:
        i=q.popleft()
        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.append(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 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(node[0])
done_v.add(node[0])

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になるか確かめる）