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**8)

def dfs(v,c):
  now = 1
  for u,i in edge[v]:
    if color[i]==0:
      if now==c:
        now += 1
      color[i] = now 
      dfs(u,now)
      now += 1
  return 0

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append([b-1,i])
  edge[b-1].append([a-1,i])
color = [0]*(N-1)
dfs(0,1<<30)
print(max(color))
print(*color, sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
A = []
g  =[[] for _ in range(n+1)]
ans = {}
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    A.append([a,b])


from collections import deque

q = deque()
q.append(1)

color = [-1]*(n+1)
color[1] = 0
cnt = 0

while q:
    v = q.popleft()
    p = 1
    for u in g[v]:
        if p==color[v]:
            p += 1
        color[u] = p
        ans[v,u] = p
        q.append(u)
        cnt = max(cnt,p)
        p += 1
print(cnt)

for i in range(n-1):
    tmp = (A[i][0],A[i][1])
    print(ans[tmp])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = -1, pre_c = -1):
        color = 1
        for b in G[a]:
            if b == pre: continue
            if color == pre_c: color += 1
            ans[ID[a][b]] = color
            bfs(b, a, color)
            color += 1

    bfs(0)
    print(m)
    [print(a) for a in ans]
      
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
k=0
used=[-1]*n
seen=[-1]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
    k=max(k,len(node[pair[0]]),len(node[pair[1]]))
print(k)
ans={}
d=deque()
d.append(0)
while d:
    i=d.pop()
    seen[i]=1
    res=1
    for j in node[i]:
        if seen[j]==1:
            continue
        d.appendleft(j)
        if res!=used[i]:
            ans[(i,j)]=res
        else:
            res+=1
            ans[(i,j)]=res
        used[j]=res
        res+=1
for pair in v:
    a,b=pair
    if (a,b) in ans:
        print(ans[(a,b)])
    else:
        print(ans[(b,a)])

Submission status: Accepted

Solution code:
n=int(input())
kotaezyun=[]
renketu=[[] for i in range(n+1)]
ans_dict={}
for i in range(n-1):
    a,b=map(int, input().split())
    renketu[a].append(b)
    kotaezyun.append([a,b])

from collections import deque
que=deque()

que.append(1)

iro=[-1]*(n+1)
iro[1]=0
irokazu=0

tansaku_moto=[1]

while que:
    tansaku_moto=que.popleft()
    ironuri=1
    for tansaku_saki in renketu[tansaku_moto]:
        if ironuri==iro[tansaku_moto]:
            ironuri+=1
        iro[tansaku_saki]=ironuri
        ans_dict[tansaku_moto,tansaku_saki]=ironuri
        que.append(tansaku_saki)
        irokazu=max(irokazu,ironuri)
        ironuri+=1
        
print(irokazu)
for i in range(n-1):
    tmp=(kotaezyun[i][0],kotaezyun[i][1])
    print(ans_dict[tmp])

Submission status: Accepted

Solution code:

from collections import deque
def resolve():
    N = int(input())
    G = [[] for _ in range(N)]
    nextV = []

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

    q = deque()
    q.append(0)
    color = [0] * N
    while q:
        v = q.popleft()
        parentC = color[v]
        c = 1
        for to in G[v]:
            if c == parentC:  # 親と同じ色だったら次の色を使用
                c += 1
            color[to] = c
            c += 1
            q.append(to)

    print(max(color))
    for b in nextV:
        print(color[b])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
"""
ABC146D Diff: 1175
"""
# BFSで各親の子供をループして調べていく.
# 各ノードの周りにある色を集合で持ったらTLE
# -> 色を塗る規則に注意すれば各親に対してintを1つ用意すれば十分

from collections import deque
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    #訪れたかどうか
    visited = [0]*N
    queue = deque()
    K = -1
    # 各ノードで使っている色の中で最大の色
    node2color = [-1 for _ in range(N)]
    queue.append(v)
    visited[v] = 1
    while queue:
        q = queue.popleft()
        # 使う色(int)を初期化: 0から++していくことで、
        # 調べる親qの子に対してできるだけ小さい色を塗れる。
        color = 0
        for nex in G[q]:
            if visited[nex]:
                #すでに訪れていたらcontinue
                continue
            visited[nex] = 1
            color += 1
            if color == node2color[q]:
                color += 1
            
            node2color[nex] = color
            # 辞書に記録
            E[(min(q, nex), max(q, nex))] = color
            queue.append(nex)
        K = max(K, color)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() # (a, b) -> color
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
        E[(a, b)] = 0 #辺->色の辞書
    K = bfs(0, N, G, E)
    # ans_list = [value for value in E.values()]
    print(K)
    for value in E.values():
        print(value)
main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    visited = [0]*N
    queue = deque()
    K = -1
    node2color = [-1 for _ in range(N)]
    queue.append(v)
    visited[v] = 1
    while queue:
        q = queue.popleft()
        color = 0
        for nex in G[q]:
            if visited[nex]:
                continue
            visited[nex] = 1
            color += 1
            if color == node2color[q]:
                color += 1
            
            node2color[nex] = color
            E[(min(q, nex), max(q, nex))] = color
            queue.append(nex)
        K = max(K, color)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() # (a, b) -> [idx, color]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
        E[(a, b)] = 0
    K = bfs(0, N, G, E)
    # ans_list = [value for value in E.values()]
    print(K)
    for value in E.values():
        print(value)
main()

Submission status: Accepted

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

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

ans = [None] * (N-1)

def dfs(v,p=-1,c=-1):
    nc = 1
    for to,e in es[v]:
        if to==p: continue
        if nc==c: nc += 1
        ans[e] = nc
        dfs(to,v,nc)
        nc += 1
dfs(0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    n = int(input().strip())
    edges = [[int(i) for i in input().strip().split()] for _ in range(n - 1)]
    g = defaultdict(list)
    for a, b in edges:
        g[a].append(b)

    # 1をルートとする
    que = deque([1])
    # 各頂点と親を結ぶ色を保存する
    # 1はルートのため 0 とする
    colors = [0] * (n + 1)

    # BFSで各ノードごとの子の色を決定する
    while que:
        parent = que.popleft()
        color = 0
        for child in g[parent]:
            color += 1
            if color == colors[parent]:
                color += 1
            colors[child] = color
            que.append(child)

    print(max(colors))

    for a, b in edges:
        print(colors[b])
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
G = [[] for _ in range(N + 1)]
# 辺の色を具体的に出力する際、辺の順番が必要になるので記録しておく
edge_order = []
for i in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge_order.append((a, b))

# どこでも良いが、ここでは1をrootとする
dq = deque([1])

# 辺の色
edge_color = {}
# 子要素を見ていく際、親が既に使った１色だけは使えない、そのチェック
used_color = [0 for _ in range(N + 1)]
# BFSで既に見たかどうか
visited = [False for _ in range(N + 1)]
visited[1] = True

# BFS
while dq:
    # prt = 親
    prt = dq.popleft()
    color = 0

    # cld = 子
    for cld in G[prt]:
        if visited[cld] == False:
            # 訪れたことを記録
            visited[cld] = True
            # 色を決める
            color += 1
            # 親が既に使った色だったらスキップ
            if color == used_color[prt]:
                color += 1

            # この段階で色は確定している

            # 「既に使った色」として記録
            used_color[cld] = color
            # 辺の色を記録
            n1 = min(cld, prt)
            n2 = max(cld, prt)
            edge_color[(n1, n2)] = color
            # キューに追加
            dq.append(cld)

# 使用する色の数
print(max(edge_color.values()))
# 具体的な辺の色を出力
for edge in edge_order:
    print(edge_color[edge])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
# 有向グラフと見る、G[親] = [子1, 子2, ...]
G = [[] for _ in range(N + 1)]
# 子ノードを記録、これで辺の番号を管理
G_order = []
# a<bが保証されている、aを親、bを子とする
for i in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append(b)
    G_order.append(b)

# どこでも良いが、ここでは0をrootとする
que = deque([0])

# 各頂点と「親」を結ぶ辺の色
# 頂点0をrootとするのでC[0]=0で確定(「無色」), 他を調べる
colors = [0] * N
# BFS
while que:
    # prt = 親
    # 幅優先探索
    prt = que.popleft()
    color = 0

    # cld = 子
    for cld in G[prt]:
        color += 1
        # 「今考えている頂点とその親を結ぶ辺の色」と同じ色は使えないので次の色にする
        if color == colors[prt]:
            color += 1
        colors[cld] = color
        que.append(cld)

# それぞれの頂点とその親を結ぶ辺の色
# print(colors)

# 必要な最小の色数
print(max(colors))

# 辺の番号順に色を出力
for i in G_order:
    print(colors[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
tree = [[] for _ in range(n)]
color = dict()
edge = [(0, 0)] * (n-1)
for i in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    edge[i] = (a, b)
color_n = max(map(len, tree))

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

visited = set()
while q:
    i, prev_c = q.popleft()
    visited.add(i)
    c = prev_c
    for x in tree[i]:
        if not x in visited:
            c = (c + 1) % color_n
            p = (i, x) if i < x else (x, i)
            color[p] = c
            q.append((x, c))
print(color_n)
for e in edge:
    print(color[e] + 1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
tree = [[] for _ in range(n)]
color = dict()
edge = [(0, 0)] * (n-1)
for i in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    edge[i] = (a, b)
color_n = max(map(len, tree))

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

visited = set()
while q:
    i, prev_c = q.popleft()
    visited.add(i)
    c = 0
    for x in tree[i]:
        if not x in visited:
            if c == prev_c:
                c = (c + 1) % color_n
            p = (i, x) if i < x else (x, i)
            color[p] = c
            q.append((x, c))
            c = (c + 1) % color_n

print(color_n)
for e in edge:
    print(color[e] + 1)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    n = INT()
    Q = [tuple(MAP1()) for _ in range(n-1)]

    deg = [0]*n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1:
            nouse = color[(min(s,p),max(s,p))]
        c = 1
        for t in adj[s]:
            if t == p:
                continue
            if c == nouse:
                c += 1
            color[(min(s,t),max(s,t))] = c
            dfs(t,s)
            c += 1
    
    dfs(1,-1)
    
    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edges_ls = [[0,0] for _ in range(n-1)]
edges_d = {}
ver_ls = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges_d[(a,b)] = i
    edges_d[(b,a)] = i
    edges_ls[i] = [a,b]
    ver_ls[a].append(b)
    ver_ls[b].append(a)
n_color = 0
for ver in ver_ls:
    n_color = max(n_color,len(ver))
def next_color(color):
    return (color+1)%n_color

edge_color = [0] * (n-1)
q = deque()
color_now = 0
for ver in ver_ls[0]:
    q.append([0,ver,color_now])
    edge_color[edges_d[(0,ver)]] = color_now
    color_now = next_color(color_now)
done_ls = [0] * n
done_ls[0] = 1

while q:
    From, to, color_now = q.popleft()
    # verはtoからの行先
    for ver in ver_ls[to]:
        if not done_ls[ver]:
            q.append([to,ver,next_color(color_now)])
            edge_color[edges_d[(to,ver)]] = next_color(color_now)
            color_now = next_color(color_now)
    done_ls[to] = 1

print(n_color)
for color in edge_color:
    print(color+1)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]
ab = [[i] + LI() for i in range(n-1)]
cnt = [0] * n
for i, a, b in ab:
    edges[a-1].append((i, b-1))
    edges[b-1].append((i, a-1))
    cnt[a-1] += 1
    cnt[b-1] += 1

k = max(cnt)
print(k)
que = deque([(0, -1, 0)])
edges_color = [None] * (n-1)
while que:
    v, p, col = que.popleft()
    cnt = 1
    for i, u in edges[v]:
        if edges_color[i] != None:
            continue
        if u == p:
            continue
        if cnt != col:
            edges_color[i] = cnt
        else:
            edges_color[i] = cnt + 1
            cnt += 1
        que.append((u, v, cnt))
        cnt += 1
for c in edges_color:
    print(c)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n=int(input())
edge=[[] for i in range(n+1)]
par=[0]*(n+1)#i番目の頂点とその親を結ぶ辺の色
par[1]=-1
col=[0]*(n-1)#i番目の辺の色
for i in range(n-1):
    a,b=mp()
    edge[a].append([a,b,i])
    edge[b].append([b,a,i])


que=deque([edge[1]])
while len(que):
    k=1
    q=que.popleft()
    for x,y,i in q:
        if col[i]==0:
            if k==par[x]:
                k+=1
            col[i]=k
            par[y]=k
            k+=1
            que.append(edge[y])
print(max(col))
for i in range(n-1):
    print(col[i])

Submission status: Accepted

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

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

Col = 0
for n in range(N):
    Col = max(Col, len(graph[n]))

Color = dict()
checked = [-1]*N
q = [0]
checked[0] = Col+1
while q:
    qq = []
    for p in q:
        c = checked[p]
        t = 0
        for np in graph[p]:
            if checked[np] == -1:
                if t == c:
                    t += 1
                checked[np] = t
                Color[(p, np)] = t
                Color[(np, p)] = t
                t += 1
                qq.append(np)
    q = qq

print(Col)
for a, b in Edges:
    print(Color[(a, b)]+1)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
g=[[] for i in range(n)]
b=[0]*(n-1)
for i in range(n-1):
    ai,bi=map(int,input().split())
    g[ai-1].append(bi-1)
    g[bi-1].append(ai-1)
    b[i]=bi-1
    
#n=8
#g=[[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
#b=[1, 2, 3, 4, 6, 5, 7]
#n=6
#g=[[1, 2, 3, 4, 5], [0], [0], [0], [0], [0]]

q=deque([0])

stack=[0]
parent=[-1]*n
pc=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
    ic=0
    for v in g[state]:
        if parent[v] !=-1:
            continue
        else:
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            ic+=1
            if ic==pc[state]:
                ic+=1
            pc[v]=ic

k=max(pc)
print(k)
for i in range(n-1):
    print(pc[b[i]])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    ans = [0]*(n-1)
    for i in range(n-1):
        u, v = mi()
        u -= 1
        v -= 1
        edge[u].append((v, i))
        edge[v].append((u, i))
    k = 0
    q = deque([0])
    visited = [False]*n
    visited[0] = True
    c = [0]*n
    while q:
        v = q.popleft()
        cur = 1
        k = max(k, len(edge[v]))
        for nv, idx in edge[v]:
            if visited[nv]:
                continue
            if cur == c[v]:
                cur += 1
            visited[nv] = True
            c[nv] = cur
            ans[idx] = cur
            cur += 1
            q.append(nv)
    print(k)
    print(*ans, sep='\n')





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
a = []
for i in range(N - 1):
    in1, in2 = map(int, input().split())
    a.append([in1, in2, i])
a = sorted(a, key = lambda x: x[0])
for i in range(N - 1):
    edges[i] = [a[i][0] - 1, a[i][1] - 1, a[i][2]]
    deg[a[i][0] - 1] += 1
    deg[a[i][1] - 1] += 1
deg_max = max(deg)
print(deg_max)

co = [0 for _ in range(N)]
ans = [0 for _ in range(N - 1)]
for i in range(N - 1):
    a = edges[i][0]
    b = edges[i][1]
    temp = 1 + (co[a] % deg_max)
    co[a] = temp
    co[b] = temp
    ans[edges[i][2]] = temp
for i in range(N - 1):  print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
n = int(input())
ab = [list(map(int,input().split()))for _ in range(n-1)]

graph = [[] for _ in range(n+1)]
ans = [0]*(n-1)
for i in range(n-1):
    graph[ab[i][0]].append((ab[i][1],i))
    graph[ab[i][1]].append((ab[i][0],i))

visit = [False]*(n+1)
def dfs(p,c):
    color = 1
    visit[p] = True
    for n,i in graph[p]:
        if visit[n] == False:
            if color == c:
                color += 1
            ans[i] = color
            dfs(n,color)
            color += 1

dfs(1,0)
print(max(ans))
for t in ans:
    print(t)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for i in range(1,n):
  a,b=map(int,input().split())
  tree[a].append([b,i])
  tree[b].append([a,i])
queue=deque([[1,0]])
ans=[0]*(n+1)
ans[1]=1
visited=[0]*(n+1)

while queue:
  v,c=queue.popleft()
  color=1
  for nv,i in tree[v]:
    if c==color:
      color+=1
    if visited[i]==1:
      continue
    visited[i]=1
    queue.append([nv,color])
    ans[i]=color
    color+=1
print(max(ans))
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

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

n = int(input())
edge = [[] for _ in [0]*n]
for i in range(~-n):
    a, b = map(int, input().split())
    a -= 1;b -= 1
    edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
    count = 1
    for to, i in edge[now]:
        # 親の色と同じとき
        if count == color:
            count += 1
        ans[i] = count
        dfs(to, count)
        count += 1

# 開始根は0番目に
dfs(0, 0)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
N = int(input())
E = [tuple(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for _ in range(N - 1)]
G = [[] for _ in range(N)]
for a, b in E:
    G[a].append(b)

colornum = len(G[0])
colors = [{} for _ in range(N)]
todo = deque()
for i, p in enumerate(G[0]):
    colors[0][p] = i
    todo.append((0, p))

while todo:
    pp, p = todo.popleft()
    colornum = max(colornum, len(G[p]) + 1)
    c = colors[pp][p]
    for np in G[p]:
        c = (c + 1) % colornum
        colors[p][np] = c
        todo.append((p, np))

print(colornum)
for a, b in E:
    print(colors[a][b] + 1)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    G = [[] for _ in range(N)]
    E = []
    _E = set()
    for i in range(N-1):
        a,b=mi()
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        E.append((a-1,b-1))
        _E.add((a-1,b-1))
    
    leaf = 0
    for i in range(N):
        g = G[i]
        if len(g) == 1:
            leaf = i

    stack = deque([(leaf,1,None)])
    seen = set()
    path = {x:0 for x in E}
    K = 0

    def save(edge,color):
        if edge == None: return

        a,b = edge
        if (a,b) in _E:
            path[(a,b)] = color
        else:
            path[(b,a)] = color


    while stack:
        current,color,edge = stack.popleft()
        seen.add(current)
        save(edge,color)
        K = max(K,color)
        # print(current,color,edge)

        i = 1
        for next in G[current]:
            if next in seen: continue
            if color == i:
                i += 1
            
            stack.append((next,i,(current,next)))
            i += 1
    
    if N == 2:
        print(1)
        print(1)
        exit()


    print(K)
    for i in range(N-1):
        a,b = E[i]
        print(path[(a,b)],sep="")







if __name__ == "__main__":
    main()

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:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy


def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    n = getN()
    graph = [[] for i in range(n)]
    ji = [0 for i in range(n)]
    hen = [0 for i in range(n-1)]
    used = [dict() for i in range(n)]
    for i in range(n - 1):
        a, b = getZList()
        graph[a].append([b, i])
        graph[b].append([a, i])
        ji[a] += 1
        ji[b] += 1
    mji = max(ji)
    mid = ji.index(mji)
    # print(mid)
    d = deque()
    d.append(mid)
    while(d):
        # print(d, hen)
        # print(used)
        cur = d.pop()
        iro = 1
        for nc, np in graph[cur]:
            if hen[np] != 0:
                continue
            # print(iro)
            while True:
                if iro not in used[cur]:
                    hen[np] = iro
                    d.append(nc)
                    used[nc][iro] = 1
                    iro += 1
                    break
                iro += 1


    # jiq = [(ji[i], i) for i in range(n)]
    # jiq.sort(reverse=True)
    # for _, id in jiq:
    #     iro = 0
    #     for tg, he in graph[id]:
    #         # for iro in range(mji):
    #         if hen[he] != 0:
    #             continue
    #         while True:
    #             if iro not in used[id]:
    #                 hen[he] = iro+1
    #                 used[tg][iro] = 1
    #                 iro += 1
    #                 break
    #             iro += 1

    print(mji)
    print(*hen, sep="\n")



def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()