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
sys.setrecursionlimit(10**6)


N = int(input())

es = [[] for _ in range(N)]


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

# 辺の色
ans = [0] * (N-1)


def solve(now, prev_color):
    # 小さいものから
    color = 1
    for b,i in es[now]:
        # nowが繋がっている辺（nowとnowの親を繋ぐ辺）と同じ色なら＋１
        if color == prev_color:
            color += 1
        # i番目の辺に塗る
        ans[i] = color
        # bの子とつながる辺についてみていく
        solve(b, color)
        # 次のbで今のｂと色が被らないように＋１
        color += 1

# 
solve(0,0)



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

Submission status: Accepted

Solution code:
#%%
def dfs_deep_measure(st, n, reach, color):
    ans_list = [[0, 0, 0, 0, 0] for i in range(n)]
    # check, color, last_point, this_point
    stack = [st]
    ans_list[st][0] = 1
    ans_list[st][1] = -1
    ans_list[st][2] = -1
    ans_list[st][3] = st
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        c = ans_list[tmp][1]
        for i, j in tmp_list:
            if ans_list[i][0] != 1:
                stack.append(i)
                ans_list[i][0] = 1
                c += 1
                ans_list[i][1] = c % color
                ans_list[i][2] = tmp
                ans_list[i][3] = i
                ans_list[i][4] = j
    return ans_list


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

st = -1
color = -1
for i in range(n):
    if len(reach[i]) > color:
        color = len(reach[i])
        st = i

#print(st, n, reach, color)
#print(dfs_deep_measure(st, n, reach, color))

ans_list = dfs_deep_measure(st, n, reach, color)
ans_list.sort(key=lambda x: x[4])

#print(ans_list)
print(color)
for i in range(len(ans_list)):
    if ans_list[i][1] == -1:
        pass
    else:
        print(ans_list[i][1]+1)

Submission status: Accepted

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)



#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.edge=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.edge.append(edge)
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n = inp()
    g = [[] for _ in range(n)]
    color = [0 for _ in range(n)]
    did = [0 for _ in range(n)]
    dic = defaultdict(str)
    p = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        g[b].append(a)
        g[a].append(b)
        if a<b:
            a,b = b,a
        key = [str(a)]
        key.append(' ')
        key.append(str(b))
        key = ''.join(key)
        p.append(key)
        dic[key] = 1
    que = deque([])
    did[0]=1
    que.append(0)
    ans = 0
    while que:
        start = que.pop()
        go = g[start]
        c = 1
        for i in range(len(go)):
            t = go[i]
            if did[t]:
                continue
            else:
                if c == color[start]:
                    c += 1
                did[t] = 1
                que.append(t)
                color[t] = c
                ans = max(ans,c)
                key = []
                x = start
                y = t
                if x<y:
                    x,y = y,x
                key.append(str(x))
                key.append(' ')
                key.append(str(y))
                key = ''.join(key)
                dic[key] = c
                c += 1
    print(ans)
    for i in range(n-1):
        key = p[i]
        print(dic[key])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
#print("graph:", graph)

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

while stack:
  s = stack.pop()
  order.append(s)
  for g in graph[s]:
    if parent[s] == g:
      continue
    else:
      parent[g] = s
      stack.append(g)
#print("order:", order)
#print("parent:", parent)

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

for e in order:
  ng = color[e]
  c = 1
  for g in graph[e]:
    if parent[e] == g:
      continue
    if c == ng:
      c += 1
    color[g] = c
    c += 1
#print("color:", color)

print(max(color[2:]))
for a, b in AB:
  if parent[a] == b:
    print(color[a])
  else:
    print(color[b])

Submission status: Accepted

Solution code:
N = int(input())
d = {}
E = [[] for _ in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    d[(a-1,b-1)]=i
    d[(b-1,a-1)]=i
    
K = 0
ans = [None]*(N-1)

#queueに(node,par)を入れる．
q = [(0,-1)]

while q:
    node,p = q.pop()
    col = 1
    for to in E[node]:
        if to!=p:
            q.append((to,node))
            if p!=-1:
                if col==ans[d[(node,p)]]:
                    col+=1
            ans[d[(node,to)]]=col
            K=max(K,col)
            col+=1

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

Submission status: Accepted

Solution code:
#Edgeの組を拾う時に，辞書が良いかも？
import sys
input = sys.stdin.readline

N = int(input())
E=[[] for _ in range(N)]

index ={}

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

K=0
#ここに答えを入れていく，
ans=[None]*(N-1)

#dfs,root=-1
#Q=[(node,pare)]
Q=[(0,-1)]
while(Q):
    node,p=Q.pop()
    col=1
    #根の時
    if p==-1:
        for to in E[node]:
            #ansの適切な位置に色情報を入れる
            ans[index[(node,to)]]=col
            col +=1
            K=max(col,K)
            Q.append((to,node))
    #根ではない時
    else:
        for to in E[node]:
            if to==p:
                continue
            #親の色と同じなら1を足す．
            col+=(col==ans[index[(node,p)]]) 
            ans[index[(node,to)]]=col
            col+=1
            K=max(col,K)
            Q.append((to,node))

print(K-1)
print(*ans,sep="\n")

Submission status: Accepted

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

n = int(input())

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

    
ans = [0]*(n-1)

def col(now,color):
    c = 1
    for (b,j) in graph[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b,c)
        c += 1

col(0,0)
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

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

# input
n = int(input())

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

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == res[e][prev_edge]:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1,prev_color=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == prev_color:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e,cnt)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])

Submission status: Accepted

Solution code:
from collections import deque

tmp = {}
saigen = []
N = int(input())
tree = [[] for _ in range(N)]  # N頂点
for _ in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree[a].append(b)
    tmp[(a, b)] = -1
    saigen.append([a, b])
    # tree[b].append(a)

colors = [-1] * N

q = deque([0])

while len(q) != 0:
    v = q.popleft()  # 親のノードの番号
    color = 1
    for e in tree[v]:  # 子のノードの色を塗っていく
        if colors[e] != -1:
            continue
        if color == colors[v]:
            color += 1
        colors[e] = color
        tmp[v, e] = color
        color += 1
        q.append(e)
print(max(colors))
# 辺の順番を考慮する必要あり
# for c in colors[1:]:
#     print(c)
for a, b in saigen:
    print(tmp[a, b])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

print(max(colors))
for i in edge_order:
    print(colors[i])

Submission status: Accepted

Solution code:
N = int(input())

edges = [[] for i in range(N+1)]
el = []
ecol = {}

for i in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
    el.append("{},{}".format(a,b))

# BFS
queue = [[1,0]]
while(len(queue) != 0):
    #queueから取り出し
    p = queue.pop(0)
    p_el = edges[p[0]]
    c = 1
    for v in p_el:
        key1 = "{},{}".format(p[0],v)
        key2 = "{},{}".format(v,p[0])
        #まだ色がついていなければ
        if (not(key1 in ecol)) :
            # 色被りを考慮
            if (c == p[1]):
                c += 1
            ecol[key1] = c
            ecol[key2] = c
            queue.append([v,c])
            c += 1

print(max(ecol.values()))
for i in range(N-1):
    print(ecol[el[i]])

Submission status: Accepted

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque

n = int(input())
E = [[] for _ in range(n + 1)]
edge_order = []

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

# 頂点1からBFS
q = deque([1])
color = [0] * (n+1) 
while q:
    V = q.popleft()
    c = 1
    for nv in E[V]:
        if c == color[V]:
            c += 1
        color[nv] = c
        c += 1
        q.append(nv)

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

Submission status: Accepted

Solution code:
N = int(input())
edge = []
# bとして振られる番号
d_col = [0] * N
# b先に振り分ける番号
e_col = [1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    edge.append([a, b, i, 0])
edge = sorted(edge)
for j, e in enumerate(edge):
    a, b, i, ans = e
    if d_col[a-1] == e_col[a-1]:
        edge[j][3] = e_col[a-1] + 1
        e_col[a-1] += 1
    else:
        edge[j][3] = e_col[a-1]
    d_col[b-1] = e_col[a-1]
    e_col[a-1] += 1
edge = sorted(edge, key=lambda x: x[2])
col = []
for e in edge:
    col.append(e[3])
print(max(col))
for i in col:
    print(i)

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.buffer.readline

n = int(input())
v = [[] for _ in range(n+1)]
edge = [0] * -~n

ans = 0


def dfs(c,fa,x):
    global ans
    color = 1
    for to, eg in v[x]:
        if to == fa:
            continue
        if color == c:
            color += 1
        edge[eg] = color
        ans = max(ans, color)
        dfs(color, x, to)
        color += 1


def bfs(x):
    q = [[0,0,x]]
    ans = 0
    while len(q):
        c, fa, now = q.pop()
        color = 1
        for to, eg in v[now]:
            if to == fa:
                continue
            if color == c:
                color += 1
            edge[eg] = color
            q.append([color, now, to])
            ans = max(ans, color)
            color += 1
    return ans


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

print(bfs(1))
for i in range(n-1):
    print(edge[i])

Submission status: Accepted

Solution code:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append((b,i+1))
    dst[b].append((a,i+1))

narcs = [len(x) for x in dst]
mx = max(narcs)
for i in range(n):
    if narcs[i]==mx:
        mxi = i
        break

color = [-1]*n
color[dst[mxi][0][1]] = 0
q = [mxi, dst[mxi][0][0]]
while len(q)>0:
    p = q.pop()
    for i in range(len(dst[p])):
        arc = dst[p][i][1]
        if color[arc] != -1:
            c = color[arc]
            arc0 = arc
            break
    for i in range(len(dst[p])):
        arc = dst[p][i][1]
        if arc==arc0:
            continue
        nd = dst[p][i][0]
        c = (c+1)%mx
        color[arc] = c
        q.append(nd)

print(mx)
for i in range(1,n):
    print(color[i]+1)

Submission status: Accepted

Solution code:
import math
import collections
import numpy as np


class Edge:
    def __init__(self, dst, color):
        self.dst = dst
        self.color = color

    def __repr__(self):
        return str(self.dst) + ' ' + str(self.color)


def main():
    N = int(input())
    adj_list = [[] for _ in range(N+1)]
    edge_order = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        edge_order.append((a, len(adj_list[a])))
        adj_list[a].append(Edge(b, None))
        adj_list[b].append(Edge(a, None))

    max_deg = 0
    for i in range(1, N+1):
        max_deg = max(max_deg, len(adj_list[i]))
    K = max_deg
    print(K)

    queue = collections.deque()
    queue.append((1, None))
    while queue:
        cur_node, used_color = queue.popleft()
        # print(' ')
        # print('cur_node: ', cur_node)
        # print('used_color: ', used_color)
        # print('adj_list: ', adj_list)

        # color is [0, K-1]
        if used_color is None:
            color = 0
        else:
            color = (used_color + 1) % K
        for edge in adj_list[cur_node]:
            if edge.color is not None:
                pass
            else:
                edge.color = color
                for inv_edge in adj_list[edge.dst]:
                    if inv_edge.dst == cur_node:
                        inv_edge.color = color
                adj_list[edge.dst]
                queue.append((edge.dst, color))
                color = (color + 1) % K
        # print('queue: ', queue)

    for i, j in edge_order:
        print(adj_list[i][j].color + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    G = [[] for i in range(N)]
    ans = [None] * (N-1)
    
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        
        G[a].append((b, i))
        G[b].append((a, i))
        
    q = [(0, -1)]
    
    visited = [False] * N
    cur = 0
    
    while q and cur < N:
        v, c = q.pop(0)
    
        if visited[v]: continue
        visited[v] = True
        cur += 1
        
        k = 0
        for u, idx in G[v]:
            if visited[u]: continue
            if c == k: k += 1
            
            ans[idx] = k
            q.append((u, k))
            k += 1
            
    print(max(ans)+1)
    for a in ans: print(a+1)
     
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

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
        idx[(b,a)]=i

    k=max(len(E[i]) for i in range(n))
    # dfs
    ans=[None]*(n-1)
    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        # 根のとき -> 辺を張る
        if(p==-1):
            col=1
            for nv in E[v]:
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))
        # そうでないとき -> 親の色は除外
        else:
            col=1
            for nv in E[v]:
                if(nv==p): continue
                col+=(col==ans[idx[(v,p)]]) # 親の色になってしまったら足す
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))

    print(k)
    print(*ans,sep='\n')
resolve()

Submission status: Accepted

Solution code:
#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

Submission status: Accepted

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

class Node:
    nodes = {}
    max_c = 0
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[1]
        for _ in range(1000000):
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = deque(start_node.childs)
        list_to_visit.append(-1)
        ap = list_to_visit.append

        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.popleft()
                continue
            node = list_to_visit[0]
            list_to_visit.popleft()
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            if c > Node.max_c:
                Node.max_c = c
            list_to_visit += deque(node.childs)
            ap(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        #return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"
        return str(self.id)

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
ap = Edges.append
for i in range(N-1):
    edge = list(map(int, input().split()))
    ap(edge)
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()

Node.color_childs(root)
#Node.dump_all_nodes()
K = Node.max_c
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    e = [[] for _ in range(n + 1)]
    q = deque([1])
    c = [0] * (n + 1)
    for a, b in zip(*[iter(ab)] * 2):
        e[a].append(b)
    while q:
        s = q.popleft()
        d = 0
        for t in e[s]:
            d += 1 + (d + 1 == c[s])
            c[t] = d
            q.append(t)
    return str("{}\n{}".format(max(c), "\n".join(str(c[b]) for _, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

K = D[argmax]
Q = deque([])
C = dict()
for i, v in enumerate(V[argmax]):
    C[tuple(sorted([argmax, v]))] = i+1
    Q.append((v, i+1))

check = [0]*N
check[argmax] = 1
while Q:
    v, color = Q.popleft()
    check[v] = 1
    i = 0
    for u in V[v]:
        if check[u]:
            continue
        i += 1
        if i == color:
            i += 1
        C[tuple(sorted([u, v]))] = i
        Q.append((u, i))

print(K)
for i in range(N-1):
    print(C[T[i]])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()
# template

class edge:
    def __init__(self, src, to, info):
        self.src = src
        self.to = to
        self.info = info
        return

def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append(edge(a - 1, b - 1, i))
        g[b - 1].append(edge(a - 1, b - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e.info] != -1:
                continue
            idx += 1
            ans[e.info] = idx
            q.append((e.to, idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()