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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      while cnt in edge[v]:
        cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)
m=0
for l in rel.values():
  m=max(len(l),m)
cols=[0]*(n+1)
c=deque(list(range(1,m+1)))
for i in range(1,n+1):
  cols[i]=c.copy()
visited=set([1])
cand=deque([1])
while len(cand)!=0:
  now=cand.popleft()
  for i in rel[now]:
    if not i in visited:
      cand.append(i)
      visited.add(i)
      if cols[i][0]<cols[now][0]:
        for j in cols[now]:
          if j in cols[i]:
            c=j
            break
      else:
        for j in cols[i]:
          if j in cols[now]:
            c=j
            break
      colrel[(min(now,i),max(now,i))]=c
      cols[now].remove(c)
      cols[i].remove(c)    
ans=[colrel[(min(a),max(a))] for a in p]
print(m)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

rel = [[] for _ in range(N)]

for s, t in ST:
    k = max(num[s-1], num[t-1])
    while True:
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
        k = (k - 1) % max_k + 1
    num[s-1] -= 1
    num[t-1] -= 1 
    rel[s-1].append(k)
    rel[t-1].append(k)

Submission status: Time Limit Exceeded

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

n = int(input())
l=[[]]
cnt = [0]*(n+1)
nn = []
for _ in range(n+1):
    l.append([])

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

m = max(map(len,l)) 

co = []
for i in range(n+1):
    co.append( set(range(1,m+1) ))

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Submission status: Time Limit Exceeded

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

n = int(input())
l=[[]]
cnt = [0]*(n+1)
nn = []
for _ in range(n+1):
    l.append([])

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

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Submission status: Time Limit Exceeded

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

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

m = max(cnt) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Submission status: Time Limit Exceeded

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

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

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    g = {}
    edges = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [[None for _ in range(N)] for _ in range(N)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        #print(colors)
        #print(prev, node, prevcol)
        #print(cols)
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx] 
            if colors[node][nxt] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
            colors[node][nxt] = col
            colors[nxt][node] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for src, dst in edges:
        print(colors[src][dst])
            
            




if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    g = {}
    edges = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [[None for _ in range(N)] for _ in range(N)]
    maxdeg = 0
    while nodes:
        prev, node = nodes.pop()
        prevcol = None
        if prev is not None:
            prevcol = colors[prev][node]
        maxdeg = max(maxdeg, len(g[node]))
        #print(colors)
        #print(prev, node, prevcol)
        cols = [i for i in range(1, len(g[node])+1) if prevcol is None or i!=prevcol]
        #print(cols)
        idx = 0
        for nxt in g[node]:
            if nxt == prev:
                continue
            colors[node][nxt] = cols[idx]
            idx += 1
            nodes.append((node, nxt))
    
    print(maxdeg)
    for src, dst in edges:
        print(colors[src][dst])
            
            




if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[]
    maxcolor=0
    for i in range(n+1):
        color.append([0]*(n+1))
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u][parent[u]]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[u][t]=col
                color[t][u]=col
                maxcolor=max(maxcolor,col)
                Q.append(t)
                col+=1
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[a][b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[]
    maxcolor=0
    for i in range(n+1):
        color.append([0]*(n+1))
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=set()
        usedcolor.add(color[u][parent[u]])
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                for col in range(1,n):
                    if col in usedcolor:
                        continue
                    color[u][t]=col
                    color[t][u]=col
                    usedcolor.add(col)
                    maxcolor=max(maxcolor,col)
                    break
                Q.append(t)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[a][b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter

N = int(input())

edges = {}
counter = Counter()
nodes = defaultdict(set)

K = 0
for i in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    K = max(K, counter[u], counter[v])
    nodes[u].add(v)
    nodes[v].add(u)
    edges[(u, v)] = i

colors = set([1 + k for k in range(K)])
checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    if len(checked) == N:
        break
    for v, vc in zip(nodes[u] - checked, colors - {uc}):
        edge_colors[edges[(min(u, v), max(u, v))]] = vc
        queue.append((v, vc))

print(K)
for i in range(N - 1):
    print(edge_colors[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter

N = int(input())

edges = []
counter = Counter()
nodes = defaultdict(set)

for _ in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    nodes[u].add(v)
    nodes[v].add(u)
    edges.append((u, v))

K = max(counter.values())
colors = set([1 + k for k in range(K)])

checked = set()
queue = deque([(1, 0)])
edge_colors = {}

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    if len(checked) == N:
        break
    for v, vc in zip(nodes[u] - checked, colors - {uc}):
        edge_colors[(min(u, v), max(u, v))] = vc
        queue.append((v, vc))

print(K)
for u, v in edges:
    print(edge_colors[(u, v)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter

N = int(input())

edges = []
counter = Counter()
nodes = defaultdict(set)

for _ in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    nodes[u].add(v)
    nodes[v].add(u)
    edges.append((u, v))

K = max(counter.values())
colors = set([1 + k for k in range(K)])

checked = set()
queue = deque([(1, 0)])
edge_colors = {}

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    for v, vc in zip(nodes[u] - checked, colors - {uc}):
        edge_colors[(min(u, v), max(u, v))] = vc
        queue.append((v, vc))

print(K)
for u, v in edges:
    print(edge_colors[(u, v)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter

N = int(input())

edges = []
counter = Counter()
nodes = defaultdict(set)

for _ in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    nodes[u].add(v)
    nodes[v].add(u)
    edges.append((u, v))

K = max(counter.values())
colors = set([1 + k for k in range(K)])

node_colors = defaultdict(set)
checked = set()
queue = deque([1])
edge_colors = {}

while queue:
    u = queue.popleft()
    checked.add(u)
    for v, c in zip(nodes[u] - checked, colors - node_colors[u]):
        node_colors[u].add(c)
        node_colors[v].add(c)
        edge_colors[(min(u, v), max(u, v))] = c
        queue.append(v)

print(K)
for u, v in edges:
    print(edge_colors[(u, v)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter

N = int(input())

edges = []
counter = Counter()
nodes = defaultdict(set)

for _ in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    nodes[u].add(v)
    nodes[v].add(u)
    edges.append((u, v))

K = max(counter.values())
colors = set([1 + k for k in range(K)])

node_colors = defaultdict(set)
checked = set()
queue = deque([1])
edge_colors = {}

while queue:
    u = queue.popleft()
    checked.add(u)
    for v in nodes[u]:
        if v in checked:
            continue
        c = (colors - node_colors[u] - node_colors[v]).pop()
        node_colors[u].add(c)
        node_colors[v].add(c)
        edge_colors[(min(u, v), max(u, v))] = c
        queue.append(v)

print(K)
for u, v in edges:
    print(edge_colors[(u, v)])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    temp = list(range(1,N))
    if prev[a] != 0:
      del temp[G[a][prev[a]][1]-1]
    temp = deque(temp)
    for i,b in enumerate(G[a]):
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        c = temp.popleft()
        colors.append((G[a][b][0],c))
        G[a][b][1]=G[b][a][1]=c
        if c > cmax: cmax = c
        
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if prev[a] == 0:
      a_color=set([])
    else:
      a_color=set([G[a][prev[a]][1]])
    for b in G[a]:
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        for c in range(1,N+1):
          if c not in a_color:
            a_color.add(c)
            colors.append((G[a][b][0],c))
            G[a][b][1]=G[b][a][1]=c
            if c > cmax: cmax = c
            break
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if prev[a] == 0:
      a_color=[]
    else:
      a_color=[G[a][prev[a]][1]]
    for b in G[a]:
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        for c in range(1,N+1):
          if c not in a_color:
            a_color.append(c)
            colors.append((G[a][b][0],c))
            G[a][b][1]=G[b][a][1]=c
            if c > cmax: cmax = c
            break
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush
n = int(input())
data = [[] for _ in range(n)]
color = [[-1]*n for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
kinds = -1
m = -1
for i in range(n):
    if kinds < len(data[i]):
        kinds = len(data[i])
        m = i
unused = [[i for i in range(1,kinds+1)] for _ in range(n)]
against = [[] for _ in range(n)]
for i in range(n):
    heapify(unused[i])
    heapify(against[i])
print(kinds)
q = deque([m])
visited = [0]*n
while q:
    p = q.popleft()
    visited[p] = 1
    for i in data[p]:
        if visited[i]:
            continue
        while against[p] and (unused[p][0] == against[p][0]):
            heappop(against[p])
            heappop(unused[p])
        color[p][i] = unused[p][0]
        color[i][p] = unused[p][0]
        q.append(i)
        heappush(against[i],heappop(unused[p]))
for i,j in sides:
    print(color[i][j])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0:
        cur = q.popleft()
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                col = 1
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print('\n'.join(map(str, seen)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[i]=(a, b)
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i

    q = deque()
    seen = [False]*N
    used = [set() for _ in range(N)]
    q.append(top)
    ret = {}
    while len(q)>0:
        cur = q.popleft()
        seen[cur] = True
        for nxt in Node[cur]:
            if cur>nxt:
                ed = (nxt, cur)
            else:
                ed = (cur, nxt)
            if ed in ret:
                continue
            col = 1
            while col in (used[cur] | used[nxt]):
                col+=1
            ret[ed] = col
            used[cur].add(col)
            used[nxt].add(col)
            if seen[nxt]!=True:
                q.append(nxt)

    print(K)
    for i in range(N-1):
        print(ret[Edge[i]])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0:
        cur = q.popleft()
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                col = 1
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print('\n'.join(map(str, seen)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0 and seen.count(False)>0:
        cur = q.popleft()
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                col = 1
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print('\n'.join(map(str, seen)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
P = [[] for _ in range(N)]
C = [set([]) for _ in range(N)]
T = set([])
D = defaultdict(int)

for _ in range(N-1):
  a, b = map(lambda x: int(x)-1, input().split())
  P[a].append(b)
  #P[b].append(a)
  D[(a, b)]

def bfs(s):
    d = [-1] * N
    d[s] = 0
    p_old = [s]
    M = 0
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i]:
          temp = T - C[i]
          if temp:
            v = temp.pop()
            D[(i, j)] = v
            C[i].add(v)
            C[j].add(v)
          else:
            M += 1
            T.add(M)
            D[(i, j)] = M
            C[i].add(M)
            C[j].add(M)
          d[j] = 0
          p_new.append(j)
      p_old = p_new
    return M

print(bfs(0))

for x in D.values():
  print(x)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
v = []
for i in range(n+1):
    v.append([])

colorv = [None] * (n+1)

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

for cur in range(1, n+1):

    #print("cur", cur)

    used = [False] * (n+1)

    for i in range(len(v[cur])):
        next, linenum = v[cur][i]
        if colorv[linenum] is None:
            continue
        #print(" line", linenum, "is", colorv[linenum])
        used[colorv[linenum]] = True

    ncolor = 1

    for i in range(len(v[cur])):
        next, linenum = v[cur][i]
        if colorv[linenum] is not None:
            continue
        while used[ncolor] is True:
            ncolor += 1
        colorv[linenum] = ncolor
        #print(" set line", linenum, "is", ncolor)
        used[ncolor] = True

print(max(colorv[:-2]))
for i in range(n-1):
    print(colorv[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
ab = [list(map(lambda x:int(x)-1,input().split()))for i in range(n-1)]
count = [0]*n
for i in range(n-1):
    count[ab[i][0]] += 1
    count[ab[i][1]] += 1
print(max(count))
edge = [[True]*n for i in range(n)]
anslist = []
for i in range(n-1):
    j = 0
    while True:
        if edge[ab[i][0]][j] and edge[ab[i][1]][j]:
            edge[ab[i][0]][j] = False
            edge[ab[i][1]][j] = False
            break
        j += 1
    anslist.append(j+1)
for ans in anslist:
    print(ans)

    
    '''
    now = max(edge[ab[i][0]][-1],edge[ab[i][1]][])+1
    edge[ab[i][0]].append(now)
    edge[ab[i][1]].append(now)
    anslist.append(now)
    '''

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

# 昔同じ問題を atcoder で見た？
n = int(input())
edges = []
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# print(edges)
# print(paths)
colors = {}  # (a->b) 1 とか
current = 1
biggest = 1
def f(current, prev, prev_color):
    global biggest
    color = 0
    for vertex in paths[current]:
        if vertex == prev:
            continue
        color += 1
        if color == prev_color:
            color += 1
        biggest = max(biggest, color)
        colors[(current, vertex)] = color
        f(vertex, current, color)
f(1, None, None)

print(biggest)
for a, b in edges:
    print(colors[(a, b)])
# TLE のみ？

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  g[b-1].append([a-1,i])
  g[a-1].append([b-1,i])
m = max(len(i) for i in g)
print(m)
henn = [-1]*(n-1)
q = deque()
q.append(0)
while len(q):
  p = q.popleft()
  color = [i for i in range(m)]
  for i,j in g[p]:
    if henn[j] != -1:
      color[henn[j]] = -1
  for i,j in g[p]:
    for k in color:
      if henn[j] == -1 and k != -1:
        henn[j] = k
        color[k] = -1
        q.append(i)
for i in henn:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
from collections import defaultdict
import sys
def zz():
    return list(map(int, sys.stdin.readline().split()))
def z():
    return int(sys.stdin.readline())
n = int(input())
a = [0] * (n)
b = [0] * (n)
dim_lis = [0]*n
G = [[] for _ in range(n)]
for i in range(n-1):
    a, b = list(map(int,input().split()))
    dim_lis[a - 1] += 1
    dim_lis[b - 1] += 1
    G[a-1].append((b-1, i))
    G[b-1].append((a-1, i))
# G = sorted(G)

max_node = np.argmax(dim_lis)
max_color = dim_lis[max_node]

que = deque([max_node])
visited = [False]*n
# color = 1
ans = [0] * (n - 1)
colors = defaultdict(list) 
while que:
    # print(len(que))
    color = 1
    node = que.pop()
    visited[node] = True
    for to, edge in G[node]:
        if (ans[edge] == 0):
            while (color in colors[node]):
                color += 1                
            ans[edge] = color
            colors[node].append(color)
            colors[to].append(color)
        color =+ 1
        # color = (color % max_color) + 1
        if (not visited[to]):
            que.append(to)
print(max_color)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
from collections import defaultdict
import sys
def zz():
    return list(map(int, sys.stdin.readline().split()))
def z():
    return int(sys.stdin.readline())
n = z()
a = [0] * (n)
b = [0] * (n)
dim_lis = [0]*n
G = [[] for _ in range(n)]
for i in range(n-1):
    a, b = zz()
    dim_lis[a - 1] += 1
    dim_lis[b - 1] += 1
    G[a-1].append((b-1, i))
    G[b-1].append((a-1, i))
# G = sorted(G)

max_node = np.argmax(dim_lis)
max_color = dim_lis[max_node]

que = deque([max_node])
visited = [False]*n
# color = 1
ans = [0] * (n - 1)
colors = defaultdict(list) 
while que:
    # print(len(que))
    color = 1
    node = que.pop()
    visited[node] = True
    for to, edge in G[node]:
        if (ans[edge] == 0):
            while (color in colors[node]):
                color += 1                
            ans[edge] = color
            colors[node].append(color)
            colors[to].append(color)
        color =+ 1
        # color = (color % max_color) + 1
        if (not visited[to]):
            que.append(to)
print(max_color)
print(*ans, sep='\n')