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: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for i in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append((y, i))
    edge[y].append((x, i))

color = [-1] * (N - 1)


def dfs(s, p=-1, pc=-1):
    c = 0
    for t, x in edge[s]:
        if color[x] != -1:
            continue
        if t == p:
            continue
        c += 1
        if c == pc:
            c += 1
        color[x] = c
        dfs(t, s, c)


dfs(1)

print(len(Counter(color)))
print(*color, sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

for i in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append((i, to))
    edges[to].append((i, fr))

ans = [-1] * (N - 1)
A = [set() for _ in range(N)]

st = [0]
while st:
    now = st.pop()
    s = 1
    for i, to in edges[now]:
        if ans[i] != -1:
            continue
        while s in A[now]:
            s += 1
        ans[i] = s
        A[to].add(s)
        A[now].add(s)
        st.append(to)

print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

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

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

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


color_list = {}
check_list = [0]*n

color_max = max(map(len, connect_list))

vertex = [0 for i in range(n)]
d = deque([0])

while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]

    for i in index_list:
        if check_list[i] == 1:
            continue

        check_list[i] = 1
        d.append(i)
        num = vertex[index] % color_max+1
        color_list[(min(index, i), max(index, i))] = num
        vertex[index], vertex[i] = num, num


print(color_max)
for a, b in ab:
    print(color_list[(a-1, b-1)])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[[] for i in range(n)]#0-indexed
edges=[tuple(map(int,input().split())) for i in range(n-1)]#1-indexed
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}#0-indexed
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    
    edge_color[(V,I)]=vertex[v]%color+1
    vertex[V],vertex[I]=edge_color[(V,I)],edge_color[(V,I)] 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

Submission status: Accepted

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

N = int(input())
G = [[] for _ in range(N)] # 辺の相手を保存
for i in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append([b, i])
    G[b].append([a, i])

stack = deque([[0, 0]])
visited = [0] * N
visited[0] = 1
ans = [0] * (N-1)
while stack:
    i, pc = stack.pop()
    c = 1
    for ni, ln in G[i]:
        if not visited[ni]:
            visited[ni] = 1
            if c == pc:
                c += 1
            ans[ln] = c
            c += 1
            stack.append([ni, ans[ln]])

print(max(ans)) 
for c in ans:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
nood = [[]for i in range(0,N+1,1)]
h_color = [1]*(N+1)
for i in range(1,N,1):
    a,b=map(int,input().split())
    nood[a].append([b,i])
    nood[b].append([a,i])

max_color_count = -1

def bfs(nowNood,preNood,preColor):
    global max_color_count
    colorCount=1
    for i in range(0,len(nood[nowNood]),1):
        if nood[nowNood][i][0]!=preNood:
            if colorCount == preColor:
                colorCount+=1
            h_color[nood[nowNood][i][1]]=colorCount
            bfs(nood[nowNood][i][0],nowNood,colorCount)
            max_color_count = max(max_color_count,colorCount)
            colorCount+=1

bfs(1,-1,-1)
print(max_color_count)
for i in range(1,N,1):
    print(h_color[i])

Submission status: Accepted

Solution code:
# D - Coloring Edges on Tree

import sys

sys.setrecursionlimit(10 ** 5)

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

ans = [-1] * (N - 1)

def dfs(key, color=-1, parent=-1):
    k = 1
    for i in range(len(G[key])):
        if G[key][i][0] == parent:
            continue
        if color == k:
            k += 1
        ans[G[key][i][1]] = k
        dfs(G[key][i][0], k, key)
        k += 1

dfs(0)

print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

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

#
N = int(input())
edges = []
graph = [[] for _ in range(N)]
color = [{} for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

    color[a][b] = -1
    color[b][a] = -1

    edges.append((a, b))

#
buf = collections.deque()
buf.append(0)

while buf:
    src = buf.popleft()
    used = [color[src][dst] for dst in graph[src]
                if color[src][dst] != -1]
    dst_color = 1
    while dst_color in used:
        dst_color += 1

    for dst in graph[src]:
        if color[src][dst] == -1:
            color[src][dst] = dst_color
            color[dst][src] = dst_color
            buf.append(dst)

            used.append(dst_color)
            while dst_color in used:
                dst_color += 1



#
print(max([max(c.values()) for c in color]))
for a,b in edges:
    print(color[a][b])

Submission status: Accepted

Solution code:
import queue

N = int(input())
ab = []
deg = [0 for i in range(N)]
child = [[] for _ in range(N)]
edge = {}
color = [0 for _ in range(N-1)]
for i in range(N-1):
  tmp = list(map(int, input().split()))
  deg[tmp[0]-1] += 1
  deg[tmp[1]-1] += 1
 
  child[tmp[0]-1].append(tmp[1]-1)
  child[tmp[1]-1].append(tmp[0]-1)
  tmp = [tmp[0]-1, tmp[1]-1]
  edge[tuple(tmp)] = i
  
q = queue.Queue()
q.put([None, 0, None])
used = [0]
# parent, self, color
while not q.empty():
  current = q.get()
  if current[0] is not None:
    cnt = 1
    for c in child[current[1]]:
  #    if c in used:
  #      continue
      used.append(c)
      if cnt == current[2]:
        cnt += 1
      q.put([current[1], c, cnt])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = cnt
      child[c].remove(current[1])
      cnt += 1
  else:
    for i, c in enumerate(child[current[1]]):
      used.append(c)
      q.put([current[1], c, i+1])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      #print(edge[tuple(ind)], i+1)
      color[edge[tuple(ind)]] = i+1
      child[c].remove(current[1])

print(max(deg))
for c in color:
  print(c)

Submission status: Accepted

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

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peers = [[] for _ in range(N)]
colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peers[a].append(b)
    colors[a][b] = 0


def draw(node, parent_edge_color):
    _peers = peers[node]
    if len(_peers) == 0:
        return 0
    color = 1
    max_nrof_color = 1
    for peer in _peers:
        #print(node,peer,color)
        if color == parent_edge_color:
            color +=1
        colors[node][peer] = color
        max_nrof_color = max(max_nrof_color, color, draw(peer, color))
        color += 1

    return max_nrof_color


print(draw(0,0))
for a,b in pairs:
    print(colors[a][b])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append((b, i))
    graph[b].append((a, i))
color = [-1] * (n + 1)
color[1] = -2
ans = [0] * (n - 1)

def bfs(s):
    stack = deque([s])
    while stack:
        num = 1
        now = stack.pop()
        for next, idx in graph[now]:
            if color[next] != -1:
                continue
            if color[now] == num:
                num += 1
            color[next] = num
            ans[idx] = num
            num += 1
            stack.append(next)


bfs(1)
print(max(ans))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:



N = int(input())
es = [[] for _ in range(N)]
connected = [0] * N
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    connected[a] += 1
    connected[b] += 1
    es[a].append((b, i))
    es[b].append((a, i))


ans = [0] * (N-1)
used = [False] * (N-1)
q = []
q.append((0, 0)) 

while q:
    curr, pc = q.pop()
    nxt_es_color = 1
    for nxt, es_num in es[curr]:
        if used[es_num]:
            continue
        if nxt_es_color == pc:
            nxt_es_color += 1

        ans[es_num] = nxt_es_color
        used[es_num] = True
        q.append((nxt, ans[es_num]))
        nxt_es_color += 1


print(max(connected))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
# list(map(int, input().split()))
mod = 10 ** 9 + 7

from collections import deque

# まず、Kの最小値を求める
#　頂点に繋がる辺の数 <= Kを全ての頂点で満たす
N = getN()
dist = [[] for i in range(N + 1)]
# エッジの配列はこうする
edge = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a].append(b)
    dist[b].append(a)
    # エッジの色の入力の仕方
    edge[(a, b)] = i
    edge[(b, a)] = i

ignore = [-1] * (N + 1)
ignore[1] = 0
# 辺の数は頂点の数より一つ少ない
ans = [0] * (N - 1)

pos = deque([1])
while len(pos) > 0:
    u = pos.popleft()
    # 一番最初の色から順にサーチしていく
    j = 1
    for i in dist[u]:
        if ignore[i] < 0:
            # 根元の頂点の色と一致していたら色を変える
            if j == ignore[u]:
                j += 1
            # 辺をスライドしていくたびに行先の頂点の色を変える
            ignore[i] = j
            # 辺の色は行先の頂点の色に合わせる
            ans[edge[(i, u)]] = j
            pos.append(i)
            j += 1
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)

# 親と子の関係を作る
while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        
# 根以外の頂点は、唯一の親を持つことから、
# vの親がpであるとき → color[v] に辺 pvの色を持たせると定めて色を管理
color = [-1] * (N+1)
for x in seen:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

ans = []
for a,b in ab:
    ans.append(color[b])

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

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n)]
inv = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append((b - 1, i))
    inv[a - 1] += 1
    g[b - 1].append((a - 1, i))
    inv[b - 1] += 1
k = max(inv)
print(k)
s = [0]
d = [-1] * n
d[0] = [-2]
ans = [0] * (n - 1)
while s:
    p = s.pop()
    c = 1
    for node, idx in g[p]:
        if d[node] == -1:
            if c == d[p]:
                c += 1
            d[node] = c
            ans[idx] = c
            c += 1
            s.append(node)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edge=[[] for i in range(n+1)]
ab=[]
ans=dict()
for i in range(n-1):
  a,b=map(int,input().split())
  ab.append([a,b])
  ans[(a,b)]=0
  edge[a].append(b)
  edge[b].append(a)
hantei=0  
for i in edge:
  if hantei<len(i):
    hantei=len(i)
iro=hantei
print(iro)
color_list=[0]*(n+1)
def bfs(x,ans):
  qu=deque([])
  qu.append(1)
  count=1
  while qu:
    now=qu.popleft()
    if now!=1:
      pre=qu.popleft()
    else:
      pre=0
    count=1
    for i in edge[now]:
      if i!=pre:
        qu.append(i)
        qu.append(now)
        if now!=1 and ans[(pre,now)]==count:
          count+=1
        ans[(now,i)]=count
        count+=1
  return ans
bfs(1,ans)
for i,j in ab:
  print(ans[(i,j)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)

edge=[[] for i in range(n)]
k=0

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

color_dict={}

def dfs(x, last=-1, ban_color=-1):
    global k
    color=1
    for to in edge[x]:
        if to==last:
            continue
        if color==ban_color:
            color+=1
        color_dict[(x,to)]=color
        k=max(k,color)
        dfs(to,x,color)
        color+=1
dfs(0)
print(k)

for i in range(n-1):
    if (a[i],b[i]) in color_dict:
        print(color_dict[(a[i],b[i])])
    else:
        print(color_dict[(b[i],a[i])])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  from collections import deque
  from collections import defaultdict
  n=int(input())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  g=[[] for _ in range(n)]
  for i,abi in enumerate(ab):
    a,b=abi
    g[b-1].append(a-1)
    g[a-1].append(b-1)
  todo=deque([(0,-1)])
  dc={}
  while len(todo)>0:
    a,pc=todo.popleft()
    l=g[a]
    c=0
    for li in l:
      d,e=min(a,li),max(a,li)
      if (d,e) not in dc:
        c+=1 if c+1!=pc else 2
        dc[(d,e)]=c
        todo.append([li,c])
  print(max(dc.values()))
  for a,b in ab:
    print(dc[(a-1,b-1)])
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  g=[[] for _ in range(n)]
  for i,abi in enumerate(ab):
    a,b=abi
    g[b-1].append([a-1,i])
    g[a-1].append([b-1,i])
  seen=[-1]*(n-1)
  todo=[[0,-1]]
  while len(todo)>0:
    a,ca=todo.pop()
    l=g[a]
    c=0
    for li in l:
      if seen[li[1]]==-1:
        c+=1 if c+1!=ca else 2
        seen[li[1]]=c
        todo.append([li[0],c])
  print(max(seen))
  for s in seen:
    print(s)
if __name__=='__main__':
  main()

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)

while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        
# 根以外の頂点は、唯一の親を持つことから、
# vの親がpであるとき → color[v] に辺 pvの色を持たせると定めて色を管理
color = [-1] * (N+1)
for x in seen:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

ans = []
for a,b in ab:
    ans.append(color[b])

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque, defaultdict

sys.setrecursionlimit(10**7)
N = int(input())
edges = [[] for _ in range(N)]
nodeinput = defaultdict(int) # (node index, node index) -> index
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    if a > b:
        a, b = b, a
    nodeinput[(a-1, b-1)] = i

seen = [0]*N
output = [0]*(N-1) # color

stack = deque()
stack.append([(0, -1)]) # node index, parent color
maxcolor = 0
while stack[0]:
    nstack = []
    cstack = stack.pop()
    #print('cstack:', cstack)
    for val in cstack:
        ni, pc = val
        seen[ni] = 1
        color = 1
        if color == pc:
            color += 1
        for edgei in edges[ni]:
            if seen[edgei] == 0:
                nstack.append((edgei, color))
                if ni > edgei: # keep: ni < edgei
                    ni, edgei = edgei, ni
                output[nodeinput[(ni, edgei)]
                ] = color
                if maxcolor < color:
                    maxcolor = color
                color += 1
                if color == pc:
                    color += 1
    stack.append(nstack)

print(maxcolor)
for out in output:
    print(out)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    q = deque()
    q.append([s, 0])
    while q:
        x, y = q.popleft()
        for g in G[x]:
            if color[g[1]] == -1:
                color[g[1]] = y + 1
                y += 1
                y %= k
                q.append([g[0], y])
    return

n = int(input())
G = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, i])
    G[b].append([a, i])
k = 0
for g in G:
    k = max(k, len(g))
color = [-1] * (n - 1)
bfs(0)
print(k)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])
from collections import deque
d = deque([(0,-1)])
ans = [0 for i in range(n-1)]
while d:
    a,noc = d.popleft()
    c = 1 if noc != 1 else 2
    for b,i in g[a]:
        if ans[i] == 0:
            ans[i] = c
            d.append((b,c))
        else:
            continue
        c += 1 if c+1 != noc else 2
print(max(ans))
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n=int(input())

#n番目の頂点が「どの頂点と、何本目の辺つながっているか」をsetの配列で持つ
g = [[] for _ in range(n)]
#i本目の辺(n頂点なのでn-1本ある)が何色か（つまり出力する答え）の配列
ans = [0]*(n-1)

def dfs(target,parent_color,parent):
    next_color = 1

    for a,b in g[target]:
        if target == parent:
            continue
        if next_color == parent_color:
            next_color += 1
        if ans[b] != 0:
            continue
        
        ans[b] = next_color
        next_color += 1
        dfs(a,ans[b],target)
    
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append((b,i))
    g[b].append((a,i))

#print(g)
dfs(0,-1,-1)

print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    # 入力
    n = int(input())
    nodes_edges_data = {e: [] for e in range(1, n + 1)}
    edges_data_to_number = {}
    for i1 in range(n - 1):
        a, b = tuple(map(int, input().split()))
        nodes_edges_data[a].append(b)
        nodes_edges_data[b].append(a)
        edges_data_to_number[(a, b)] = i1
        edges_data_to_number[(b, a)] = i1
    # 処理
    edges_color = [-1] * (n - 1)
    nodes_num = [0] * (n + 1)
    nodes_num[1] = -1
    max_edges_per_node = 0
    nodes_next = deque([1])
    nodes_next_next = deque()
    nodes_seen = set()
    while len(nodes_seen) < n:
        while nodes_next:
            e = nodes_next.pop()
            nodes_seen.add(e)
            adj_nodes = nodes_edges_data[e]
            nodes_next_next += adj_nodes
            num_of_nodes = len(adj_nodes)
            max_edges_per_node = max(max_edges_per_node, num_of_nodes)
            num = nodes_num[e]

            for adj_node in adj_nodes:
                if not adj_node in nodes_seen:

                    num = (num + 1) % max_edges_per_node
                    edges_color[edges_data_to_number[(e, adj_node)]] = num
                    #nodes_num[adj_node] = (num + 1) % max_edges_per_node
                    nodes_num[adj_node] = num
        nodes_next_next_set = set(nodes_next_next)
        nodes_next += deque(nodes_next_next_set - nodes_seen)
        nodes_next_next = deque()

    # 出力
    print(max(edges_color) + 1)
    for i in range(n - 1):
        print(edges_color[i] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    root = [[] for _ in range(N)]
    node = [0] * N
    color = [0] * (N-1)
    for i in range(N-1):
        a,b = LI()
        root[a-1].append((b-1,i))
        root[b-1].append((a-1,i))

    q = [(0,0)]
    ans = 0
    while q:
        i,c = q.pop()
        node[i] = 1
        next_c = 1
        for d,x in root[i]:
            if node[d]: continue
            if next_c == c: next_c += 1
            color[x] = next_c
            ans = max(ans,next_c)
            q.append((d,next_c))
            next_c += 1
    print(ans)
    print(*color,sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in [0]*n]
for i in range(~-n):
    a, b = map(int, input().split())
    a -= 1;b -= 1
    edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
    count = 1
    for to, i in edge[now]:
        # 親の色と同じとき
        if count == color:
            count += 1
        ans[i] = count
        dfs(to, count)
        count += 1

# 開始根は0番目に
dfs(0, 0)

print(max(ans))
for p in ans:
    print(p)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()

graph = [[] for _ in range(N)]
edges = []
 
for _ in range(N - 1):
  a, b = inputIL()
  edges.append((a-1, b-1))
  
for a, b in edges:
  graph[a].append(b)
  graph[b].append(a)
  
k = max(len(edges) for edges in graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [ None for _ in range(N) ]
colored = {}

def youcanusethiscolor(u):
  for c in colors:
    if c == usedcolor[u]:
      continue
    yield c
    
for u in range(N):
  color = youcanusethiscolor(u)
  for v in graph[u]:
    if (u,v) not in colored and (v,u) not in colored:
      now = next(color)
      colored[(u,v)] = colored[(v,u)] = now
      usedcolor[v] = now
  
print(k)
for a,b in edges:
  print(colored[(a,b)])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]

col_max = 0
for i in range(N-1):
  a, b = ab[i]
  graph[a] += [b]
  graph[b] += [a]

for i in range(N):
  col_max = max(col_max, len(graph[i]))
print(col_max)

def bfs(s):
  q = deque([s])
  col = [-1]*N
  col[s] = 0
  edge_col = {}

  while q:
    c = 1
    u = q.pop()
    for v in graph[u]:
      if col[v] == -1:
        if c == col[u]:
          c += 1
        col[v] = c
        q.append(v)
        edge_col[(u, v)] = c
        edge_col[(v, u)] = c
        c += 1
  return edge_col

col = bfs(0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)

    for i in range(N-1):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,i))
        G[b].append((a,i))
    
    res = [0] * (N-1)
    dfs(0,-1,-1,G,res)
    print(max(res))
    print(*res, sep='\n')
    
def dfs(v,p,pc,G,res):
    next_c = 1
    for next_v, num in G[v]:
        if next_v == p:
            continue
        if next_c == pc:
            next_c += 1
        
        res[num] = next_c
        dfs(next_v,v,next_c,G,res)
        
        next_c += 1

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
AB = [[] * 2 for _ in range(n - 1)]
graph = [[] for _ in range(n + 1)]

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

root = 1
parent = [0] * (n + 1)
order = []
stack = [root] # 根を stack に入れる

while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)

color = [-1] * (n + 1)
for x in order:
	ng = color[x]
	c = 1
	for y in graph[x]:
		if y == parent[x]:
			continue
		if c == ng:
			c += 1
		color[y] = c
		c += 1

res = []
for a, b in AB:
	if parent[a] == b:
		res.append(color[a])
	else:
		res.append(color[b])

print(max(res)) # root
print('\n'.join(map(str, res)))