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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

def coloring(n, previous, col): #頂点nにpreviousから色colで辿ってきた。
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col #やってきた頂点との間における色
		else:
			if cnt == col:
				cnt += 1
			color[(x, n)] = cnt
			color[(n, x)] = cnt
			coloring(x, n, cnt)
			cnt += 1

coloring(0, -1, 0)

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Submission status: Accepted

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

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

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


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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
P = [[] for _ in range(N)]
AB = defaultdict(int)

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

C = [-1] * N

def bfs(s):
    d = [-1] * N
    d[s] = 0
    p_old = [s]
    K = -1
    while p_old:
      p_new = []
      for i in p_old:
        c = 1
        for j in P[i]:
          if d[j] != -1:
            continue
          if C[i] == c:
            c += 1
          d[j] = 0
          p_new.append(j)
          C[j] = c
          AB[(i, j)] = c
          K = max(K, c)
          c += 1
      p_old = p_new
    return K

print(bfs(0))

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

Submission status: Accepted

Solution code:
N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

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)
K = -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
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

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

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

Submission status: Accepted

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

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

print(max(color))
for i in e:
    print(color[i])

Submission status: Accepted

Solution code:
#create date: 2020-07-05 13:34

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    to = list()
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
        to.append(b)
    l = [-1] * n
    l[0] = 10**10
    q = deque([0])
    while q:
        v = q.popleft()
        vcolor = l[v]
        for i, w in enumerate(g[v]):
            q.append(w)
            if i < vcolor:
                l[w] = i
            else:
                l[w] = i + 1

    print(max(l[1:])+1)
    for i in to:
        print(l[i]+1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


N, *AB = map(int, open(0).read().split())
g = defaultdict(set)
edges = []
for a, b in zip(*[iter(AB)] * 2):
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)
    edges.append((a, b))

q = deque([0])
visited = [False] * N
visited[0] = True
used = [0] * N
colors_cnt = 1
ans = {}
while q:
    v = q.popleft()
    color = 1
    for nv in g[v]:
        if visited[nv]:
            continue
        if color == used[v]:
            color += 1
        used[nv] = color
        ans[(min(v, nv), max(v, nv))] = color
        color += 1
        q.append(nv)
        visited[nv] = True
    colors_cnt = max(colors_cnt, color - 1)
print(colors_cnt)
[print(ans[(a, b)]) for a, b in edges]

Submission status: Accepted

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = filter(lambda c: c != pc, colors)
    childs = filter(lambda c: c[0] != pv, edge[v])
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print(*ans)

Submission status: Accepted

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = filter(lambda c: c != pc, colors)
    childs = list(filter(lambda c: c[0] != pv, edge[v]))
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    # dequeを使ったスタックによるDFS
    # 子をindexで、親ノードを要素で
    # 今回は彩色のためにどんな順番でpopされたかも保持しておく
    order  = []
    parent = [0] * (n+1)
    visited = [0] * (n+1)
    visited[1] = 1
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if visited[chl]:
                continue
            # 行ったことなかったら1へ
            visited[chl] = 1
            parent[chl] = par
            q.append(chl)
    # 彩色
    # 親と同じにならないように若い番号を割り当てて行く
    cl = [None] * (n+1)
    for par in order:
        # 親の色
        pc = cl[par]
        # 彩色は1以上k以下
        color = 1
        for chl in adj[par]:
            # 隣接リストの親は無視
            if chl == parent[par]:
                continue
            # 親の色と同じなら色を変える
            if pc == color:
                color += 1
            # カラーリストに子indexにcolorを入れる
            cl[chl] = color
            #　他の子は色を変える必要がある
            color += 1
    # 木グラフなので単純に次数最大で考えて問題ない
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    # dequeを使ったキューによるBFS
    # 子をindexで、親ノードを要素で
    # 今回は彩色のためにどんな順番でpopされたかも保持しておく
    order  = []
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            parent[chl] = par
            q.append(chl)
    # 彩色
    # 親と同じにならないように若い番号を割り当てて行く
    cl = [None] * (n+1)
    for par in order:
        # 親の色
        pc = cl[par]
        # 彩色は1以上k以下
        color = 1
        for chl in adj[par]:
            # 隣接リストの親は無視
            if chl == parent[par]:
                continue
            # 親の色と同じなら色を変える
            if pc == color:
                color += 1
            # カラーリストに子indexにcolorを入れる
            cl[chl] = color
            #　他の子は色を変える必要がある
            color += 1
    # 木グラフなので単純に次数最大で考えて問題ない
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]

tree = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(X):
    tree[a].append((b, i))
    tree[b].append((a, i))

visited = [False] * (N + 1)
visited[1] = True
color = [0] * (N - 1)
stack = deque()
stack.append((1, 0))
while stack:
    u, c = stack.popleft()
    tmp = 0
    for v, i in tree[u]:
        if visited[v]:
            continue
            
        tmp += 1
        if tmp == c:
            tmp += 1
            
        visited[v] = True
        color[i] = tmp
        stack.append((v, tmp))

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

Submission status: Accepted

Solution code:

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

colorv = [None] * (n+1)

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

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

    #print("cur", cur)

    used = dict()

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

    ncolor = 1

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

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
N = int(input())
d = defaultdict(list)
m = dict()
ls = []
for i in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)
    ls.append((a, b))

K = 0
for i in range(N):
    d[i+1].sort()
    K = max(K, len(d[i+1]))
print(K)

q = deque([])
q.append((1, 0))
visited = [0 for i in range(N+1)]
visited[1] = 1
while q:
    l, r = q.popleft()
    flag = 0
    cur = 1
    for i, x in enumerate(d[l], start=1):
        if visited[x] == 1:
            continue
        if flag == 0:
            if cur == r:
                q.append((x, cur+1))
                m[(l, x)] = cur+1
                m[(x, l)] = cur+1
                cur += 2
                visited[x] = 1
                flag = 1
                continue
            m[(l, x)] = cur
            m[(x, l)] = cur
            q.append((x, cur))
            cur += 1
            visited[x] = 1
        else:
            q.append((x, cur))
            m[(l, x)] = cur
            m[(x, l)] = cur
            cur += 1
            visited[x] = 1
for i in range(N-1):
    a, b = ls[i]
    print(m[(a, b)])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

N  = int(input())
Gb = [ [] for _ in range(N) ]
Gu = [ [] for _ in range(N) ]
Es = {}

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

    Es[f'{a:06}{b:06}'] = None

    Gb[a].append(b)
    Gb[b].append(a)
    Gu[a].append(b)

colors = list(range(max(map(len, Gb))))

def dfs(base_node, edge_color):
    global Es

    valid_colors = filter(lambda color: color != edge_color, colors)

    for child_node, color in zip(Gu[base_node], valid_colors):
        Es[f'{base_node:06}{child_node:06}'] = color + 1

        dfs(child_node, color)

print(len(colors))

dfs(0, None)

for color in Es.values():
    print(color)

Submission status: Accepted

Solution code:
"""2020/7/2再挑戦"""
#幅優先探索 親の頂点と色を覚えておく。親の色を除く＋1ずつ足していく。color_maxを超えたら余りをとる。
from collections import deque
N = int(input())
connection ={i:set() for i in range(1,N+1)}
connection_parent =[]
for i in range(1,N):
    a,b = (int(i) for i in input().split())
    connection[a].add(b)
    connection[b].add(a)
    connection_parent.append(b)

#最小の色数
c =[]
for i in connection.values():
    c.append(len(i))
color_min =max(c)

#幅優先探索
start =1
color={i:0 for i in range(1,N+1)} #P:今の頂点と次への辺の色を記録(tuple)。
passed =set() # 通過した記録
dq =deque([start]) #スタートは1でいいのか？
color[start] =0
while len(dq) >0:
    now =dq.popleft()
    passed.add(now)
    c1 =color[now]
    for next in connection[now]:
        if next not in passed:
            c1 +=1
            c1 %=color_min
            color[next] =c1  #0 <=c <= color_min-1のため　＋１
            dq.append(next)
print(color_min)
for i in connection_parent:
    print(color[i] +1)

Submission status: Accepted

Solution code:
import sys
 
n = int(input())
links = [set() for _ in range(n)]
for i, line in enumerate(sys.stdin):
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add((i, b))
    links[b].add((i, a))
 
ans = [-1] * (n - 1)
k = max(map(len, links))
q = [(0, -1)]
fixed = set()
 
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for i, u in links[v]:
        if ans[i] != -1:
            continue
        ans[i] = color
        q.append((u, color))
        color += 1
        if c == color:
            color += 1
 
print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

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

mx_color = 0    
for i in range(n):
    mx_color = max(mx_color,len(adj[i]))

dist = [-1]*n

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

q = deque([])
q.append([0,-1])
dist[0] = 0

while len(q) > 0:
    v,c = q.popleft()
    color = 1
    
    if color == c:
        color += 1
        
    for nv,nc in adj[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            q.append([nv,color])
            res[nc] = color
            color += 1
            if color == c:
                color += 1

print(mx_color)

for i in res:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def II(): return int(input())
def MI(): return map(int, input().split())
N=II()
edge=[[] for i in range(N)]
a=[0]*N
b=[0]*N
for i in range(N-1):
  a[i],b[i]=MI()
  a[i]-=1
  b[i]-=1
  edge[a[i]].append(b[i])
  edge[b[i]].append(a[i])
k=0
color_dict={}
def dfs(to,fm=-1,ban_color=-1):
  global k
  color=1
  for nxt in edge[to]:
    if nxt==fm:
      continue
    if color==ban_color:
      color+=1
    color_dict[(to,nxt)]=color
    dfs(nxt,to,color)
    color+=1
  k=max(k,color-1)
dfs(0)
print(k)
for i in range(N-1):
  print(color_dict[(a[i],b[i])])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
k = 0
data = [[] for _ in range(n)]
ans_index = []

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

q = deque([0])
color = [0] * n
while q:
    cur = q.popleft()
    c = 1
    for x in data[cur]:
        if c == color[cur]:
            c += 1
    
        color[x] = c
        c += 1
        q.append(x)

print(max(color))
for i in ans_index:
    print(color[i])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

dic = {i:[] for i in range(1,N+1)}

rlt = [0]*(N-1)

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

while h:
  j = 1
  c = 0
  t = h.popleft()
  for k in dic[t[0]]:
    if k[0] == t[1]:
      c = rlt[k[1]]
      break
  for k in dic[t[0]]:
    if k[0] == t[1]:
      continue
    if c == j:
      j += 1
    rlt[k[1]] = j
    h.append((k[0],t[0]))
    j += 1
    
print(max(rlt))  
for l in rlt:
  print(l)

Submission status: Accepted

Solution code:
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    V[a].append([b,i])
    V[b].append([a,i])
m = 0
for W in V:
    m = max(m, len(W))
from collections import deque
q = deque([])
reach = [-1]*(n+1)
q.append([1,0])
reach[1] = 0
color = [0]*(n-1)
while q:
    x,c = q.popleft()
    j = 1
    for W,i in V[x]:
        if c == j:
            j += 1
        if reach[W] == -1:
            reach[W] = 0
            q.append([W, j])
            color[i] = j
            j += 1
print(m)
for i in range(n-1):
    print(color[i])

Submission status: Accepted

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

from collections import deque
q=deque([1])
color=[0]*(n+1)
while q:
  cur=q.popleft()
  c=1
  for nx in G[cur]:
    if c==color[cur]:
      c+=1
    color[nx]=c
    c+=1
    q.append(nx)

print(max(color))
for i in G_order:
  print(color[i])

Submission status: Accepted

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

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

print(biggest)
for a, b in edges:
    print(colors[(a, b)])
# pypy3

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]

    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    queue = deque([0])
    parent = [-1] * N
    order = []

    while queue:
        v = queue.popleft()
        order.append(v)
        for nv in G[v]:
            if nv == parent[v]:
                continue
            parent[nv] = v
            queue.append(nv)

    color = [0] * N
    for v in order:
        c = 1
        for nv in G[v]:
            if nv == parent[v]:
                continue
            if c == color[v]:
                c += 1
            color[nv] = c
            c += 1

    ans = [0] * (N - 1)
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        if parent[a - 1] == b - 1:
            ans[i] = color[a - 1]
        else:
            ans[i] = color[b - 1]

    print(max(ans))
    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    queue = deque([0])
    color = [0] * (N - 1)
    color_from_parent = [0] * N
    color_from_parent[0] = -1

    while queue:
        v = queue.popleft()
        c = 1
        for i, nv in G[v]:
            if color_from_parent[nv] != 0:
                continue
            if c == color_from_parent[v]:
                c += 1
            color_from_parent[nv] = c
            color[i] = c
            c += 1
            queue.append(nv)

    print(max(color))
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    color = [0] * (N - 1)

    def dfs(v, p, pc):
        c = 1
        for i, nv in G[v]:
            if nv == p:
                continue
            if c == pc:
                c += 1
            color[i] = c
            dfs(nv, v, c)
            c += 1

    dfs(0, -1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    queue = deque([0])
    seen = [False] * N
    seen[0] = True
    color = [0] * (N - 1)
    color_parent = [-1] * N

    while queue:
        v = queue.popleft()
        c = 1
        for i, nv in G[v]:
            if seen[nv]:
                continue
            if c == color_parent[v]:
                c += 1
            color_parent[nv] = c
            color[i] = c
            queue.append(nv)
            seen[nv] = True
            c += 1

    print(max(color))
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import deque
        
n = int(input())
uf = UnionFind(n)
g = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * (n - 1)

for i in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    uf.union(a, b)
    g[a].append((b, i))
    g[b].append((a, i))
    cnt[a] += 1
    cnt[b] += 1
    

for i in uf.roots():
    visited = [0] * n
    visited[i] = 1
    que = deque()
    que.append([i, 0])
    while que:
        s = que.popleft()
        k = 0
        for j in g[s[0]]:
            if not visited[j[0]]:
                while True:
                    k += 1
                    if k != s[1]:
                        que.append([j[0], k])
                        visited[j[0]] = 1
                        ans[j[1]] = k
                        break

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [0] * (n - 1)

q = deque([[1, 0, -1]])

while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node:
            continue
        if cnt == pcol:
            cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1

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

Submission status: Accepted

Solution code:
import collections
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])
q = collections.deque()
q.append([0,-1,-1])
colors = [0]*(N-1)
while len(q) != 0:
    v, color, num = q.popleft()
    if colors[num] == 0 and color != -1:
        colors[num] = color
    next_color = 0
    for w in edges[v]:
        if colors[w[1]] != 0:
            continue
        next_color += 1
        if next_color == colors[num]:
            next_color += 1
        q.append([w[0],next_color,w[1]])
print(len(set(colors)))
for i in colors:
    print(i)

Submission status: Accepted

Solution code:
import collections
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])
# for i in edges:
#     print(i)
q = collections.deque()
q.append([0,-1,-1])
colors = [0]*(N-1)
check = [0]*N
while len(q) != 0:
    v, color, num = q.popleft()
    check[v] = 1
    # print(v,color,num)
    if colors[num] == 0 and color != -1:
        colors[num] = color
    next_color = 0
    for w in edges[v]:
        if check[w[0]] != 0:
            continue
        next_color += 1
        if next_color == colors[num]:
            next_color += 1
        q.append([w[0],next_color,w[1]])
# print(colors)
print(len(set(colors)))
for i in colors:
    print(i)