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*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=deque(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                colar.appendleft(ckamo)
                ckamo=colar.pop()
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import*
from copy import*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
if n<90000:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=deque(range(1,m+1))
        for i in d[point]:
            if tuple(sorted([point,i])) not in dcolars:
                ckamo=colar.pop()
                if c==ckamo:
                    csave=deepcopy(ckamo)
                    ckamo=colar.pop()
                    colar.append(csave)
                dcolars[tuple(sorted([point,i]))]=ckamo
                BFS(d,i,ckamo)
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

else:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=0
        for i in d[point]:
            colar+=1
            if tuple(sorted([point,i])) not in dcolars:
                if c==colar:
                    colar+=1
                dcolars[tuple(sorted([point,i]))]=colar
                dcolars[tuple(sorted([point,i])[::-1])]=colar
                BFS(d,i,colar)
    
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

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

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

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

que = [[1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    if parent != -1:
        used[ans[EdaNum[(min(now,parent),max(now,parent))]]] = True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now])
    #print(que)

print(K)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

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

que = [[1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    if parent != -1:
        used[ans[EdaNum[(min(now,parent),max(now,parent))]]] = True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            que.append([i,now])
    #print(que)

print(K)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

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

que = [1]
K = 0
visited = [False]*(N+1)

while que != []:
    now = que.pop()
    visited[now]=True
    K = max(K, len(G[now]))
    used = [False]*(K+1)
    for i in G[now]:
        if visited[i]:
            used[ans[EdaNum[(min(now,i),max(now,i))]]] = True
    nowcolor = 1
    for i in G[now]:
        if not visited[i]:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            que.append(i)

print(K)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())

ki = [[] for i in range(N)]
kita = [False] * N

iros = [None] * (N - 1)

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

iros[0] = 1

irokazu = 0

q = deque()
q.append((0, -1))

while len(q) > 0:
    node, oyanoiro = q.popleft()
    kita[node] = True
    tsugis = ki[node]

    tsukatta = {oyanoiro}
    for tsugi, henbangou in tsugis:
        if kita[tsugi]:
            continue

        nakatta = True
        for i in range(1, irokazu+1):
            if i not in tsukatta:
                iros[henbangou] = i
                tsukatta.add(i)
                nakatta = False
                break
        if nakatta:
            irokazu += 1
            iros[henbangou] = irokazu
            tsukatta.add(irokazu)

        q.append((tsugi, iros[henbangou]))

print(irokazu)
for iro in iros:
    print(iro)

Submission status: Time Limit Exceeded

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                i = 1
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self,nodeName):
        self.name = nodeName
        self.edges = []
    def getName(self):
        return self.name
    def init_edge(self,edge):
        self.edges.append(edge)
        
class Edge():
    def __init__(self,a,b,i):
        self.a = a
        self.b = b
        self.number = i
        self.color = -1
    def setColor(self,i):
        self.color = i
    def getColor(self):
        return self.color
    

N = int(input())
s = [input() for i in range(N-1)]
a = []
b = []
for ab in s:
    sab = ab.split(" ")
    a.append(int(sab[0]))
    b.append(int(sab[1]))

a.extend(b)
nodeList=set(a)
nodes = []
edgeList = []
for name in nodeList:
    nodes.append(Node(name))
    
i = 0
for ai,bi in zip(a, b):
    edgei = Edge(ai,bi,i)
    i += 1
    edgeList.append([i,edgei])
    for node in nodes:
        if node.getName() == ai or node.getName() == bi:
            node.init_edge(edgei)
for node in nodes:
    edges = node.edges
    colors = []
    i = 0
    for edge in edges:
        colors.append(edge.color)
        colors = list(set(colors))
    for edge in edges:
        if edge.color == -1:
            while True:
                if i in colors:
                    i += 1
                else:
                    break
            edge.setColor(i)
            colors.append(i)
allcolors = []
for node in nodes:
    edges = node.edges
    for edge in edges:
        allcolors.append(edge.getColor())
allcolors = set(allcolors)
print(len(allcolors))
for el in edgeList:
    print(el[1].getColor()+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ab = [list(map(int, (input()+' '+str(i)).split())) for i in range(n-1)]
ab.sort()
uc = [0]*n
coloring = [0]*(n-1)
for i in range(n-1):
  j = 0
  while (uc[ab[i][0]-1]>>j | uc[ab[i][1]-1]>>j) & 1:
    j+=1
  else:
    coloring[ab[i][2]] = j+1
    uc[ab[i][0]-1] += 2**j
    uc[ab[i][1]-1] += 2**j
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ab = [list(map(int, (input()+' '+str(i)).split())) for i in range(n-1)]
ab.sort()
count = [0]*n
for i in range(n-1):
  count[ab[i][0]-1] += 1
  count[ab[i][1]-1] += 1
color = max(count)
print(color)
uc = [0]*n
coloring = [0]*(n-1)
for i in range(n-1):
  j = 0
  while (uc[ab[i][0]-1]>>j | uc[ab[i][1]-1]>>j) & 1:
    j+=1
  else:
    coloring[ab[i][2]] = j+1
    uc[ab[i][0]-1] += 2**j
    uc[ab[i][1]-1] += 2**j
for i in range(n-1):
  print(coloring[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
all_set = set([c for c in range(1,n+1)])
node_col = [set() for _ in range(n)]
maxc = 0
anslist = []
for i in range(n-1):
    a,b = map(int,input().split())
    abset = node_col[a-1] | node_col[b-1]
    all_m_ab = all_set - abset
    minc = min(all_m_ab)
    node_col[a-1].add(minc)
    node_col[b-1].add(minc)
    anslist.append(minc)
    maxc = max(maxc,minc)
print(maxc)
for p in anslist:print(p)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    col = 1 
    for i in g[prvi]:
      if i in used:continue
      if col == prvcol: col += 1
      cols[eds.index(sorted([i,prvi]))] = col
      q.append([i,col])
      used.add(i)
      col += 1

N = int(input())
g = {i:[] for i in range(N)}
eds = []
for _ in range(N-1):
  a,b = map(int,input().split())
  eds.append([a-1,b-1])
  g[a-1].append(b-1)
  g[b-1].append(a-1)

cols = [-1 for _ in range(N-1)]
used = set([])
bfs(0)
print(max(cols))
[print(col) for col in cols]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    used_col = [prvcol]
    for i in g[prvi]:
      if i in used:continue
      
      for coli in range(1,len(g[prvi])+1):
        if coli not in used_col:
          cols[eds.index(sorted([i,prvi]))] = coli
          used_col.append(coli)
          q.append([i,coli])
          used.add(i)
          break      

N = int(input())
g = {i:[] for i in range(N)}
eds = []
for _ in range(N-1):
  a,b = map(int,input().split())
  eds.append([a-1,b-1])
  g[a-1].append(b-1)
  g[b-1].append(a-1)

cols = [-1 for _ in range(N-1)]
used = set([])
bfs(0)
print(max(cols))
[print(col) for col in cols]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
G=[[] for n in range(N)]
E=[]
color_map={}
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    color_map[(a-1,b-1)]=0
    G[a-1].append(b-1)
    G[b-1].append(a-1)
deg=[len(v) for v in G]
K=max(deg)
Q=deque([0])
X=[]

while Q:
    v=Q.popleft()
    X.append(v)
    for u in set(G[v])-set(X):
        Q.append(u)
    if v!=0:
        p=(set(X)&set(G[v])).pop()
        colors=set(range(1,K+1))
        for q in G[p]:
            p1,q1=min(p,q),max(p,q)
            colors-={color_map[(p1,q1)]}
        a,b=min(p,v),max(p,v)
        color_map[(a,b)]=colors.pop()
print(K)
for edge in E:
    print(color_map[edge])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for n in range(N)]
E=[]
color_map={}
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    color_map[(a-1,b-1)]=0
    G[a-1].append(b-1)
    G[b-1].append(a-1)
deg=[len(v) for v in G]
K=max(deg)
Q=[0]
X=[]

while Q!=[]:
    v=Q.pop(0)
    X.append(v)
    for u in G[v]:
        if u not in X:
            Q.append(u)
    if v!=0:
        p=(set(X)&set(G[v])).pop()
        colors=set(range(1,K+1))
        for q in G[p]:
            p1,q1=min(p,q),max(p,q)
            colors-={color_map[(p1,q1)]}
        a,b=min(p,v),max(p,v)
        color_map[(a,b)]=colors.pop()
print(K)
for edge in E:
    print(color_map[edge])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
deg=[len(v) for v in G]
K=max(deg)
Q=[0]
X=[]
color_map={}
while Q!=[]:
    v=Q.pop(0)
    X.append(v)
    for u in G[v]:
        if u not in X:
            Q.append(u)
    if v!=0:
        p=(set(X)&set(G[v])).pop()
        colors=set(range(1,K+1))
        for edge in color_map.keys():
            if p in edge:
                colors-={color_map[edge]}
        a,b=min(p,v),max(p,v)
        color_map[(a,b)]=colors.pop()
print(K)
for edge in E:
    print(color_map[edge])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for n in range(N)]
E=[]
color_map={}
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    color_map[(a-1,b-1)]=0
    G[a-1].append(b-1)
    G[b-1].append(a-1)
deg=[len(v) for v in G]
K=max(deg)
Q=[0]
X=[]
while Q!=[]:
    v=Q.pop(0)
    X.append(v)
    for u in G[v]:
        if u not in X:
            Q.append(u)
    if v!=0:
        p=(set(X)&set(G[v])).pop()
        colors=set(range(1,K+1))
        for edge in E:
            if p in edge:
                colors-={color_map[edge]}
        a,b=min(p,v),max(p,v)
        color_map[(a,b)]=colors.pop()
print(K)
for edge in E:
    print(color_map[edge])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
edgelist = {}
edges = [set() for i in range(n)]
for i in range(n-1):
  u, v = map(int, input().split())
  u, v = u-1, v-1
  edgelist[(u,v)] = i
  edgelist[(v,u)] = i
  edges[u].add(v)
  edges[v].add(u)

colors = [0 for i in range(n-1)]
q = [0]
qi = 0
v = set(q)
k = 1
while qi < len(q):
  node = q[qi]
  qi += 1
  k = max(k, len(edges[node]))
  available = set(range(1,k+1))
  for adj in edges[node]:
    i = edgelist[(node, adj)]
    if colors[i] > 0:
      available.remove(colors[i])
  for adj in edges[node]:
    if adj in v:
      continue
    v.add(adj)
    q.append(adj)
    i = edgelist[(node, adj)]
    colors[i] = list(available)[0]
    available.remove(colors[i])
print(k)
for c in colors:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a, b = [0 for i in range(N-1)], [0 for i in range(N-1)]
for i in range(N-1):
  a[i], b[i] = map(int, input().split())
C = []
for i in range(1, N+1):
    C.append((a+b).count(i))
K = max(C)
index = 1
add_complete = {}
for k in range(1, K+1):
    add_complete[k] = []
print(K)
for i in range(len(a)):
    for k in range(1, K+1):
        #print(add_complete)
        if a[i] in add_complete[k] or b[i] in add_complete[k]:
            continue
        else:
            print(k)
            add_complete[k].append(a[i])
            add_complete[k].append(b[i])
            break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque


#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        checkedge=deque()
        for edge in self.edge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
                
        while checkedge:
            edge=checkedge.popleft()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Time Limit Exceeded

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)
from collections import deque


#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        checkedge=deque()
        for edge in self.edge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
        while checkedge:
            edge=checkedge.popleft()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Time Limit Exceeded

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)



#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        checkedge=[]
        for edge in self.edge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
        while checkedge:
            edge=checkedge.pop()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge=[edge]+checkedge
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Time Limit Exceeded

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)



#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        checkedge=self.edge[::-1]
        while checkedge:
            edge=checkedge.pop()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge=[edge]+checkedge
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())

#Adj_dict = {}
All_edges = []
# for i in range(n):
#     new = {i:[]}
#     Adj_dict.update(new)
Adj_dict= {i:[] for i in range(n)}

for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a-1].append(b-1)
    Adj_dict[b-1].append(a-1)
    All_edges.append((a-1,b-1))

max_val_count = 0
start_node = 0
for key, val in Adj_dict.items():
    if len(val) >= max_val_count:
        max_val_count = len(val)
        start_node = key


Visited = [False for _ in range(n)]
Colors_use = [False for _ in range(max_val_count)]
Colors_use_raw = [False for _ in range(max_val_count)]

edges_colors = {}

def coloring(Adj_dict, start, Visited, Colors_use):
    
    # 終端処理
    if Visited[start]:
        return
    
    Visited[start] = True

    for node in Adj_dict[start]:
        if Visited[node] == False:
            color = Colors_use.index(False) + 1
            Colors_use[color-1] = True
            
            edge_color = {(min(node, start), max(node, start)): color}
            edges_colors.update(edge_color)
            
            New_Colors_use = Colors_use_raw.copy()
            New_Colors_use[color-1] = True
            
            coloring(Adj_dict, node, Visited, New_Colors_use)
    return

coloring(Adj_dict, start_node, Visited, Colors_use)

print(max_val_count)
for edge in All_edges:
    print(edges_colors[edge])