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 deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
hen=[tuple(map(int,input().split())) for i in range(n-1)]
color={(hen[i][0]-1,hen[i][1]-1):0 for i in range(n-1)}
for i in range(n-1):
  a,b=hen[i][0],hen[i][1]
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
mcol=0
ne=0
for i in range(n):
  if len(ki[i])>mcol:
    mcol=len(ki[i])
    ne=i
print(mcol)
from collections import deque
d=deque()
d.append(ne)
visited=[False]*n
visited[ne]=True
col=[0]*n
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    if g>i:
      x,y=i,g
    else:
      x,y=g,i
    color[(x,y)]=col[g]%mcol+1
    col[g],col[i]=color[(x,y)],color[(x,y)]
for i in hen:
  print(color[(i[0]-1,i[1]-1)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N - 1)


def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1


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

Submission status: Accepted

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, id): self.to, self.id = to, id

def main():
    N = Z()
    col = [0] * (N-1)
    G = collections.defaultdict(list)
    for i in range(N-1):
        a, b = ZZ()
        G[a].append(edge(b, i))
        G[b].append(edge(a, i))
    numCol = 0
    for i in range(1, N+1): numCol = max(numCol, len(G[i]))

    def dfs(v):
        colSet = set()
        for ed in G[v]:
            if col[ed.id] != 0: colSet.add(col[ed.id])
        c = 1
        for ed in G[v]:
            if col[ed.id] != 0: continue
            while c in colSet: c += 1
            col[ed.id] = c
            c += 1
            dfs(ed.to)

    dfs(1)
    print(numCol)
    for i in range(N-1): print(col[i])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for i in range(n)]
edge = []

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

ans = []
def color(a, c=-1, fromnode=None):
    i = 0
    cp = 0
    while i < len(tree[a]):
        nxt, idn = tree[a][i]
        if nxt==fromnode:
            i+=1
            continue 
        if cp == c:
            cp+=1
        ans.append([idn, cp])
        color(nxt, cp, a)
        i+=1
        cp+=1

color(0)

ans.sort()
ans = [c+1 for idn, c in ans]
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id
N = int(input())
graph = {}
ans = [0] * (N-1)
def dfs(v, c=-1, p=-1):
    global graph, ans
    k = 1
    for edge in graph[v]:
        nv = edge.to
        if nv == p:continue
        if k == c:k += 1
        ans[edge.id] = k
        dfs(nv, k, v)
        k += 1
def main():
    global N, graph, ans
    for i in range(N):
        graph[i] = set()
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a-1].add(Edge(b-1, i))
        graph[b-1].add(Edge(a-1, i))
    color_count = 0
    for i in range(N):
        color_count = max(color_count, len(graph[i]))
    dfs(0, 0, -1)
    print(color_count)
    for x in ans:
        print(x)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = dict()
    # vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if not ((v1, v2) in vc):
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[(v1, v2)] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[(v1, v2)])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

N, *ab = map(int, open(0).read().split())
B = ab[1::2]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

    def dfs(vNow, vPar, clrPar):
        clr = 1
        for v2, i in adjL[vNow]:
            if v2 == vPar: continue
            if clr == clrPar:
                clr += 1
            anss[i] = clr
            dfs(v2, vNow, clr)
            clr += 1

    anss = [0] * (N-1)
    dfs(0, -1, 0)

    print(max(anss))
    print('\n'.join(map(str, anss)))


solve()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
arr=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    arr[a-1].append([b-1,i])
    arr[b-1].append([a-1,i])

que=deque([0])
ans=[0]*(n-1)
par=[0]*n
par[0]=-1
while que:
    x=que.popleft()
    p=par[x]
    color=1
    for tup in arr[x]:
        if p==color:
            color+=1
        if ans[tup[1]]==0:
            ans[tup[1]]=color
            par[tup[0]]=color
            color+=1
            que.append(tup[0])
print(max(ans))
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
# ある頂点で、子供に対して順に1,2,3...と辺の色を渡していく
# 親から来た色を持っておき、親から来た色と同色になったときはスキップして次の色を渡す
# グラフ構築の際に、辺の番号を持っておく

import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a-1].append([b-1,i])
  G[b-1].append([a-1,i])
  
ans = [0 for i in range(N - 1)]
from collections import deque
# 頂点、親から来た色、親
q = deque([[0, 0, -1]])
while q:
  v,pcol,parent = q.popleft()
  cnt = 1
  for child in G[v]:
    if child[0] == parent:
      continue
    if cnt == pcol:
      cnt += 1
    ans[child[1]] = cnt
    q.append([child[0],cnt,v])
    cnt += 1

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

Submission status: Accepted

Solution code:
n=int(input())
nextlist=[[] for _ in range(n)]
ablist=[]
for i in range(n-1):
    a,b=map(int,input().split())
    ablist.append((a,b))
    nextlist[a-1].append(b)
    nextlist[b-1].append(a)

nc=0

for i, next in enumerate(nextlist):
    tmp=len(next)
    if tmp>nc:
        nc=tmp
        nci=i+1
print(nc)

linedic={}

seen=set()
todo=[[[nci,0]],[]]
seen.add(nci)

i=0
while todo[i] != []:
    if i ==0:
        x=1
    else:
        x=0
    todo[x]=[]
    
    for to in todo[i]:
        tmp=to[1]
        k=1
        for next in nextlist[to[0]-1]:
            if not next in seen:
                if k == tmp:
                    k +=1
                seen.add(next)
                todo[x].append([next,k])
                linedic[(min(to[0],next),max(to[0],next))]=k
                k += 1
                
    i=x

for ab in ablist:
    print(linedic[ab])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque

def solve():
    N = II()
    E = [[] for _ in range(N)]

    for i in range(N-1):
        a, b = MI1()
        E[a].append((b, i))
        E[b].append((a, i))

    q = deque([(0, -1, -1)])
    ans = [0] * (N-1)
    while len(q) > 0:
        current, v_pre, c_pre = q.popleft()
        color = 1
        for (nv, idx) in E[current]:
            if nv == v_pre: continue
            if color == c_pre:
                color += 1
            q.append((nv, current, color))
            ans[idx] = color
            color += 1

    print(max(ans))
    printlist(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque

def solve():
    N = II()
    E = [[] for _ in range(N)]

    out = []
    for i in range(N-1):
        a, b = MI1()
        E[a].append(b)
        E[b].append(a)
        out.append((a, b))

    q = deque([(0, -1, -1)])
    memo = {}
    max_color = 0
    while len(q) > 0:
        current, v_pre, c_pre = q.popleft()
        color = 1
        for nv in E[current]:
            if nv == v_pre: continue
            if color == c_pre:
                color += 1
            q.append((nv, current, color))
            memo[(min(nv, current), max(nv, current))] = color
            max_color = max(max_color, color)
            color += 1
    # print(memo)

    print(max_color)
    for t in out:
        print(memo[t])

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

n=int(input())
l=[list(nii()) 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=[-1 for i in range(n)]
col[0]=0

que=deque()
que.append(0)

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

  t_col=1
  for i in tree[x]:
    if col[i]!=-1:
      continue
    if t_col==col[x]:
      t_col+=1
    que.append(i)
    col[i]=t_col
    ans_dict[(x+1,i+1)]=t_col
    ans_dict[(i+1,x+1)]=t_col
    t_col+=1

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

Submission status: Accepted

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)
for line in ab:
    print(d2[line])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
lis = []
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
    lis.append([a,b,i])
mx = 0
for i in range(n):
    ki[i].sort()
    mx = max(mx,len(ki[i]))
lis = sorted(lis, key=lambda x:x[0])
lis = sorted(lis, key=lambda x:x[1])
lis2 = [[] for i in range(n)]
cnt = 0
for i in range(n-1):
    lis2[lis[i][0]].append(lis[i])
#print(lis2)

#print(ki)
def bfs(ki,lis2):
    d = [True] * n
    que = deque([(0,-1)])
    d[0] = False
    while len(que) != 0:
        val = que.popleft()
        cnt = 1
        cnt2 = 0
        for i in range(len(ki[val[0]])):
            if d[ki[val[0]][i]] == True:
                d[ki[val[0]][i]] = False

                #print(cnt,cnt2,val,i)
                if val[1] == cnt:
                    cnt += 1
                lis2[val[0]][cnt2].append(cnt)
                que.append([ki[val[0]][i],cnt])
                cnt += 1
                cnt2 += 1

    return lis2
lis2 = bfs(ki,lis2)
#print(lis2)
val = 0
for i in range(n):
    val = max(len(ki[i]),val)
print(val)
lis = []
for i in range(n):
    for j in range(len(lis2[i])):
        lis.append(lis2[i][j])
lis = sorted(lis,key=lambda x:x[2])
for i in range(n-1):
    print(lis[i][3])

Submission status: Accepted

Solution code:
import sys
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(i,r):
    c=1
    for (x,y) in T[i]:
        c+=(c==r)
        C[y]=c
        f(x,c)
        c+=1
f(0,0)
print(max(C))
for c in C:
    print(c)

Submission status: Accepted

Solution code:
def f(u, i, d, t, vis):
    if vis[u]:
        return
    vis[u] = True
    z = t[u]

    c = 1
    for v in z:
        if vis[v]:
            continue
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t, vis)
        c += 1


def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        t[j].append(i)
        m.append([i, j])
    d = defaultdict(dict)
    vis = [False for _ in range(n + 1)]
    f(1, len(t[1]) + 1, d, t, vis)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t)) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 連想配列
from collections import deque
N = int(input())
ab = {}
abl = []
path = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
    abl.append((a-1,b-1))
    ab[(a-1,b-1)] = 0
color = [0]*N
color[0] = -1
q = deque([])
q.append(0)
max = 0

while len(q)>0:
    cn = q.popleft()
    ccolor = color[cn]
    ncolor = 1
    for i in path[cn]:
        if color[i] == 0:
            if ccolor != ncolor:
                color[i] = ncolor
                ab[(cn,i)] = ncolor
                ncolor += 1
            else:
                color[i] = ncolor+1
                ab[(cn,i)] = ncolor+1
                ncolor += 2
            if color[i] > max:
                max = color[i]
            q.append(i)
print(max)
for i in abl:
    print(ab[i])

Submission status: Accepted

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

n=int(input())
l=[list(nii()) for i in range(n-1)]

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

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

dq=deque()
dq.append((0,0))

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.pop()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

dq=deque()
dq.append((0,0))

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.popleft()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

dq=deque()
dq.append((0,0))

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.pop()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

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

Submission status: Accepted

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

d = deque()
dic = {}
dic_l = {}

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

    if(a in dic):
        dic[a].append(b)
    else:
        dic[a] = [b]
    
    if(b in dic):
        dic[b].append(a)
    else:
        dic[b] = [a]
    
    l = max(a,b)
    s = min(a,b)
    dic_l[s,l] = i


#print(dic_l)
mx = 0
for k in dic:
    mx = max(mx,len(dic[k]))

#print("mx",mx)
col = [i+1 for i in range(mx)]
ans = [0 for _ in range(n-1)]
seen = {1}

cnt = 0
tmp = deque()
for i in dic[1]:
    if not(i in seen):
        d.append(i)
        seen.add(i)
        tmp.append(1)
        tmp.append(i)

    load_key = (1,i)
    l_num = dic_l[load_key]
    ans[l_num] = col[cnt]
    cnt += 1


while d:
    nxt = d.popleft()
    tmp_1 = tmp.popleft()
    tmp_2 = tmp.popleft()
    ng = (tmp_1,tmp_2)
    #print(ng)
    ng_col = ans[dic_l[ng]]
    cnt = 0
    for i in dic[nxt]:
        if not(i in seen):
            d.append(i)
            seen.add(i)
            tmp.append(nxt)
            tmp.append(i)
            l = max(nxt,i)
            s = min(nxt,i)
            load_key = (s,l)
            l_num = dic_l[load_key]
            while cnt+1 == ng_col:
                cnt += 1
            ans[l_num] = col[cnt]
            cnt += 1

print(mx)
for s in ans:
    print(s)

Submission status: Accepted

Solution code:
n=int(input())

import sys
sys.setrecursionlimit(10 ** 7)

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

max_color=0
for graph_i in graph:
    max_color=max(max_color, len(graph_i))
print(max_color)

colors=[-1]*(n-1)

def dfs(v, color, pre):
    if color!=0:
        nc=0
    else:
        nc=1
    for e in graph[v]:
        # print(e,nc)
        if e[0]==pre:
            continue
        colors[e[1]]=nc
        dfs(e[0],nc,v)
        nc+=1
        if nc==color:
            nc+=1

dfs(0,-1,-1)

for c in colors:
    print(c+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b#3-3-dfs-%E3%81%AE%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

    N = int(input())
    M = N-1  # 頂点数，辺数
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append((b, i))
        G[b].append((a, i))

    seen = [False]*N
    res = [0]*M

    def dfs(G, v):
        col = 1
        parent_col = -1
        if col == parent_col:
            col += 1
        seen[v] = True
        stack = deque([(v, -1)])
        while stack:
            v, parent_col = stack.pop()
            col = 1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if col == parent_col:
                    col += 1
                res[edge_ind] = col
                seen[next_v] = True
                stack.append((next_v, col))
                col += 1

    # 頂点 0 をスタートとした探索
    dfs(G, 0)
    print(max(res))
    for i in res:
        print(i)


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b#3-3-dfs-%E3%81%AE%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

    N = int(input())
    M = N-1  # 頂点数，辺数
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append((b, i))
        G[b].append((a, i))

    seen = [False]*N
    res = [0]*M

    def dfs(G, v, parent_col):
        col = 1
        if col == parent_col:
            col += 1
        seen[v] = True
        stack = deque([(v, -1)])
        while stack:
            v, parent_col = stack.pop()
            col = 1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if col == parent_col:
                    col += 1
                res[edge_ind] = col
                seen[next_v] = True
                stack.append((next_v, col))
                col += 1

    # 頂点 0 をスタートとした探索
    dfs(G, 0, -1)
    print(max(res))
    for i in res:
        print(i)


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b#3-3-dfs-%E3%81%AE%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

    N= int(input())
    M=N-1  # 頂点数，辺数
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append((b, i))
        G[b].append((a, i))

    seen = [False]*N
    res = [0]*M


    def dfs(G, v, pc):
        color = 1
        if color == pc:
            color += 1
        seen[v] = True
        stack = deque([(v,-1)])
        while stack:
            v,pc = stack.pop()
            color=1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if color == pc:
                    color += 1
                res[edge_ind] = color
                seen[next_v] = True
                stack.append((next_v,color))
                color+=1

            

    # 頂点 0 をスタートとした探索
    dfs(G, 0, -1)
    print(max(res))
    for i in res:
        print(i)



resolve()

Submission status: Accepted

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, 0)])
    sd = set()
    ce = dict()
    while sn:
        v, cv = sn.popleft()
        sd.add(v)
        ci = 1
        for vn in al[v]:
            if vn in sd:
                continue
            if ci == cv:
                ci += 1
            if (v, vn) in e:
                ce[(v, vn)] = ci
            else:
                ce[(vn, v)] = ci
            sn.append((vn, ci))
            ci += 1
    for k, _ in sorted(e.items(), key=itemgetter(1)):
        print(ce[k])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

        
N = int(input())
graph = {}
colored = [-1]*(N+1)
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,colored)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Accepted

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

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

que = deque([0])
ans = [0] * (n - 1)
visited = [-1] * n
visited[0] = 0
while que:
    a = que.popleft()
    c = 1
    for b in graph[a]:
        if visited[b] < 0:
            if visited[a] == c:
                c += 1
            visited[b] = c
            ans[edges[(a, b)]] = c
            c += 1
            que.append(b)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input =sys.stdin.readline
N = int(input())

#構造入力
color_max =0
connection ={i:deque() for i in range(1,N+1)}
edge_color={}
A =[(-1,-1)]*N
for i in range(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)
    edge_color[(a,b)] =-1
    A[i] =(a,b)
    color_max =max(color_max, len(connection[a]) , len(connection[b]))

#幅優先探索で色塗る
passed =set()
#edge_color ={i:-1 for i in range(1,N+1)}
parent ={i:-1 for i in range(1,N+1)}
parent[1] =0
dq =deque()
dq.append(1)
color =0
#prev =0 #頂点１の親は０とする
edge_color[(0,1)] =0
#node_color[1] =0
while dq:
    now =dq.popleft()
    passed.add(now)
    na_max =max(parent[now],now)
    na_min =min(parent[now],now)
    i_color =edge_color[(na_min,na_max)]
    for next in connection[now]:
        if next in passed:
            continue
        else:
            i_color +=1
            n_max =max(now,next)
            n_min =min(now,next)
            edge_color[(n_min,n_max)] =(i_color)% color_max 
            dq.append(next)
            parent[next] =now
print(color_max)
del edge_color[(0,1)]
for i in range(1,N):
    print(edge_color[A[i]] +1 )