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

N = int(input())
EhasV = [set() for x in range(N)]
EhasVnums = [0] * N
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)
    EhasVnums[a] += 1
    EhasVnums[b] += 1

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,EhasVnums[x]+1)) for x in range(N)]
Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
while q:
    v1 = q.pop()
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)

print(*([K]+Ecolor),sep='\n')

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10000000)

def readInts():
  return [int(s) for s in input().split(" ")]

def next_color(c, exclude):
  if c == exclude:
    return c + 1
  else:
    return c

def traverse(N, edges, k, ans, v, exclude = 0):
  c = next_color(1, exclude)
  for (b, i) in edges[v]:
    ans[i] = c
    traverse(N, edges, k, ans, b, c)
    c = next_color(c + 1, exclude)

def main():
  N = readInts()[0]
  edges = [[] for _ in range(N)]
  counts = [0 for _ in range(N)]
  for i in range(N-1):
    a, b = readInts()
    a -= 1
    b -= 1
    edges[a].append((b, i))
    counts[a] += 1
    counts[b] += 1

  k = max(counts)
  ans = [0 for _ in range(N-1)]
  traverse(N, edges, k, ans, 0)

  print(k)
  for i in range(N-1):
    print(ans[i])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# ABC146d
ans = 1


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())

    n = int(input())

    edges = [list() for _ in range(n)]
    colors = [-1] * (n - 1)

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

    def dfs(i, color, pre):
        nc = 0 if color != 0 else 1
        for e in edges[i]:
            if e[0] == pre:
                continue
            global ans
            if ans < len(edges[i]):
                ans = len(edges[i])
            colors[e[1]] = nc
            dfs(e[0], nc, i)
            nc += 1
            if nc == color:
                nc += 1
    dfs(0, -1, -1)
    print(ans)
    for i in colors:
        print(i+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

# txt = "100000"
# for i in range(99999):
#     txt += "\n" + str(i) +" " +  str(i+1)
# def i():
#     for l in txt.split("\n"):
#         yield l
# input = i().__next__
def main():
    N = int(input())
    mawari = [[] for _ in range(N)]
    e_num = [0] * N 
    for l in range(N-1):
        i, j = [int(x)-1 for x in input().split()]
        e_num[i] += 1
        e_num[j] += 1
        mawari[i].append((j, l))
        mawari[j].append((i, l))
    look = -1
    for ind, l in enumerate(e_num):
        if l == 1:
            look = ind
            break
    color = [-1]*(N-1)
    c_prev = deque([-1])
    to_visit = deque([look])
    maxc = 0
    while len(to_visit)>=1:
        look = to_visit.pop()
        c = 0
        prevc = c_prev.pop()
        for i,j in mawari[look]:
            if color[j] != -1:
                continue
            if c == prevc:
                c += 1
            color[j] = c
            c_prev.append(c)
            to_visit.append(i)
            maxc = max(maxc, c)
            c += 1
        
    # mc, c = a(N, 0, look, color, mawari, -1)
    print(maxc+1)
    for i in color:
        print(i+1)


# def a(N, maxc, look, color, mawari, prev):
#     nexts = mawari[look]
#     c = 0
#     for i,j in nexts:
#         if c == prev:
#             c += 1
#         color[j] = c
#         maxc = max(maxc, a(N, maxc, i, color, mawari, c)[0])
#         c += 1
#     return maxc, color
    

main()

Submission status: Accepted

Solution code:
N = int(input())
E ={i:[] for i in range(N+1)}
ab = []
for i in range(N-1):
  a,b = [int(x)  for x in input().split()]
  ab.append((a,b,i))
  E[a].append((b,i))
  E[b].append((a,i))
visited=[0]*(N+1)
stk = [[1,-1,0]]
ans = [0]*(N-1)
while stk:
  v,p,r = stk.pop()
  if visited[v]:
    continue
  visited[v]=1
  a = 1
  for i,j in E[v]:
    if i!=p:
      if a!=r:
        stk.append([i,v,a])
        ans[j]=a
        a=a+1
      else:
        a=a+1
        stk.append([i,v,a])
        ans[j]=a
        a = a+1
print(max(ans))
for i in range(N-1):
	print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

N=int(input())
edges = [0 for i in range(N)]
edge_l = [[] for i in range(N)]
cols = [0 for i in range(N)]
out = 0
seen = [False for i in range(N)]
seen2 = [False for i in range(N)]

def paint(cur, parC):
  if seen[cur]:
    return
  curC = 1
  seen[cur] = True
  for e in edge_l[cur]:
    if not seen2[e[1]]:
      seen2[e[1]] = True
      if curC == parC:
        curC+=1
      cols[e[1]] = curC
      paint(e[0], curC)
      curC+=1
  return

for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a]+=1
  edges[b]+=1
  edge_l[a].append([b,i])
  edge_l[b].append([a,i])
  out = max(out,edges[a],edges[b])
print(out)
paint(0,0)
for i in range(N-1):
  print(cols[i])

Submission status: Accepted

Solution code:
import collections
def main():

    N = int(input())
    edge = [[] for _ in range(N)]
    ncol = 0
    start = None
    graph = collections.defaultdict(list)
    pair = collections.defaultdict(dict)
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(i)
        edge[b-1].append(i)
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        pair[a-1][b-1] = i
        pair[b-1][a-1] = i
        if len(graph[a-1]) > ncol:
            ncol = len(graph[a-1])
            start = a-1
        if len(graph[b-1]) > ncol:
            ncol = len(graph[b-1])
            start = b-1

    n = max(edge)
    cols = [0 for _ in range(N-1)]
    idx = 1
    for i in edge[start]:
        cols[i] = idx
        idx += 1
    visited = set([start])
    m = ncol
    cur = [[h, cols[pair[start][h]]] for h in graph[start]]

    while cur:
        temp = []
        for node, c in cur:
            idx = 1
            for h in graph[node]:
                if cols[pair[node][h]] == 0:
                    if idx == c:
                        idx += 1
                    cols[pair[node][h]] = idx
                    idx += 1
                    temp.append([h, cols[pair[node][h]]])
        cur = temp
    print(m)
    for i in range(N-1):
        print(cols[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import itertools


UNDEF = 0


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF] * (n - 1)
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        for i in itertools.count(1):
            if len(cur_cols) + len(new_cols) >= num_adj:
                break
            elif i not in cur_cols:
                new_cols.add(i)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    a=[0]*(N-1)
    b=[0]*(N-1)
    for i in range(N-1):
        a[i],b[i]=map(int,input().split())
    a_i=np.argsort(a)
    l=[]
    d={1:0}
    p_color=0
    currentcolor=0
    currentnum=0
    K=0
    for i in a_i:
        if a[i]!=currentnum:
            p_color=d[a[i]]
            currentnum=a[i]
            currentcolor=0
        currentcolor+=1
        if currentcolor == p_color:
            currentcolor+=1
        l.append(currentcolor)
        K=max(K,currentcolor)
        d[b[i]]=currentcolor
    print(K)
    l2=[0]*(N-1)
    for i,ai in enumerate(a_i):
        l2[ai]=l[i]
    for z in l2:
        print(z)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n = int(input())
neibors = [dict() for i in range(n + 1)] # index to name
edges = []
for i in range(n-1):
    e = [int(s) for s in input().split()]
    edges.append(e)
for a,b in edges:
    neibors[a][b] = None
    neibors[b][a] =  None

colorCount = 0
for i in range(1,n+1):
    colorCount = max(colorCount, len(neibors[i]))

visited = set()
queue = collections.deque()

visited.add(1)
color = 0
for node in neibors[1]:
    color += 1
    neibors[1][node] = color
    queue.append(node)

while queue:
    x = queue.popleft()
    for node in neibors[x]:
        if node in visited:
            fatherColor = neibors[node][x]
            neibors[x][node] = fatherColor
    color = 0
    for node in neibors[x]:
        if neibors[x][node] is None:
            color += 1
            if color == fatherColor:
                color += 1
            neibors[x][node] = color
            queue.append(node)
    visited.add(x)

print(colorCount)
for a, b in edges:
    print(neibors[a][b])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
g = [[] for _ in range(N)]
d = {}
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    d[i] = (min(a,b)-1,max(a,b)-1)

q = deque([])
m = 0
s = 0
for i in range(N):
    if len(g[i])>m:
        s = i
        m = len(g[i])
done = [-1]*N
done[s] = 0
ans = {}
cnt = 1
for i in g[s]:
    done[i] = cnt
    ans[(min(i,s),max(i,s))] = cnt
    cnt += 1
    q.append(i)

while q:
    cnt = 1
    i = q.popleft()
    for j in g[i]:
        if done[j]==-1:
            if done[i]==cnt:
                cnt += 1
            ans[min(i,j),max(i,j)] = cnt
            done[j] = cnt
            cnt += 1
            q.append(j)
m = 0
for k in ans:
    m = max(m,ans[k])
print(m)
for i in range(N-1):
    print(ans[d[i]])

Submission status: Accepted

Solution code:
from collections import deque         
N = int(input())
G = {}
E = {}
E1 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
    E[(a,b)] = 0
    E[(b,a)] = 0
    E1.append((a,b))
col = 0
for x in G:
    col = max(col,len(G[x]))
hist = [0 for _ in range(N+1)]
heap = deque([(1,0)])
while heap:
    x = heap.popleft()
    hist[x[0]] = 1
    if x[1]!=0:
        c = E[(x[0],x[1])]
    else:
        c = 0
    for y in G[x[0]]:
        if hist[y]==0:
            c = c%col+1
            E[(x[0],y)] = c
            E[(y,x[0])] = c
            heap.append((y,x[0]))
print(col)
for i in range(N-1):
    print(E[E1[i]])

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
ls = []
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [(b-1, i)]
  dic[b-1] += [(a-1, i)]
  ls += [(a-1,b-1)]
K = 0
for k in dic.keys():
  if K<len(dic[k]):
    K = len(dic[k])

print(K)
log = [1]*N
ls = [0]*N
stuck = [(0, 0)]
log[0] = 0
ls[0] = 1
ans = [0]*(N-1)
while stuck:
  e, i = stuck.pop()
  b = 1
  for j in range(len(dic[e])):
    ce, h = dic[e][j]
    if log[ce]:
      log[ce] = 0
      ans[h] = (ls[e]+b)%K
      ls[ce] = (ls[e]+b)%K
#      print(h, ls[e], b)
      b += 1
      stuck += [(ce,h)]
      
for x in ans:
  if x==0:
    print(K)
  else:
    print(x)

Submission status: Accepted

Solution code:
N=int(input())
E=[None]*(N-1)
EV=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[i]=[a,b]
  # 相手, 色, 回答出力順(-1は無視)
  EV[a].append([b,-1,i])
  EV[b].append([a,-1,-1])

ans=[0]*(N-1)
# visited=[False]*N

stack=[]
# 対象のノード, 親、親の色
stack.append([0,-1,0])
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  parentcolor=node[2]
  childs=EV[v]
  color=1
  # visited[v]=True
  for i in range(len(childs)):
    child=childs[i]
    child_v=child[0]
    if child_v==parent:
      continue
    if color==parentcolor:
      color+=1
    childs[i][1]=color
    position=child[2]
    if position!=-1:
      ans[position]=color
    stack.append([child_v,v,color])
    color+=1
    
# answer
print(max(ans))
for i in range(len(ans)):
  print(ans[i])

Submission status: Accepted

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

N=int(input())

G = [[] for i 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])

def bfs(x, c, b):
    if seen[x]:
        return
    seen[x] = True
    if b!=-1:
        global k
        color[b] = c
        k = max(k,c)
    t = 1
    for i,b in G[x]:
        if t==c:
            t+=1
        if not(seen[i]):
            bfs(i,t,b)
            t+=1

seen = [False]*N
color = [0]*N
k=0
bfs(0, 0, -1)


print(k)
print(*color[:-1],sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
        
    s = [(1, -1)]
    done = set([1])
    K = 1
    ans = {}
    while s:
        u, c = s.pop()
        used = set([c])
        c = 1
        for v in g[u]:
            if v in done:
                continue
            while c in used:
                c += 1 
                K = max(K, c)
            used.add(c)
            s.append((v, c))
            i, j = min(u, v), max(u, v)
            ans[(i, j)] = c
            done.add(v)
    print(K)
    for a, b in AB:
        print(ans[(a, b)])
    # return ans


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for i in range(n)]
irohash = {}
irojyun = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    a -= 1;b -= 1
    graph[a].append(b)
    graph[b].append(a)
    s = str(min(a,b)) + "," + str(max(a,b))
    irohash[s] = -1
    irojyun.append(s)

#最初の頂点を探す
ii = 0
for i in range(n):
    if len(graph[i]) == 1:
        ii = i
        break


iro = max([len(i) for i in graph])
stack = [[ii,graph[ii][0]]]
s = str(min(ii,graph[ii][0])) + "," + str(max(ii,graph[ii][0]))
irohash[s] = 1
while stack:
    oo = stack.pop()
    b,p = oo[0],oo[1]
    s = str(min(b,p)) + "," + str(max(b,p))
    piro = irohash[s]
    count = 1
    for v in graph[p]:
        s = str(min(p,v)) + "," + str(max(v,p))
        if irohash[s] != -1:continue
        if count == piro:count += 1
        irohash[s] = count
        stack.append([p,v])
        count += 1
print(iro)
for i in range(n-1):
    print(irohash[irojyun[i]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline
from collections import defaultdict
N = int(input())
g = defaultdict(list)
color = defaultdict(int)
gn = [0]*(N+1)
edges = []
for i in [0]*(N-1):
    a,b = map(int,input().split())
    edges.append((a,b))
    g[a].append(b)
    g[b].append(a)
    gn[a]+= 1
    gn[b]+= 1

M = max(gn)

dq = deque([1])
visited = [False] * (N+1)
ncolor = [-1]*(N+1)
ncolor[1] = 0
while dq:
    s = dq.popleft()
    visited[s] = True
    s_clr = ncolor[s]
    for t in g[s]:
        if not visited[t]:
            s_clr = (s_clr + 1) % M
            ncolor[t] = s_clr
            if s < t:
                color[(s,t)] = s_clr
            else:
                color[(t,s)] = s_clr
            dq.append(t)
print(M)
for edge in edges:
    print(color[edge]+1)

Submission status: Accepted

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

n = int(input())
edges = [[] for _ in range(n)]

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

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

q = [0]
visit = [False] * n
visit[0] = True

while q:
    l = q.pop(-1)
    li = []
    for i,j in edges[l]:
        if not visit[i]:
            q.append(i)
            visit[i] = True
        li.append(j)
    li = list(set(li))
    li2 = []
    for i in li:
        li2.append(ans[i])
    li2.sort()
    if li2[0] == -1:
        li2 = li2[1:]
    count = 1
    for i in li:
        while ans[i] == -1:
            if count not in li2:
                ans[i] = count
            count += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def bfs(i, V, E, Ec):
    V[i] = 1
    Q = [(i, 0)]
    while(True):
        Qi = []
        for q, cq in Q:
            c = 1
            for j, idx in E[q]:
                if V[j] == 0:
                    if cq == c:
                        c += 1

                    V[j] = 1
                    Qi.append((j, c))
                    Ec[idx] = c
                    c += 1
        if len(Qi) == 0:
            break
        else:
            Q = Qi
    return V, Ec


n = int(input())
E = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
Ec = [None for _ in range(n - 1)]
V = [0 for _ in range(n + 1)]
_, Ec = bfs(1, V, E, Ec)
print(max(Ec))
for c in Ec:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
edge = [set() for _ in range(N)]
ab = []
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    ab.append((a,b))
    edge[a].add(i)
    edge[b].add(i)

K = 0
ans = [0]*(N-1)
def dfs(node, prev=0):
    global K
    c = 0
    for i in edge[node]:
        c += 1
        if c == prev:
            c += 1
        a, b = ab[i]
        if node == a:
            x = b
        else:
            x = a
        edge[x].remove(i)
        ans[i] = c
        dfs(x, c)
    if c >= K:
        K = c

dfs(0)
print(K)
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

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

N = int(input())
P = [[] for i in range(N)]
ans = [0] * (N - 1)

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


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

while len(q) > 0:
    c, n = q.popleft()
    ac = 1
    for l, i in P[n]:
        if ac == c:
            ac += 1
        q.append((ac, l))
        ans[i] = ac
        ac += 1

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

Submission status: Accepted

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


N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for i in range(N-1):
    adj[AB[i][0]-1].append([AB[i][1]-1,i])
    adj[AB[i][1]-1].append([AB[i][0]-1,i])


col = [0]*(N-1)
visited = [False] * N
visited[0] = True
def dfs(v, color):
    child = adj[v]
    ctmp = 1
    for u,idx in child:
        if not(visited[u]):
            if ctmp == color:
                ctmp += 1
            col[idx] = ctmp
            visited[u] = True
            dfs(u,ctmp)
            ctmp += 1
    return 
            
    
    
    

dfs(0,0)
K = max(col)
print(K)
for k in col:
    print(k)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(a,b)]=i

    ans=[None]*(n-1)
    k=max(len(E[v]) for v in range(n))

    # DFSで辺に色付け
    Q=[0]
    while(Q):
        v=Q.pop()
        if(v):
            p=min(E[v]) # 親はE[v]の最小値
            c=ans[idx[(p,v)]] # 親につながる色
        cnt=1
        for nv in E[v]:
            if(v==0):
                ans[idx[(v,nv)]]=cnt
                cnt+=1
                Q.append(nv)
            else:
                if(cnt==c): cnt+=1
                if(nv==p): continue
                ans[idx[(v,nv)]]=cnt
                cnt+=1
                Q.append(nv)

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

resolve()

Submission status: Accepted

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

EDICT={x:ind for ind,x in enumerate(E)}

ELIST=[[] for i in range(N+1)]
ED=[0]*(N+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)
    ED[x]+=1
    ED[y]+=1

MAX=max(ED)
print(MAX)

from collections import deque

Q=deque()
Q.append(1)

USED=[0]*(N+1)

ANS=[-1]*(N-1)
count=1
BAN=[set() for i in range(N+1)]

while Q:
    x=Q.pop()
    USED[x]=1

    for to in ELIST[x]:
        if USED[to]==1:
            continue

        while count in BAN[x] or count in BAN[to]:
            count=count%MAX+1
            
        ANS[EDICT[tuple(sorted([x,to]))]]=count
        BAN[x].add(count)
        BAN[to].add(count)
        Q.append(to)

for a in ANS:
    print(a)

Submission status: Accepted

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

n = int(input())

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

m_node = 0
for e in nodes:
    m_node = max(len(e), m_node)

use_node = [0 for i in range(n)]
dic = {}
def dfs(node, start_color):
    use_node[node] = 1
    for e in nodes[node]:
        if use_node[e] == 0:
            dic[(node,e)] = (start_color%m_node)+1
            dic[(e,node)] = (start_color%m_node)+1
            dfs(e, (start_color%m_node)+1)
            start_color += 1

dfs(0,0)
print(m_node)
for a,b in abl:
    print(dic[(a-1,b-1)])

Submission status: Accepted

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

def main():
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N-1)]
    
    nodes = [[] for _ in range(N+1)]

    for a, b in AB:
        nodes[a].append(b)
        nodes[b].append(a)

    K = max(map(lambda x: len(x), nodes))
    print(K)
    C = {}

    Q = [(1, None, None)]
    while len(Q) > 0:
        nodeIdx, parent, parentNodeColor = Q.pop()
        colorIdx = 1
        
        for subNodeIdx in nodes[nodeIdx]:
            if subNodeIdx == parent:
                continue

            if colorIdx == parentNodeColor:
                colorIdx += 1

            C[(nodeIdx, subNodeIdx)] = colorIdx
            Q.append((subNodeIdx, nodeIdx, colorIdx))
            colorIdx += 1

    for a, b in AB:
        if (a, b) in C:
            print(C[(a, b)])
        else:
            print(C[(b, a)])



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

k = 0

memo = [-1] * (n-1)
used = [0] * n


q = deque([(0, 0)])
used[0] = 1
while q:
    v, used_number = q.popleft()
    mark = 1
    for nv, i in g[v]:
        if used[nv] > 0:
            continue
        if mark == used_number:
            mark += 1
        k = max(k, mark)
        used[nv] = 1
        memo[i] = mark
        q.append((nv, mark))
        mark += 1
        

print(k)
for m in memo:
    print(m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
mlmis = lambda: [-int(x) for x in input().split()]
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N = ii()
    class Edge:
        def __init__(self, a, b):
            self.a = a
            self.b = b
            self.color = None
        def get_con(self, i):
            return self.b if self.a==i else self.a
    edges = []
    tree = tuple([] for _ in range(N))
    for _ in range(N-1):
        a, b = mis()
        a -= 1
        b -= 1
        edge = Edge(a, b)
        edges.append(edge)
        tree[a].append(edge)
        tree[b].append(edge)
    tasks = [(0, 0)]
    max_color = 1
    for used, node in tasks:
        color = 1
        for edge in tree[node]:
            if color == used:
                color += 1
            if edge.color is not None:
                continue
            edge.color = color
            tasks.append((color, edge.get_con(node)))
            max_color = max(max_color, color)
            color += 1
    print(max_color)
    for edge in edges:
        print(edge.color)



main()

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()

# 戦略
# 一番ハブの多いやつをrootにした木で幅優先する?いや1でいい
# 3つのノードがまっすぐ連なるところは過去の色を再利用したい
# ハブになっているノードが問題では？


# やっぱり幅優先

# どうやって最後に並び替える？そもそも並び替える必要がないか
# color = [1]
# ans = []
# cur_color = 0
# pre_color = 0
# defaultcolor = 1
# pre_parent = 0
# for _ in range(N):
#     a, b = read_ints()
#     if a != pre_parent:
#         # 新しく色付けを始める
#         cur_color = defaultcolor
#         ans.append(cur_color)
#     elif a == pre_parent:
#         # 色付けを拡張していく
#         cur_color += 1
#         ans.append(cur_color)


from collections import defaultdict, deque
tree = defaultdict(lambda: [])
inputls = []
ans = dict()
for _ in range(N - 1):
    a, b = read_ints()
    inputls.append((a, b))
    tree[a].append(b)  # 一方方向だけでいいよね
    ans[(a, b)] = 0  # 初期化

# bfs
que = deque([(1, 0)])  # (親ノード,親の前の色情報)
defcolor = 1
while que:
    cur, pre_color = que.popleft()
    cur_color = defcolor
    for nx in tree[cur]:
        if cur_color == pre_color:
            cur_color += 1

        que.append((nx, cur_color))
        ans[(cur, nx)] = cur_color
        cur_color += 1


print(max(ans.values()))
for a, b in inputls:
    print(ans[(a, b)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append( [b, i])
    graph[b].append( [a, i])

maxc = 0

nexts = [1]
color = [0] * (n-1)
while len(nexts) > 0:
    target = nexts.pop()
    used = set()
    fillable = set()
    for i in range(len(graph[target])):
        cr = color[graph[target][i][1]]
        if cr == 0:
            fillable.add(i)
        else:
            used.add(cr)
    mins = 1
    for i in list(fillable):
        while mins in used:
            mins += 1
        color[graph[target][i][1]] = mins
        nexts.append(graph[target][i][0])
        if mins > maxc:
            maxc = mins
        mins += 1

print(maxc)
for i in color:
    print(i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

n = int(input())
edges = [[] for _ in range(n)]
color = [0 for _ in range(n - 1)]
for e in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, e))
    edges[b - 1].append((a - 1, e))

def dfs(i, p, pcol):
    col = 1
    ret = 0
    for c, e in edges[i]:
        if c != p:
            if col == pcol:
                col += 1
            color[e] = col
            ret = max(ret, dfs(c, i, col))
            col += 1
    return max(ret, col - 1)

print(dfs(0, -1, -1))
for i in range(n - 1):
    print(color[i])