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
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

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

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
E = [[] for _ in range(N+1)]

for i in range(N-1):
  a, b = map(int, input().split())
  E[a].append((b, i))
  E[b].append((a, i))
  
K = max(len(e) for e in E)  # 使用する色の最大数
print(K)

ans = [-1]*(N-1)
def dfs(v=1, p=0, p_col=-1):
  col = 1
  for u, idx in E[v]:
    if u == p: continue # 親だったらスキップ
    if col == p_col: col += 1 # 親とつながっている辺の色は使わない
    ans[idx] = col
    dfs(u, v, col)
    col += 1
dfs()
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
# アイデア：（これまでどおり）BFS。
# まず頂点に色を塗り，次に，その頂点から出る辺に色を塗ってゆく。
# 頂点に塗られた色及び「その頂点から出る何本目の辺か」によって，その辺に塗る色を決定する。
# 頂点に入ってくるときには，その際に取った辺の色を頂点に塗る。

from collections import deque

N=int(input())
d={} # 辺の両端の頂点→辺の番号を辿れるようにしておく
out=[set() for v in range(N+1)];out[0]=None # 隣接リスト，頂点の番号も問題文どおり1-initial,1~N
for i in range(1,N): # 問題文どおり辺の番号は1-initial,1~N-1
    u,v=map(int,input().split())
    out[u].add(v);out[v].add(u)
    u,v=min(u,v),max(u,v);d[(u,v)]=i
K=max([len(out[v]) for v in range(1,N+1)])
    
vcol=[0 for v in range(N+1)];vcol[0]=None
ecol=[0 for e in range(N)];ecol[0]=None

vr=[False for v in range(N+1)];vr[0]=None

q=deque()
q.append(1);vr[1]=True
vcol[1]=1 # 頂点1を色1で塗る
while q:
    u=q.popleft() # 今いる頂点    
    i=1 # その頂点から塗り始める何本目の辺か(1-initial),1<=i<=K
    for v in out[u]:
        if not vr[v]:
            col=(vcol[u]+i-1)%K+1
            vcol[v]=ecol[d[(min(u,v),max(u,v))]]=col
            vr[v]=True
            q.append(v)
            i+=1

print(K)
for i in range(1,N):
    print(ecol[i])

Submission status: Accepted

Solution code:
def solve():
  from collections import deque
  from sys import stdin
  
  f_i = stdin
  N = int(f_i.readline())
  
  e_color = {}
  edge = []
  adj = [[] for i in range(N)]
  for i in range(N - 1):
    a, b = map(int, f_i.readline().split())
    a -= 1
    b -= 1
    e = frozenset((a, b))
    e_color[e] = None
    edge.append(e)
    adj[a].append(b)
    adj[b].append(a)
  
  color_to_parent = [0] * N # color of edge between a vertex and its parent
  q = deque([0])
  notVisited = [True] * N
  notVisited[0] = False
  
  # BFS
  while q:
    v = q.popleft()
    color = 1
    for child in adj[v]:
      if notVisited[child]:
        if color == color_to_parent[v]:
          color += 1
        color_to_parent[child] = color
        e_color[frozenset((v, child))] = color
        color += 1
        notVisited[child] = False
        q.append(child)
  
  print(len(max(adj, key=len)))
  g = (e_color[e] for e in edge)
  print('\n'.join(map(str, g)))

solve()

Submission status: Accepted

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    # {node: {target: chain_index}}
    node_relation = {i: {} for i in range(NODE_N)}
    # {index: color}
    chain_color = {i: None for i in range(CHAIN_N)}
    # {node : set(color)}
    node_has_color = {i: set() for i in range(NODE_N)}
    passed = set()

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1
        node_relation[node][target] = i
        node_relation[target][node] = i

    bfs_queue = collections.deque([0])

    max_branch = 0
    while len(bfs_queue) > 0:
        node = bfs_queue.pop()
        leafs = node_relation[node]
        if max_branch < len(leafs):
            max_branch = len(leafs)

        color = 1
        for leaf, index in leafs.items():
            if leaf in passed:
                continue
            # search color
            # while color in node_has_color[node] or color in node_has_color[leaf]:
            while color in node_has_color[node]:
                color += 1
            node_has_color[node].add(color)
            node_has_color[leaf].add(color)
            chain_color[index] = color

            bfs_queue.appendleft(leaf)
            passed.add(node)

    ret = [max_branch]
    for i in range(CHAIN_N):
        ret.append(chain_color[i])
    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col
#                show(i,c,col)
                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Accepted

Solution code:
from collections import deque

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

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]


stack = [(0, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev = stack.pop()
    color = 0
    # 自分の子ノードを順番に塗り進めていく
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, u))
        color += 1
        a, b = min(u, prev), max(u, prev)
        # 親-自分間で使用済の色だったら1つ進める
        if a != -1 and color == edges[(a, b)][1]:
            color += 1
        a, b = min(u, v), max(u, v)
        edges[(a, b)][1] = color
        i = edges[(a, b)][0]
        ans[i] = str(color)
    # 各ノードから使った色数の最大を取る
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
num = [[]for _ in range(N)]
for i in (range(N-1)):
  a, b = map(int, input().split())
  num[a-1].append([i, b-1])
answer = [0] * (N-1)
color = [-1] * (N)
max_num = 0
for i in range(len(num)):
  if max_num <= len(num[i]):
    if i == 0:
      max_num = len(num[i])
    else:
      max_num = len(num[i]) + 1
  c = 1
  for j in range(len(num[i])):
    if c == color[i]:
      c += 1
    answer[num[i][j][0]] = c
    color[num[i][j][1]] = c
    c += 1
print(max_num)
for i in answer:
  print(i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append([i, b - 1])
    t[b - 1].append([i, a - 1])
    e.append([a - 1, b - 1])
colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

res = [0 for _ in range(n - 1)]
f = [False for _ in range(n)]


def dfs2(d, c):
    f[d] = True
    nc = 1
    for g in t[d]:
        if not f[g[1]]:
            if c == nc:
                nc += 1
            res[g[0]] = nc
            dfs2(g[1], nc)
            nc += 1

dfs2(0, res1+10)

print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append([i, b - 1])
    t[b - 1].append([i, a - 1])
    e.append([a - 1, b - 1])
colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

res = [0 for _ in range(n - 1)]
f = [False for _ in range(n)]


def dfs2(d, c):
    f[d] = True
    nc = 1
    for j in range(len(t[d])):
        if not f[t[d][j][1]]:
            if c == nc:
                nc += 1
            res[t[d][j][0]] = nc
            dfs2(t[d][j][1], nc)
            nc += 1


dfs2(0, 1000000)

print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
#入力
n=int(input())
ab=[]
#頂点1,3,4が直接つながっている時G[1]=[3,4],G[3]=[1,4],G[4]=[1,3]となるグラフ表現
G=[[] for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

#親から伸びた枝の色を保存するリスト
#p[3]=2ならばノード3の親とノード3をつなぐ枝の色は2
p=[-1 for i in range(n+1)]
#枝の色を保存するディクショナリ
#edge{"2,5":3}ならばノード２とノード５をつなぐ枝の色は３
edge={}
#ノードが探索済みか否かを判別するリスト
#used[6]=1ならばノード６は探索済み
used=[0 for i in range(n+1)]

#一つのノードから伸びる枝の数の最大値
max_n=0
for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        #枝が最も多いノードを根とする
        top=i

#キューに根を追加
queue=[]
queue.append(top)

#幅優先探索
while len(queue)>0:
    #キューからノードを取り出して、探索済みにする
    num=queue.pop(0)
    used[num]=1
    color=1
    
    #現在のノードから伸びている枝の数だけ探索
    for i in range(len(G[num])):
        #探索するノードが未探索かの判定
        if used[G[num][i]]==0:
            if p[num]==color:
                #いま塗ろうとしている色が親からの伸びる枝の色とかぶっていた場合
                #その色をスキップ
                color+=1
                #双方向から塗っておく
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                #子に伸びる色を保存
                p[G[num][i]]=color
                #キューに子を追加
                queue.append(G[num][i])
            else:
                #かぶっていない場合はそのまま塗る
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1
            
#色の数は一つのノードから伸びる枝の数の最大値に等しい
print(max_n)
#枝の色を表示
for i in range(n-1):
    print(edge["{},{}".format(ab[i][0],ab[i][1])])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
K=0
g=[[] for _ in range(n+1)]
for  i in range(n-1):
    a,b=map(int,input().split())
    g[a].append([b,i])
    g[b].append([a,i])
for i in range(n):
    K=max(len(g[i]),K)
print(K)
ans=[0]*(n-1)
q=deque([(-1,1)])
while q:
    s,p=q.popleft()
    C = (c for c in range(1, K + 1) if c != s)
    for i,j in g[p]:
        g[i].remove([p,j])       
        sa=next(C)
        ans[j]=sa
        q.append((sa,i) )
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

N = int(input().split()[0])

# ノードの情報
node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

a_list = []
b_list = []
edge_dict = {}
edge_list = []

# エッジの情報
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a

# ルートを探す
root = list(set(a_list) - set(b_list))[0]

max_color_degree = -float("inf")

# 最悪で10 ** 5
for k, v in node_dict.items():
    d = len(v["children"])
    # 親がいない場合は、親の数も含める
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_LIST = list(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color = parent_edge_color

    # 最悪で10 ** 5
    color_index = 0
    for child in next_node_list:
        color = COLOR_LIST[color_index]
        if color == ng_color:
            color_index += 1
            color = COLOR_LIST[color_index]

        edge_dict[(parent, child)]["color"] = color
        color_index += 1
    return


parent = root
next_node_list = node_dict[root]["children"]
next_next_node_list = []

# 最悪で10 ** 5
color_index = 0
for node in next_node_list:
    color = COLOR_LIST[color_index]
    color_index += 1
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = next_parent_list

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(max_color_degree)
print(color_list_str)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

N = int(input().split()[0])

# ノードの情報
node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

a_list = []
b_list = []
edge_dict = {}
edge_list = []

# エッジの情報
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a

# ルートを探す
root = list(set(a_list) - set(b_list))[0]

max_color_degree = -float("inf")

# 最悪で10 ** 5
for k, v in node_dict.items():
    d = len(v["children"])
    # 親がいない場合は、親の数も含める
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_LIST = list(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color = parent_edge_color

    # 最悪で10 ** 5
    color_index = 0
    for child in next_node_list:
        color = COLOR_LIST[color_index]
        if color == ng_color:
            color_index += 1
            color = COLOR_LIST[color_index]

        edge_dict[(parent, child)]["color"] = color
        color_index += 1
    return


parent = root
next_node_list = node_dict[root]["children"]
next_next_node_list = []

# 最悪で10 ** 5
color_index = 0
for node in next_node_list:
    color = COLOR_LIST[color_index]
    color_index += 1
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    # コピーはO(N)
    next_node_list = next_parent_list

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(max_color_degree)
print(color_list_str)

Submission status: Accepted

Solution code:
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.adj = []
        self.pec = 0

n = int(input())
ab = []
nodes = [None] * n
cntMap = {}

def addCount(v1):
    if v1 not in cntMap:
        cntMap[v1] = 1
    else:
        cntMap[v1] += 1

for i in range(n-1):
    v1, v2 = map(int, input().split())
    addCount(v1)
    addCount(v2)
    ab.append([v1, v2])
    nodeAidx = v1-1
    nodeBidx = v2-1
    nodeA = None
    nodeB = None
    if nodes[nodeAidx] is None:
        nodeA = Node(v1)
        nodes[nodeAidx] = nodeA
    else:
        nodeA = nodes[nodeAidx]
    if nodes[nodeBidx] is None:
        nodeB = Node(v2)
        nodes[nodeBidx] = nodeB
    else:
        nodeB = nodes[nodeBidx]
    nodeA.adj.append(nodeB)

#print(ab)
#print(nodes)
root = nodes[0]
nodes[1].pec = 1
q = deque()
q.append(root)

temp = list(cntMap.values())
temp.sort()
maxV = temp[-1]
used = set()
edgeMap = {}

print(maxV)

while q:
    used.clear()
    node = q.popleft()
    pec = node.pec
    used.add(pec)
    prev = 0

    for i in range(len(node.adj)):
        a = node.adj[i]
        for j in range(prev+1, maxV+1):
            if j not in used:
                a.pec = j
                used.add(j)
                prev = j
                break

        edgeMap[(node.val, a.val)] = a.pec
        q.append(a)

for i in range(n-1):
    key = (ab[i][0], ab[i][1])
    print(edgeMap[key])

Submission status: Accepted

Solution code:
from collections import deque
 
N, *AB = map(int, open(0).read().split())
 
E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))
K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u, i in E[v]:
        E[u].remove((v, i))
        c = next(C)
        Q.append((c, u))
        A[i] = c
 
print(K)
for a in A:
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n = int(input())

tree = defaultdict(list)

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

I = dict()
que = deque([1])
color = [None]*(n+1)
color[1] = 0
max_val = 0
used = {1, }
while que:
	u= que.popleft()
	max_val = max(max_val, len(tree[u]))
	next_color = 1
	for v in tree[u]:
		if v in used: continue
		if color[u] == next_color:
			next_color += 1
		color[v] = I[(u, v)] = I[(v, u)] = next_color
		next_color += 1
		que.append(v)
		used.add(v)
print(max_val)
for edge in edges:
	print(I[edge])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edge = [set() for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a].add((b, i))
  edge[b].add((a, i))

r = [0] * (N - 1)
q = deque([(0, 1)])

while q:
  preC, fromv = q.popleft()
  c = 0
  for tov, i in edge[fromv]:
    edge[tov].remove((fromv, i))
    c += 1 + (c + 1 == preC)
    q.append((c, tov))
    r[i] = c
print(max(r))
for x in r:
  print(x)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
import sys
sys.setrecursionlimit(20000000)
from collections import defaultdict
d=defaultdict(lambda:defaultdict(int))
l1=[[] for i in range(n+1)]
#d=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l1[a].append(b)
  l1[b].append(a)
  l.append([a,b])
max1=0
for i in l1:
  if max1<len(i):
    max1=len(i)
def dfs(x,y):#xは頂点yは入ってくる色
  l2=l1[x]
  now=1
  for i in range(len(l2)):
    if d[x][l2[i]]!=0:
      pass
    else:                
      if now==y:
        now+=1
      d[x][l2[i]]=now
      d[l2[i]][x]=now
      dfs(l2[i],now)
      now+=1
print(max1)
dfs(1,0)
for i in range(len(l)):
  print(d[l[i][0]][l[i][1]])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = [set() for _ in range(N)]
ABs = []
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1, b-1
    ABs.append((a,b))
    lines[a].add(b)
    lines[b].add(a)


K = -1
ki = -1
for i in range(N):
    if K < len(lines[i]):
        K = len(lines[i])
        ki = i



colors = [defaultdict(int) for _ in range(N)]

def dfs(s,bs,bk):
    cnt = 0
    for t in lines[s]:
        if t == bs:
            continue
        else:
            if cnt == bk:
                cnt += 1
            colors[s][t] = cnt
            colors[t][s] = cnt
            dfs(t,s,cnt)
            cnt += 1


for i,t in enumerate(lines[ki]):
    colors[ki][t] = i
    colors[t][ki] = i
    dfs(t,ki,i)

print(K)
for a,b in ABs:
    print(colors[a][b]+1)

Submission status: Accepted

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

N = int(input())

graph = [[] for i in range(N)]

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

def dfs(past,now,edge_col):
    new_col = 1
    for (future,i) in graph[now-1]:
        if future == past:
            pass
        else:
            if new_col == edge_col:
                new_col += 1
            ans[i] = new_col
            dfs(now,future,new_col)
            new_col += 1
            
dfs(-1,1,-1)

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

Submission status: Accepted

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

N = int(input())
edge = [[] for _ in range(N)]
v_dic = {}
b_l = []
for i in range(N-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge[a].append(b)
    if a not in v_dic:
        v_dic[a] = 1
    else:
        v_dic[a] += 1
    if b not in v_dic:
        v_dic[b] = 1
    else:
        v_dic[b] += 1
    b_l.append(b)
colors = [0 for _ in range(N)]


def bfs(p_node, p_color):
    children_node = edge[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1


def solve():
    bfs(0, 0)

    print(max(v_dic.values()))
    for b in b_l:
        print(colors[b])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

q = queue.Queue()
ans = [0]*(N-1)
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[idx[(n[0], nxt)]] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    ab = []
    for i in range(n-1):
        tma, tmb = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        ab.append([tma-1, tmb-1])

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0]
    ans = collections.defaultdict(int)
    ls = [1] * n
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    fq[tmv]
                    if ls[tmp] == cost:
                        ls[tmp] += 1
                    ql.append([ls[tmp], tmv])
                    ans[tmp, tmv] = ls[tmp]
                    ls[tmp] += 1
        else:
            break
    print(max(ans.values()))
    for a, b in ab:
        print(ans[a, b])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
#bfs_use_coler = [[ -1 for _ in range(N+1) ] for _ in range(N+1) ] 

def solve_bfs(previous_colors,n_list,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    next_colors = []
    next_n_list =[]
    for idx1,n in enumerate(n_list):
        use_color_num = 1
        for idx2,val in enumerate(tree[n]):
            if use_color_num == previous_colors[idx1]:
                use_color_num += 1
            already_make[val[1]] = use_color_num
            next_colors.append(use_color_num)
            next_n_list.append(val[0])
            last_color = max(use_color_num,last_color)
            use_color_num += 1
    if len(next_colors) > 0:
        return solve_bfs(next_colors,next_n_list,last_color)
    else:
        return last_color

last_color = solve_bfs([0],[1],last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)

Submission status: Accepted

Solution code:
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0,pu=-1,pc=-1):
        c=1
        for i,cu in to[u]:
            if cu==pu:continue
            if c==pc:c+=1
            ans[i]=c
            dfs(cu,u,c)
            c+=1

    to=defaultdict(list)
    n=int(input())
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append([i,b])
        to[b].append([i, a])
    ans=[-1]*(n-1)
    dfs()
    print(max(ans))
    print(*ans,sep="\n")

main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

que = deque([(1, -1)])
ans = [-1] * (N - 1)
while que:
    now, parent = que.popleft()

    canUse = set(range(1, len(edges[now]) + 1))
    for to, i in edges[now]:
        if to == parent and ans[i] in canUse:
            canUse.remove(ans[i])

    canUse = list(canUse)
    for to, i in edges[now]:
        if to == parent:
            continue
        color = canUse.pop()
        if ans[i] == -1:
            ans[i] = color
        que.append((to, now))

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

Submission status: Accepted

Solution code:
import sys


def bfs(p_node, p_color):
    global K
    children_node = graph[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1
    K = max(K, c_color - 1)


sys.setrecursionlimit(10**9)

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

colors = [-1] * (N + 1)
K = 0

bfs(1, -1)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

N = int(input())

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

colors = [-1] * (N + 1)
K = 0


def bfs(p_node, p_color):
    global K
    children_node = graph[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1
    K = max(K, c_color - 1)


bfs(1, -1)

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