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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))
#print(N,m,AB)
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    #print(a,b)
#print(graph)
root = 1
parent = [0] * (N+1)
order = []
stack = [root]
#print(stack)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
#print(order,parent) 
color = [-1] * (N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1
#print(color)
answer = []
append = answer.append
for a,b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
 
K = max(answer)
print(K)
print('\n'.join(map(str,answer)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    N = int(input())
    bl = []
    d = {i:0 for i in range(1,N+1)}
    d1 = {i:[] for i in range(1,N+1)}
    d2 = {}
    d3 = [0] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        d2[tuple(sorted([a,b]))] = i
        d[a] += 1
        d[b] += 1
        d1[a].append(b)
        d1[b].append(a)
    m = 0
    for i in d:
        m = max(m, d[i])
    dfs(1, d1, d2, d3, 0)
    print(m)
    for i in d3:
        print(i)

def dfs(n, d1, d2, d3, c):
    count = 1
    for i in d1[n]:
        if d3[d2[tuple(sorted([n,i]))]] > 0:
            continue
        if count == c:
            count += 1
        d3[d2[tuple(sorted([n,i]))]] = count
        dfs(i, d1, d2, d3, count)
        count += 1
main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

que = deque()
que.append([0, 0])

watch = [False] * n
watch[0] = True
color = [0] * (n-1)

while que:
    i, prev_color = que.popleft()
    watch[i] = True
    max_color = 1
    for next, index in g[i]:
        if watch[next]: continue
        watch[next] = True
        if max_color == prev_color:
            max_color += 1
        que.append([next, max_color])
        color[index] = max_color
        max_color += 1

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

Submission status: Accepted

Solution code:
from collections import deque
# dequeは両端へのアクセスが早い　O(1)

N = int(input())
#辺の集合を隣接リストとして入力
E = [[] for i in range(N+1)] #２次元配列 N個の箱を用意する 
edge_order = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b) #　頂点をindexとする箱
    edge_order.append(b) # 辺の数をカウント、idとしてそれらも確保
#print(E)

#頂点１から幅優先探索
queue = deque([1])
color = [0] * (N+1)
while queue:
    V = queue.popleft()
    c = 1
    for i in E[V]:
        if c == color[V]:
            c += 1
        color[i] = c
        c += 1
        queue.append(i)

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

Submission status: Accepted

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

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

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N = int(input())
    # 辺の集合を隣接リストとして入力
    E = [[] for i 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から幅優先探索
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N = int(input())
    # 辺の集合を隣接リストとして入力
    E = [[] for i 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から幅優先探索
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if i < V:
                continue
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import sys

UNDEF=-1
sys.setrecursionlimit(1000010)
N = int(input())
# print(N)
V=[[UNDEF,UNDEF,[],[] ] for _ in range(N) ]      # Vertex
E=[[] for _ in range(N-1) ]    # Edge 

for i in range(N-1):
    (xa,xb) = map(int,input().split())
    # print(xa,xb)
    E[i]=[xa,xb]
    V[xb-1][0]=xa
    V[xb-1][1]=i+1
    V[xa-1][2].append(xb)
    V[xa-1][3].append(i+1)


# print("Edge:", E)
# print("Vertex:",V)

def root_v():
    global UNDEF
    global V
    for i in range(len(V)):
        if V[i][0] == UNDEF:
            return i+1
    return UNDEF

# print("Root Node:",root_v())

def max_degree(s):
    if V[s-1][0] != UNDEF: 
        degree=len(V[s-1][2]) + 1 # Node S 's degree for non root
    else:
        degree=len(V[s-1][2])     # Node S 's degree for root 

    for c in V[s-1][2]:
        degree = max ( degree, max_degree(c) ) 
    return degree

# print("Max Degree:", max_degree(root_v()))
print(max_degree(root_v()))

# Initialize 'color list' for edges
color=[UNDEF for _ in range(N-1)]

def put_colors(s):
    # print("put_color",s)
    global color 
    pcolor=UNDEF
    if V[s-1][1] != UNDEF:
        pcolor = color[V[s-1][1]-1]
    ic = 1
    for i in range(len(V[s-1][3])):
        if ic == pcolor:
            ic = ic + 1
        # print("put_color",s,i,V[s-1][3][i], ic )
        color[V[s-1][3][i]-1] = ic 
        put_colors(V[s-1][2][i])
        ic = ic + 1
    
put_colors(root_v())
for i in range(N-1):
    print(color[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

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

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
sys.setrecursionlimit(n * 10)
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
visited[0] = True
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in tree[v]:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []
ans = []

class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id

def dfs(v, fr, frk):
    global ans
    k = 1
    for e in G[v]:
        if e.to != fr:
            if k == frk:
                k += 1
            ans[e.id] = k
            dfs(e.to, v, k)
            k += 1

def main():
    global G, ans
    n = int(input().strip())
    ans = [0] * (n-1)
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int, input().strip().split()))
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    dfs(0, -1, -1)
    maxk = 0
    for l in G:
        maxk = max(maxk, len(l))
    print(maxk)
    for p in ans:
        print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
l.sort()
flg = [0 for _ in range(n+1)]
ans = [0 for _ in range(n)]
#print(l)
t=0
count=0
for i in range(n-1):
    a,b,c=l[i]
    if t!=a:
        t=a
        count=1
    if flg[a]==count:
        count+=1
    flg[b]=count
    ans[c]=count
    count+=1
    #print(flg,ans)
print(max(flg))
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

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

N = int(input())

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

result = [0]*(N-1)
def search(par, ans, own, par_num):
    ans =  max(ans, len(ki[own]))
    i = 1
    for child in ki[own]:
        if child[0] == par:
            continue
        else:
            if i == par_num:
                i += 1
            result[child[1]] = i
            ans = max(search(own, ans, child[0], i),ans)
            i += 1
    return ans

print(search(-1, 0, 0, -1))
for i in result:
    print(i)

Submission status: Accepted

Solution code:

#%%
import sys
sys.setrecursionlimit(100000)

def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())

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

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

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



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

Submission status: Accepted

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

n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n-1)

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

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

dfs(0, -1, 0)
print(max(color))
print(*color, sep="\n")

Submission status: Accepted

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

N = int(input())

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

ans = [None]*(N-1)

# 引数：今回の基準頂点、前回の基準頂点と今回の頂点を結ぶ辺の色番号
def func(ver, color):
    # 色番号。まずは最低の番号から始める。もし今回と前回の基準頂点の色番号1の場合は後で色番号変更
    cnt = 1
    # for (基準頂点と繋がっている頂点, 辺の番号) in 基準頂点
    for (to, i) in G[ver]:
        # 既使用（前回の基準頂点と今回の頂点を結ぶ辺の色）と今回使う色番号が同じなら+1で色番号変更
        if cnt==color:
            cnt += 1
        # i番目の辺における色番号
        ans[i] = cnt
        # 今回の頂点と、今回の頂点と基準頂点の辺の色番号を入力し、今回の頂点を次の基準頂点にする
        func(to, cnt)
        # 今回の基準頂点と繋がる次の頂点の処理をするために色番号変更
        cnt += 1

func(0, 0)

print(max(ans))

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

Submission status: Accepted

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

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

ans = [None]*(n-1)
def rec(cur,color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100000)

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

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

Submission status: Accepted

Solution code:
#D
from collections import deque
#import bisect
#import math
#import heapq
#import sys
#input = sys.stdin.readline

#inf = float("inf")
#mod = 10**9 + 7
#mod = 998244353

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

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

K = [0]*N
for ab in AB:
    a,b,i = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)
AB.sort()
C = [0]*N
D = deque(AB)
flag = 0
visited = [-1]*N
ans = [0]*(N-1)
while D:
    a,b,i = D.popleft()
    if visited[a-1] == -1 and visited[b-1] == -1:
        if flag == 0:
            flag = 1
            visited[a-1] = 0
            visited[b-1] = 0
            ans[i] = 1
            C[a-1] = 1
            C[b-1] = 1
        else:
            D.append([a,b,i])
    else:
        if visited[b-1] == -1:
            if C[a-1] == k:
                ans[i] = 1
                C[a-1] = 1
                C[b-1] = 1
            else:
                ans[i] = C[a-1]+1
                C[a-1]+=1
                C[b-1] = C[a-1]
            visited[b-1] = 0
        else:
            visited[a-1] = 0
            if C[b-1] == k:
                ans[i] = 1
                C[a-1] = 1
                C[b-1] = 1
            else:
                ans[i] = C[b-1]+1
                C[b-1]+=1
                C[a-1] = C[b-1]
                
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]
ans = {}
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    ans[(a, b)] = 0
    tmp.append((a, b))  # 最後に出力する際に使う, 順番通りに出力する必要があるから。

# print(tree)
visited = [False]*N
colors = [-1]*N  # そのノードに上から刺さっている辺の色 (colors[根のノードのindex]は変わらない)
q = deque([0])  # 始まりのノード
visited[0] = True
while len(q):
    # vは数字, 親のノードのインデックス
    v = q.pop()
    color = 1

    for e in tree[v]:
        if visited[e]:  # 到達済みなら次のノードへ
            continue
        visited[e] = True
        if colors[v] == color:  # 親のノードに刺さっている辺の色が今から塗ろうとしている色と同じなら、変更する
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
G = [list() for _ in range(N)]

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

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)
dfs(0)

k = max(map(len, G))
print(k)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

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

K = max(len(e) for e in E)
print(K)

res = [-1 for _ in range(N-1)]
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dfs(child,v,col)
            col += 1
dfs()
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
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:
            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:
n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append([b, i+1])
    tree[b].append([a, i+1])

edge = [0] * n #ans
visit = [False] * (n+1) #vert
color = [set() for i in range(n+1)]
visit[1] = True
q = [1]
edge[1] = 1

while q:
    now = q.pop()
    c = 1
    for next, num in tree[now]:
        if not visit[next]:
            while c in color[now]:
                c += 1
            edge[num] = c
            color[next].add(c)
            visit[next] = True
            q.append(next)
            c += 1
    before = now

print(max(edge))
for i in range(1, n):
    print(edge[i])

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

for i in range(n-1):
    for j in range(2):
        A[i][j] -= 1

M = [[] for i in range(n)]
for i in range(n-1):
    M[A[i][0]].append([A[i][1], i])
    M[A[i][1]].append([A[i][0], i])
    
C = [-1] * n
s = 0
Q = [[0, 0]]
C[0] = 0
while len(Q) > s:
    i = Q[s][0]
    ic = Q[s][1]
    for j in range(len(M[i])):
        if C[M[i][j][0]] == -1:
            C[M[i][j][0]] = ic+1
            Q.append([M[i][j][0], ic+1])

    s += 1
# print(C)
D = []
for i in range(n):
    D.append([C[i], i])
D.sort()
ANS = [0] * (n-1)
NG = [0] * n
# print(D)
for i in range(n):
    c = 1
    v = D[i][1]
    for j in range(len(M[v])):
        if ANS[M[v][j][1]] == 0:
            if NG[v] == c:
                c += 1
            ANS[M[v][j][1]] = c
            NG[M[v][j][0]] = c
            c += 1
# print(ANS)

print(max(ANS))
for i in range(len(ANS)):
    print(ANS[i])

# print(max(C)+1-1)
# for i in range(n-1):
#     print(min(C[A[i][0]], C[A[i][1]]) + 1)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    ans = {}
    queue = deque([])
    e = []
    for l in range(N-1):
        temp = list(map(int,input().split()))
        temp[0] -= 1
        temp[1] -= 1
        e.append(tuple(temp))
        ans[(temp[0],temp[1])] = 0
        ans[(temp[1],temp[0])] = 0
        G[temp[0]].append(temp[1])
        G[temp[1]].append(temp[0])
        if l == 0:
            queue.append(temp[0])
    #使えない色
    nuc = [[0] for _ in range(N)]
    #使った色
    auc = []
    #答え
    def bfs(x):
        k = 1
        for i in G[x]:
            if ans[(x,i)] ==0:
                queue.append(i)
                flag = 1
                while flag:
                    if k not in nuc[x]:         
                        ans[(x,i)] = k
                        ans[(i,x)] = k
                        nuc[x].append(k)
                        nuc[i].append(k)
                        if k not in auc:
                            auc.append(k)
                        flag = 0
                    else:
                        k += 1
                    
    while len(queue) > 0:
        next_ = queue.popleft()
        bfs(next_)
    print(len(auc))
    for m in e:
        print(ans[m])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
G = [list() for _ in range(N)]

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

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)

dfs(0)
mx = 0

for i in range(N):
    mx = max(mx,len(G[i]))
print(mx)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
AB = []
for i in range(N-1):
    a,b = map(int,input().split())
    AB.append([a-1,b-1])
G = [list() for _ in range(N)]
for i in range(N-1):
    G[AB[i][1]].append([AB[i][0],i])
    G[AB[i][0]].append([AB[i][1],i])

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx,len(G[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:

n = int(input())
Ad = [[] for _ in range(n)]
Deg = [0]*n
E = {}
E2 =[]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1
    E[(ai,bi)]=-1
    E[(bi,ai)]=-1
    E2.append((ai,bi))
mx = max(Deg)
print(mx)
E[(0,0)] = -1#後の都合
P =[-1]*n#parent
from collections import deque
Q = deque()
Q.append(0)
P[0] = 0

while Q:
    v = Q.popleft()
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)

Q = deque()
cnt = 1
for v in Ad[0]:
    E[(0,v)]=cnt
    E[(v,0)]=cnt
    cnt+=1
    Q.append(v)

while Q:
    v = Q.popleft()
    cnt = 1
    for u in Ad[v]:
        if E[(u,v)]<0:
            if cnt==E[(v,P[v])]:
                cnt +=1
            E[(u,v)] = cnt
            E[(v,u)] = cnt
            cnt+=1
            Q.append(u)
for i in range(n-1):
    print(E[E2[i]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

Submission status: Accepted

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 0)])

while(len(queue)):
    q, c = queue.popleft()
    k = 0
    for v in edges[q]:
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        k += 1
        data[(a, b)] = c+k
        queue.append((v, c+k))
print(maxColor)
for i in range(N-1):
    print((data[inputData[i]]-1)%maxColor+1)

Submission status: Accepted

Solution code:
N = int(input())
AB =[]
V = [[] for _ in range(N)]
Edict = dict()
for _ in range(N-1):
    a,b = map(int,input().split())
    AB.append((a-1,b-1))
    V[a-1].append(b-1)
    V[b-1].append(a-1)
K = max(len(V[i]) for i in range(N))
for i in V:
    i.sort()
for i,v in enumerate(V[0]):
    Edict[(0,v)] = i
for i in range(1,N): # 2(N-1)
    color = 0
    for j in V[i]:
        if j < i: # unique per V and first
            parent_color = Edict[(j,i)]
        else:
            if color == parent_color:
                color += 1
            Edict[(i,j)] = color
            color += 1
print(K)
for i in AB:
    print(Edict[i]+1)