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 queue
n = int(input())


#ab = [[]*(n)]
ab = [[] for _ in range(n+1)]
#print(ab)

li = []

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

#ab_color = [[None for _ in range(n+1)] for _ in range(n+1)]
ans = [0] * (n-1)

q = queue.Queue()
check = [0] * (n+1)
#check[1] == 1
check_color = [0] * (n+1)

q.put(1)
color_num = 1
#mae_color = 0

while not q.empty():
    tmp_color = 0
    tmp = q.get()
    #print(tmp)
    #tmp_color = mae_color
    mae_color = check_color[tmp]
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i][0]] == 1:
            #print(i,tmp)
            continue
        else:
            #print(mae_color,tmp_color,tmp,i)
            tmp_color += 1
            q.put(ab[tmp][i][0])
            if tmp_color == mae_color:
                tmp_color += 1
            check_color[ab[tmp][i][0]] = tmp_color
            ans[ab[tmp][i][1]] = tmp_color
            #ab_color[ab[tmp][i]][tmp] = tmp_color
            #ab_color[tmp][ab[tmp][i]] = tmp_color
            check[tmp] = 1
            if color_num < tmp_color:
                color_num = tmp_color
            #color_num = max(color_num,tmp_color)
            #print(check,i)

print(color_num)
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])

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])


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

colors = [0] * (N-1)
while q:
  node, parent, edge_color = q.popleft()
  c = 1
  for child, index in G[node]:
    if child == parent:
      continue
    
    if c == edge_color:
      c += 1
    
    q.append([child, node, c])
    colors[index] = c
    c += 1

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

Submission status: Accepted

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

Q = deque([(0, -1)])
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.appendleft((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = deque([(0, -1)])
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = deque([(0, -1)])
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.appendleft((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
X = [deque() for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = deque([(0, -1)])
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.appendleft((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Submission status: Accepted

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

from collections import deque

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

tree = {}
node_in = [0 for i in range(n)] # 頂点に入る辺は1つ
node_out = [[0] for i in range(n)] # 頂点から出る辺は1つ以上
for edge in sorted(edges):
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b

    color = 0
    if node_out[a-1][-1] == 0:
        if node_in[a-1] <= 1: # node_in[a-1] == 0の時1、1の時2なのでまとめて
            color = node_in[a-1] + 1
        else: # node_in[a-1] >= 2
            color = 1
    else:
        color = node_out[a-1][-1] + 1
        if node_in[a-1] == color:
            color += 1
            
    tree[(a, b)] = color
    node_out[a-1].append(color)
    node_in[b-1] = color

print(max(tree.values()))
for edge in edges:
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b
    print(tree[(a, b)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())

M = [set() for _ in range(N)]

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

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

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

Submission status: Accepted

Solution code:
n = int(input())
vs = [[] for i in range(n)]
out = [0]*n

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

nex = [[0,-1]]

def coloring(index,defColor):
    i=0
    for v in vs[index]:
        if i==defColor:
           i+=1
        out[v[1]]=i
        vs[v[0]].remove([index,v[1]])
        nex.append([v[0],i])
        i+=1
    out[0] = max(out[0],i-1)

while nex.__len__()>0:
    c,d = nex.pop()
    coloring(c,d)

for i in range(n):
    print(out[i]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = [(0, -1)]
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = [(0, -1)]
ANS = [-1] * (N-1)
maxc = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        if c>maxc:maxc=c
        Q.append((y, c))
        c += 1

print(maxc)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    P[b-1] = a-1

Q = [(0, -1)]
ANS = [-1] * (N-1)
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
vertex_neighbor_vertices = {}  # 各頂点と、その頂点に隣接する頂点リストのマップ
vertex_colors = {}  # 各頂点と、その頂点を端点に持つ辺に塗られた色セットのマップ
sides = []  # 辺情報（(a_i, b_i)のタプル形式で、順番を保持）
side_color = {}  # 辺とその辺に塗られた色のマップ


def add_neighbors(start, end):
    neighbors_of_s = set()
    if start in vertex_neighbor_vertices:
        neighbors_of_s = vertex_neighbor_vertices[start]
    else:
        vertex_neighbor_vertices[start] = neighbors_of_s
    neighbors_of_s.add(end)


def init_colors(vertex):
    colors = set()
    if vertex not in vertex_colors:
        vertex_colors[vertex] = colors


def get_unused_color(colors_of_sv, colors_of_ev, color_start):
    for i in range(color_start, N + 1):
        if (i not in colors_of_sv) and (i not in colors_of_ev):
            return i


for i in range(N - 1):
    s, e = map(int, input().split())
    sides.append((s, e))
    add_neighbors(s, e)
    add_neighbors(e, s)
    init_colors(s)
    init_colors(e)

max_color_num = 0
max_neighbor_vertex = 0
for k, v in vertex_neighbor_vertices.items():
    if len(v) > max_color_num:
        max_color_num = len(v)
        max_neighbor_vertex = k

print(max_color_num)

# 辺を最も多く持つ頂点を起点に、幅優先探索で辺を色付けしていく
visited = set()
q = deque([max_neighbor_vertex])

while q:
    vertex = q.popleft()
    visited.add(vertex)
    # 色付け
    color_start = 1
    for neighbor in vertex_neighbor_vertices[vertex]:
        if neighbor in visited:
            continue
        q.append(neighbor)
        color = get_unused_color(vertex_colors[vertex], vertex_colors[neighbor], color_start)
        color_start = color + 1
        vertex_colors[vertex].add(color)
        vertex_colors[neighbor].add(color)
        side_color[(vertex, neighbor)] = color

for s, e in sides:
    color = 0
    if (s, e) in side_color:
        color = side_color[(s, e)]
    else:
        color = side_color[(e, s)]
    print(color)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
num_of_edge = [0] * N
edge = defaultdict(list)

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

K = max(num_of_edge)

ans = [0] * (N-1)
stack = [(0, -1, 0)]
while stack:
    cur, past, color = stack.pop()
    color_cand = 1
    for cand, num in edge[cur]:
        if cand != past:
            if color_cand == color:
                color_cand += 1
            ans[num] = color_cand
            stack.append((cand, cur, color_cand))
            color_cand += 1

print(K)
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import queue as qu
import bisect



def resolve():
    N=int(input())
    nod=[[[],[]] for i in range(N)]
    path=[[] for i in range(N-1)]
    col=[0 for i in range(N-1)]


    for i in range(N-1):
        path[i]=[int(i)-1 for i in input().split()]
        nod[path[i][1]][0].append(i)
        nod[path[i][0]][0].append(i)
    mx=0
    mnod=0
    for i in range(N):
        if len(nod[i][0])>mx:
            mx=len(nod[i][0])
            mnod=i
    print(mx)

    q=qu.Queue(N)
    q.put(mnod)

    while not q.empty():

        tagnod=q.get()
        nod[tagnod][1].sort()
        nod[tagnod][0].sort()
        cc=1
        pointer=0
        for i in range(len(nod[tagnod][0])-1,-1,-1):
            tp=nod[tagnod][0][i]

            while pointer<len(nod[tagnod][1]) and nod[tagnod][1][pointer] == cc:
                cc+=1
                pointer+=1
            col[tp]=cc
            if tagnod==path[tp][0]:
                nnod=path[tp][1]
            else:
                nnod=path[tp][0]

            bisect.insort(nod[nnod][1],cc)
            nod[nnod][0].remove(tp)
            q.put(nnod)
            cc+=1

    for i in col:
        print(i)





if __name__ == "__main__":
    resolve()
#    unittest.main()

Submission status: Accepted

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


def main():
    N = int(input())
    C = []
    T = [[] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = [int(x) for x in input().split()]
        T[a].append([b, i])
        T[b].append([a, i])
        C.append(a)
        C.append(b)
    

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

    visited = set()
    ans = [0] * N
    while q:
        i, color = q.popleft()
        visited.add(i)
        now_color = 0
        for v, j in T[i]:
            if not v in visited:
                now_color += 1
                if now_color == color:
                    now_color += 1
                q.append([v, now_color])
                ans[j] = now_color
    
    print(max(ans))
    for i in range(N - 1):
        print(ans[i])



    

    



if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N = int(input())
    C = []
    T = [[] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = [int(x) for x in input().split()]
        T[a].append([b, i])
        T[b].append([a, i])
        C.append(a)
        C.append(b)
    
    c = Counter(C)
    print(c.most_common(1)[0][1])

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


    visited = set()
    ans = [0] * N

    while q:
        i, color = q.popleft()
        visited.add(i)
        now_color = 0
        for v, j in T[i]:
            if not v in visited:
                now_color += 1
                if now_color == color:
                    now_color += 1
                q.append([v, now_color])
                ans[j] = now_color
    
    for i in range(N - 1):
        print(ans[i])



    

    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, c = -1 , p = -1):
    k = 1    
    for e in node.edge:
        if e == p:
            continue
        if k == c:
            k += 1
        # 子のノードを取得
        child = tree[e]

        # 答えを記録
        if a < b:
            ans['{0} {1}'.format(node.num, child.num)] = k
        else:
            ans['{0} {1}'.format(child.num, node.num)] = k
        k += 1

        # 掘る
        dfs(child,k - 1, node.num)


N = int(input())
ans = {}
# colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)

# print("edges:{}".format(edges))
# print(max(c))
# print(ans)
count = 0
for node in tree:
    count = max(count, len(node.edge))
print(count)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))

Submission status: Accepted

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

n = inp()
aa = [0] * (n-1)
bb = [0] * (n-1)
g = [[] for i in range(n)]
res = defaultdict(lambda : defaultdict(int))
for i in range(n-1):
    a,b = inpl()
    aa[i] = a-1
    bb[i] = b-1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def dfs(i,c=-1,p=-1):
    # print('i:{}'.format(i))
    cnt = 1
    for j in g[i]:
        # print(res[j][i])
        if j == p:
            continue
        if cnt == c:
            cnt += 1
        res[i][j] = cnt
        res[j][i] = cnt
        cnt += 1
        dfs(j,res[i][j],i)
dfs(0)
m = 0
for i in g:
    m = max(m, len(i))
print(m)
for i in range(n-1):
    print(res[aa[i]][bb[i]])

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 = [0]*(N-1)

def func(prt, col):
    cnt = 1
    for cld, org in G[prt]:
        if cnt==col:
            cnt += 1
        ans[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

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

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(prt, col):
    cnt = 1
    for cld, org in G[prt]:
        if cnt==col:
            cnt += 1
        ans[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]

# graph[i]: 頂点iの親と子の集合
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 根
root = 1
# parent[i]: 頂点iの親
parent = [0]*(N+1)
# トポロジカル順序(dfsの順番)
order = []
# 未探索の頂点
stack = [root]

# dfsでparentを求める
while stack:
    # n: 探索する頂点
    n = stack.pop()
    order.append(n)
    for j in graph[n]:
        # jがnの親の場合
        if j == parent[n]:
            continue
        parent[j] = n
        stack.append(j)

# color[i]: 頂点iと親を繋ぐ辺の色
color = [-1] * (N+1)
# dfsで頂点iから出る辺の色を塗る
for i in order:
    # 既に使用した色
    ng = color[i]
    # 色
    c = 1
    for j in graph[i]:
        # jがiの親の場合(塗装済みなのでcontinue)
        if j == parent[i]:
            continue
        if c == ng:
            c += 1
        # 頂点iと頂点jの辺に色を塗る
        color[j] = c
        c += 1

# 入力順に辺の色を出力する
answer = [color[a] if parent[a]==b else color[b] for a,b in AB]
print(max(answer))
print("\n".join(map(str,answer)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]

# graph[i]: 頂点iの親と子の集合
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 根
root = 1
# parent[i]: 頂点iの親
parent = [0]*(N+1)
# トポロジカル順序
order = []
# 未探索の頂点
stack = [root]

# dfsでparentを求める
while stack:
    # n: 探索する頂点
    n = stack.pop()
    order.append(n)
    for j in graph[n]:
        # jがnの親の場合
        if j == parent[n]:
            continue
        parent[j] = n
        stack.append(j)

# color[i]: 頂点iと親を繋ぐ辺の色
color = [-1] * (N+1)
# dfsで頂点iから出る辺の色を塗る
for i in order:
    # 既に使用した色
    ng = color[i]
    # 色
    c = 1
    for j in graph[i]:
        # jがiの親の場合(塗装済みなのでcontinue)
        if j == parent[i]:
            continue
        if c == ng:
            c += 1
        # 頂点iと頂点jの辺に色を塗る
        color[j] = c
        c += 1

# 入力順に辺の色を出力する
answer = [color[a] if parent[a]==b else color[b] for a,b in AB]
print(max(answer))
print("\n".join(map(str,answer)))

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=0
for e in E:
    k=max(k,len(e))
ans=[0]*(n-1)
def dsf(v,p,vp_c):
    c=1
    for u,i in E[v]:
        if u!=p:
            if c==vp_c:
                c+=1
            ans[i]=c
            dsf(u,v,c)
            c+=1
dsf(1,0,0)
print(k)
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
n=int(input())
s=[[]for _ in range(n)]
d={}
f=[]
for i in range(n-1):
  a,b=map(int,input().split())
  d[min(a,b)*1000000+max(a,b)]=10**7
  s[a-1].append(b-1)
  s[b-1].append(a-1)
  f.append((a-1,b-1))
se={0}
mc=max(len(s[i])for i in range(n))
print(mc)
Q=[(0,i)for i in s[0]]
r=[-1]*n
r[0]=0
while Q:
  P=[]
  b=-1
  for i,j in Q:
    if j in se:continue
    if b!=i:x=1
    else:x+=1
    if r[i]==x:x+=1
    b=i
    se.add(j)
    for k in s[j]:
      P.append((j,k))
    d[min(i,j)*1000000+max(i,j)]=x
    r[j]=x
  Q=P
for i,j in f:print(d[min(i,j)*1000000+max(i,j)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]

# graph[i]: 頂点iの親と子の集合
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 根
root = 1
# parent[i]: 頂点iの親
parent = [0]*(N+1)
# トポロジカル順序
order = []
# 未探索の頂点
stack = [root]

# dfsでparentを求める
while stack:
    # n: 探索する頂点
    n = stack.pop()
    order.append(n)
    for j in graph[n]:
        # jがnの親の場合
        if j == parent[n]:
            continue
        parent[j] = n
        stack.append(j)

# color[i]: 頂点iと親を繋ぐ辺の色
color = [-1] * (N+1)
# dfsで色を塗る
for i in order:
    # 既に使用した色
    ng = color[i]
    # 色
    c = 1
    for j in graph[i]:
        # jがiの親の場合(塗装済みなのでcontinue)
        if j == parent[i]:
            continue
        if c == ng:
            c += 1
        # 頂点iと頂点jの辺に色を塗る
        color[j] = c
        c += 1

# 入力順に辺の色を出力する
answer = [color[a] if parent[a]==b else color[b] for a,b in AB]
print(max(answer))
print("\n".join(map(str,answer)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def main():
    N = int(readline())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    m = map(int,read().split())
    AB = list(zip(m,m))
    for a, b in AB:
        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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def main():
    N, *ab = map(int, read().split())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    for a, b in zip(*[iter(ab)] * 2):
        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:
import sys
from collections import deque
read = sys.stdin.read

def main():
    N, *ab = map(int, read().split())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    for a, b in zip(*[iter(ab)] * 2):
        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:
import sys
input = sys.stdin.readline

N = int(input())
adj = [[] for i in range(N)]
ran = [0]*N
ans = [0]*(N-1)
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    adj[a].append([b,i])
    adj[b].append([a,i])
    ran[a]+=1
    ran[b]+=1
K = max(ran)
ind = ran.index(K)
print(K)

que = [[ind,0]]
while len(que)!=0:
    i,c = que.pop(0)
    col = 1
    for jlis in adj[i]:
        if col == c:
            col += 1
        if ans[jlis[1]]==0:
            ans[jlis[1]] = col
            que.append([jlis[0],col])
            col += 1
print("\n".join([str(i) for i in ans]))

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):
        if focus == N-1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            # if child < N-1:
            #     dfs(child,color)
            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:
from collections import deque
n = int(input())
l = [[] for _ in range(n)]
ans = [0]*(n-1)
q = deque()
color = [0]*n # 保持している色(初期:なし)
count = 0
for i in range(n-1):
    x,y = map(lambda x: int(x)-1, input().split())
    if i == 0:
        q.append(x) # 探索開始ノードを追加
    l[x].append((y,i))
    l[y].append((x,i))
while count<n-1:
    node = q.popleft()
    c = 1
    for d, ind in l[node]:
        if ans[ind] == 0:
            if c == color[node]:
                c += 1
            ans[ind] = c
            q.append(d) # キューを保存
            color[d] = c # 色の保存
            c += 1
            count += 1
print(max(ans))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)


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

for i in range(n-1):
    a,b = map(int,input().split())
    lis[a].append((b,i))
    lis[b].append((a,i))
k = max(len(li) for li in lis)
print(k)
ans = [-1] * (n-1)
def dfs(v = 1, p = 0, p_col = -1):
    col = 1
    for u,idx in lis[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())
G = [[] for i in range(n)]
root = 0
color_num = 0

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))
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [(root, -1)]
checked = set()
answer = [-1] * (n - 1)

while len(queue) > 0:
  node, c = queue.pop(0)
  color = 1
  for node2, index in G[node]:
    if node2 not in checked:
      if color == c:
        color = c + 1
      answer[index] = color
      color += 1
      queue.append((node2, answer[index]))
  checked.add(node)
print('\n'.join(map(str, answer)))

Submission status: Accepted

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

n = int(input())
child_list = [[] for i in range(n)]

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

ans = [None]*(n-1)


def rec(node, parent_color_id):
    default_color_id = 1
    color_id = default_color_id

    for child_node, no in child_list[node]:
        if parent_color_id == color_id:
            color_id += 1
        ans[no] = color_id
        rec(child_node, color_id)
        color_id += 1


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

Submission status: Accepted

Solution code:
from collections import deque

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)
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])