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 defaultdict
n=int(input())
col=[{}for i in range(n)]
edges=[set() for i in range(n)]
ret=[0]*(n-1)
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].add((s-1,i));edges[s-1].add((a-1,i))
m=0
ind=-1
for i in range(n):
    if m<len(edges[i]):
        ind=i
        m=len(edges[i])
print(m)
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i,e in zip(range(1,m+1),edges[ind]):
    col[e[0]][ind]=i
    dq.append(e[0])
    ret[e[1]]=i
x=set(range(1,m+1))
while dq:
    a=dq.popleft()
    c=x-set(col[a].values())
    ng=set(col[a].keys())
    for to,num in edges[a]:
        if to not in ng:
            cc=c.pop()
            col[to][a]=cc
            dq.append(to)
            ret[num]=cc
        
print(*ret,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
col=[{}for i in range(n)]
edges=[set() for i in range(n)]
ed=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].add(s-1);edges[s-1].add(a-1)
    ed.append((a-1,s-1))
m=0
ind=-1
for i in range(n):
    if m<len(edges[i]):
        ind=i
        m=len(edges[i])
print(m)
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i,e in zip(range(1,m+1),edges[ind]):
    col[e][ind]=i
    dq.append(e)
x=set(range(1,m+1))
while dq:
    a=dq.popleft()
    c=x-set(col[a].values())
    for to in edges[a]-set(col[a].keys()):
        col[to][a]=c.pop()
        dq.append(to)
for i,j in ed:
    if j in col[i]:
        print(col[i][j])
    else:
        print(col[j][i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
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)

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)
      uni=cols[now]|cols[i]
      c=min(set(range(1,m+1))-uni)
      colrel[(min(now,i),max(now,i))]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[colrel[(min(a),max(a))] for a in p]
print(m)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)

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)
      uni=cols[now]|cols[i]
      if len(uni)==0:
        c=1
      else:
        m=max(uni)
        if len(uni)==m:
          c=m+1
        else:
          c=min(set(range(1,m))-uni)
      colrel[min(now,i),max(now,i)]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[colrel[min(a),max(a)] for a in p]
print(max(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)

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)
      uni=cols[now]|cols[i]
      if len(uni)==0:
        c=1
      else:
        m=max(uni)
        if len(uni)==m:
          c=m+1
        else:
          c=min(set(range(1,m))-uni)
      colrel[min(now,i),max(now,i)]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[0]*(n-1)
m=0
for i,a in enumerate(p):
  x=colrel[min(a),max(a)]
  ans[i]=x
  m=max(m,x)
print(m)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)

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)
      uni=cols[now]|cols[i]
      if len(uni)==0:
        c=1
      elif len(uni)==max(uni):
        c=max(uni)+1
      else:
        c=min(set(range(1,max(uni)))-uni)
      colrel[min(now,i),max(now,i)]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[]
for a,b in p:
  ans.append(colrel[min(a,b),max(a,b)])
print(max(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)

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)
      c=1
      while c in cols[now] or c in cols[i]:
        c+=1
      colrel[min(now,i),max(now,i)]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[]
for a,b in p:
  ans.append(colrel[min(a,b),max(a,b)])
print(max(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

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

l=list(d.items())
# l.sort(key=lambda x:-len(x[1]))
# m=len(l[0][1])
m=0
d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a1,list1 in l:
    m=max(m,len(list1))
    color=1
    for b1 in list1:
        if a1>b1:
            a,b=b1,a1
        else:
            a,b=a1,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
ans=[]
for line in ab:
    ans.append(d2[line])
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

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

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a1,list1 in l:
    color=1
    for b1 in list1:
        if a1>b1:
            a,b=b1,a1
        else:
            a,b=a1,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
ans=[]
for line in ab:
    ans.append(d2[line])
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

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

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for node,list1 in l:
    a=node
    color=1
#     print(node,list1)
    for b1 in list1:
        if node>b1:
            a,b=b1,node
        else:
            a,b=node,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
for line in ab:
    print(d2[line])

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop as p
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
def f(Q):
    R=[]
    for q in Q:
        H=list(range(1,n))
        for t in T[q[0]]:
            x=p(H)
            if x==q[1]:
                x=p(H)
            C[t[1]]=x
            if len(T[t[0]])!=0:
            	R.append([t[0],x])
    if len(R)!=0:
    	return f(R)
f([[0,0]])
print(max(C))
for c in C:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

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

tree=[[] for i in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

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

que=deque()
que.append(0)

ans_dict={}
while que:
  x=que.popleft()

  c=1
  for i in tree[x]:
    if col[i]==[0]:
      que.append(i)

      while True:
        if c in col[x]:
          c+=1
        else:
          break

      col[x].append(c)
      col[i].append(c)
      ans_dict[(x+1,i+1)]=c
      ans_dict[(i+1,x+1)]=c

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from operator import itemgetter

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    al = [[] for _ in range(n)]
    e = dict()
    for i in range(n - 1):
        a, b = [int(j) - 1 for j in read().split()]
        al[a].append(b)
        al[b].append(a)
        e[(a, b)] = i
    v, k = 0, 0
    for i in range(n):
        if len(al[i]) > k:
            v = i
            k = len(al[i])
    print(k)
    sn = deque([v])
    sd = set()
    cv = [set() for _ in range(n)]
    ce = dict()
    while sn:
        v = sn.popleft()
        sd.add(v)
        for vn in al[v]:
            if vn in sd:
                continue
            for ci in range(1, k + 1):
                if ci not in cv[v] and ci not in cv[vn]:
                    cv[v].add(ci)
                    cv[vn].add(ci)
                    if (v, vn) in e:
                        ce[(v, vn)] = ci
                    else:
                        ce[(vn, v)] = ci
                    break
            sn.append(vn)
    for k, _ in sorted(e.items(), key=itemgetter(1)):
        print(ce[k])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    ver = set(graph[r].keys())
    col = [i for i in range(k) if i not in set(graph[r].values())]
    i = 0
    for n in ver:
      if not visited[n]:
        graph[r][n] = col[i]
        graph[n][r] = col[i]
        i = (i+1)%len(col)

        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    ver = graph[r].keys()
    col = graph[r].values()
    for n in set(ver):
      if not visited[n]:
        if color not in set(col):
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    col = graph[r].values()
    for n in set(graph[r].keys()):
      if not visited[n]:
        if color not in set(col):
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

bfs(1,k)
print(k)
for i in range(N-1):
  a,b = ab[i]
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    col = graph[r].values()
    for n in set(graph[r].keys()):
      if not visited[n]:
        if color not in col:
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

bfs(1,k)
print(k)
for i in range(N-1):
  a,b = ab[i]
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    for n in set(graph[r].keys()):
      if not visited[n]:
        if color not in graph[r].values():
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

bfs(1,k)
print(k)
for i in range(N-1):
  a,b = ab[i]
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    for n in graph[r].keys():
      if not visited[n]:
        if color not in graph[r].values():
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

bfs(1,k)
print(k)
for i in range(N-1):
  a,b = ab[i]
  print(graph[a][b]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())

ans = []
lst = [[True]*(n+1) for i in range(n+1)]
graph = [[] for i in range(n+1)]

for i in range(n-1):
  
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  
  for j in range(1, n+1):
    if lst[a][j] and lst[b][j]:
      lst[a][j] = False
      lst[b][j] = False
      ans.append(j)
      break

maxi = 0
for i in range(len(graph)):
  maxi = max(maxi, len(graph[i]))

print(maxi)
for i in range(len(ans)):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
ans = []
lst = [[True]*(n+1) for i in range(n+1)]
graph = [[] for i in range(n+1)]
for i in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  for i in range(1, n+1):
    if lst[a][i] and lst[b][i]:
      lst[a][i] = False
      lst[b][i] = False
      ans.append(i)
      break

maxi = 0
for i in range(len(graph)):
  maxi = max(maxi, len(graph[i]))

print(maxi)
for i in range(len(ans)):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)

def bfs_graph(start, G):
    from collections import deque
    # 隣接リストを食わせる
    color = [set(range(1, color_num + 1)) for _ in range(N)]
    ans = {}
    seen = {start}
    que = deque([start])
    while que:
        v = que.popleft()
        seen.add(v)
        for w in G[v]:
            if w in seen:
                continue
            que.append(w)
            c = (color[v]&color[w]).pop()
            color[v].remove(c)
            color[w].remove(c)
            ans[(v, w)] = c
            ans[(w, v)] = c
    return ans
ans = bfs_graph(0, graph)

for ab in ablist:
    try:
        print(ans[tuple(ab)])
    except KeyError:
        print(ans[tuple(ab[::-1])])

Submission status: Time Limit Exceeded

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)

def bfs_graph(start, G):
    from collections import deque
    # 隣接リストを食わせる
    color = [set(range(1, color_num + 1)) for _ in range(N)]
    ans = {}
    dist = [-1] * N
    que = deque([start])
    dist[start] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
            c = (color[v]&color[w]).pop()
            color[v].remove(c)
            color[w].remove(c)
            ans[(v, w)] = c
            ans[(w, v)] = c
    return ans
ans = bfs_graph(0, graph)

for ab in ablist:
    try:
        print(ans[tuple(ab)])
    except KeyError:
        print(ans[tuple(ab[::-1])])

Submission status: Time Limit Exceeded

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)

def bfs_graph(start, G):
    from collections import deque
    # 隣接リストを食わせる
    color_set = set(range(1, color_num + 1))
    color = [set() for _ in range(N)]
    ans = {}
    dist = [-1] * N
    que = deque([start])
    dist[start] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
            c = (color_set - (color[v]|color[w])).pop()
            color[v].add(c)
            color[w].add(c)
            ans[(v, w)] = c
            ans[(w, v)] = c
    return ans
ans = bfs_graph(0, graph)

for ab in ablist:
    try:
        print(ans[tuple(ab)])
    except KeyError:
        print(ans[tuple(ab[::-1])])

Submission status: Time Limit Exceeded

Solution code:
import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
color = [[] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        
        col = 1
        if edge[i[1]] == -1:
            que.put(i[0])
            while(True):
               
                if col in (color[i[0]] + color[start]):
                    col +=1
                    if col > maxi:
                        maxi = col
                else :
                    break
            edge[i[1]] = col
            color[i[0]].append(col)
            color[start].append(col)
print(maxi)
for i in edge[1:]:
    print(i)

Submission status: Time Limit Exceeded

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

que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = max([len(i) for i in tree])
color = [[i for i in range(1,maxi+1)] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        
        if edge[i[1]] == -1:
            col = max(color[i[0]][0],color[start][0])
            edge[i[1]] = col
            que.put(i[0])
            color[i[0]].remove(col)
            color[start].remove(col)
print(maxi)
for i in edge[1:]:
    print(i)

Submission status: Time Limit Exceeded

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

que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = max([len(i) for i in tree])
color = [[i for i in range(1,maxi+1)] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
            node[i[0]] = 1
        if edge[i[1]] == -1:
            col = max(color[i[0]][0],color[start][0])
            edge[i[1]] = col
            color[i[0]].remove(col)
            color[start].remove(col)
print(maxi)
for i in edge[1:]:
    print(i)

Submission status: Time Limit Exceeded

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

que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
color = [[] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
            node[i[0]] = 1
        col = 1
        if edge[i[1]] == -1:
            while(True):
               
                if col in (color[i[0]] + color[start]):
                    col +=1
                    if col > maxi:
                        maxi = col
                else :
                    break
            edge[i[1]] = col
            color[i[0]].append(col)
            color[start].append(col)
print(maxi)
for i in edge[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    node_unused_color = [{i for i in range(max_root)} for j in range(n)]

    que = queue.Queue()
    que.put(0)

    while que.qsize() > 0:
        node = que.get()
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            chosen_color = -1
            for tmp_a in node_unused_color[ai]:
                if tmp_a in node_unused_color[bi]:
                    chosen_color = tmp_a
                    break
            node_unused_color[ai] -= {chosen_color}
            node_unused_color[bi] -= {chosen_color}
            edge_dic[(ai, bi)] = chosen_color
            que.put(k)

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    node_unused_color = [{i for i in range(max_root)} for j in range(n)]

    que = queue.Queue()
    que.put(0)

    while que.qsize() > 0:
        node = que.get()
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            choices = node_unused_color[ai] & node_unused_color[bi]
            chosen_color = min(choices)
            node_unused_color[ai] -= {chosen_color}
            node_unused_color[bi] -= {chosen_color}
            edge_dic[(ai, bi)] = chosen_color
            que.put(k)

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)]+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(graph, N, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        # do_something(node)
        color = 1
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                while color in colors[node].values():
                    color += 1
                colors[node][n] = color
                colors[n][node] = color
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
colors = bfs(graph, N, 0)
print(max(counts))
for i, j in inputs:
    print(colors[i][j])