Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

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

class Node:
    def __init__(self, id_=0):
        self.id = id_
        self.link = []
        self.edge_ids = []
        self.check = False

def main():
    N = int(input())
    ab = [list(map(int, input().split())) for i in range(N-1)]

    nodes = [Node(i) for i in range(N+1)]
    for i, (a, b) in enumerate(ab):
        nodes[a].link.append(nodes[b])
        nodes[a].edge_ids.append(i)
        nodes[b].link.append(nodes[a])
        nodes[b].edge_ids.append(i)
    
    ans = 0
    edge_colors = [0 for i in range(N-1)]

    q = deque()
    # キューの中身: (node, このノードに来るエッジで使った色ID)
    q.append((nodes[1], 0))
    nodes[1].check = True

    while len(q) > 0:
        node, pre_color = q.popleft()
        # print("at ", node.id)
        next_color = 1
        for next_node, edge_id in zip(node.link, node.edge_ids):
            if not next_node.check:
                # print("next ", next_node.id)
                if next_color == pre_color:
                    next_color += 1
                ans = max(ans, next_color)
                edge_colors[edge_id] = next_color
                q.append((next_node, next_color))
                next_node.check = True
                next_color += 1
    
    print(ans)
    for color in edge_colors:
        print(color)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i 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=[0]*(N-1)
g=[0]*N
def dfs(v,h=-1):
  res=1
  for i,j in es[v]:
      if g[i]:
            continue
      g[v]=1
      if h==res:
            res+=1
      ans[j]=res
      dfs(i,res)
      res+=1

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

Submission status: Accepted

Solution code:
from collections import deque

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

que=deque([0])
while que:
   s=que.pop()
   color=1
   for ni in G[s]:
      if ans[s]==color:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.popleft()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for ni in L:
   print(ans[ni])

Submission status: Accepted

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for ni in L:
   print(ans[ni])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	a, b = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
 
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
 
print(max(ans))
for node in node_list:
	print(ans[node])

Submission status: Accepted

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


def main():
    # 再帰の上限回数のデフォルトを変更
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 7)

    n = int(input())
    graph = [list() for _ in range(n)]
    ans = [0 for _ in range(n - 1)]

    # KeyInsight:
    # 木の問題と再帰関数は相性がいい
    # See:
    # https://www.youtube.com/watch?v=7IlBVSglZqc
    for i in range(n - 1):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai].append((bi, i))
        graph[bi].append((ai, i))

    # 実装できなかったところ
    # 1. 色のカウントをどう管理するか?
    # 2. 辺のidをどう管理するか?

    # 親方向からの色番号を引数に持つ
    def dfs(vertex, parent=-1, edge_color=-1):
        # 一般的なポイント: 頂点に関する処理を書く
        color_code = 1

        # 基本形: 親の頂点周りを探索
        for to, edge_id in graph[vertex]:
            if to == parent:
                continue

            # 一般的なポイント: 辺に関する処理を書く
            if color_code == edge_color:
                color_code += 1

            ans[edge_id] = color_code
            color_code += 1

            dfs(to, vertex, ans[edge_id])
            # 一般的なポイント: 辺に関する処理を書く

        # 一般的なポイント: 頂点に関する処理を書く

    dfs(0)
    count = 0

    for g in graph:
        count = max(count, len(g))

    print(count)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 7)

    n = int(input())
    graph = [list() for _ in range(n)]
    ans = [0 for _ in range(n - 1)]

    # KeyInsight:
    # 木の問題と再帰関数は相性がいい
    # See:
    # https://www.youtube.com/watch?v=7IlBVSglZqc
    for i in range(n - 1):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai].append((bi, i))
        graph[bi].append((ai, i))

    def dfs(vertex, parent=-1, edge_color=-1):
        color_code = 1

        for to, edge_id in graph[vertex]:
            if to == parent:
                continue

            if color_code == edge_color:
                color_code += 1

            ans[edge_id] = color_code
            color_code += 1

            dfs(to, vertex, ans[edge_id])

    dfs(0)
    count = 0

    for g in graph:
        count = max(count, len(g))

    print(count)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class Edge:
    def __init__(self, first, second):
        self.color = 0
        self.first = first
        self.second = second

def main():
    def dfs(i, par, pcol):
        cc = 1
        for e in v[i]:
            if cc == pcol:
                cc += 1
            if e.color == 0:
                e.color = cc
                dfs(e.second, par, cc)
                cc += 1

    n = int(input())
    e = [[] for _ in range(n-1)]
    v = [[] for _ in range(n+1)]

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

    dfs(1, -1, 0)

    m = 0
    for i in range(n-1):
        m = max(m,e[i].color)

    print(m)
    for i in range(n-1):
        print(e[i].color)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
edges = [[] for _ in range(N + 1)]
ends = []
 
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    ends.append(b)
 
nodes = deque([1])
count = [0] * (N + 1)
 
while nodes:
    node = nodes.popleft()
    nodes.extend(edges[node])
 
    c = 0
    for n in edges[node]:
        c += 1 + (c + 1 == count[node])
        count[n] = c
 
print(max(count))
for i in ends:
    print(count[i])

Submission status: Accepted

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

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

    K = 0
    for i in range(N):
        K = max(K, len(edges[i]))

    visited = [False] * N

    def dfs(v, color):
        visited[v] = True
        for l, m in enumerate(edges[v]):
            if visited[m[0]]:
                continue
            color += 1
            color %= K
            ans.append((m[1],color))
            dfs(m[0], color)

    dfs(0,0)

    ans.sort()
    print(K)
    for a, b in ans:
        print(b+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
from collections import deque
def clear_maze(s):

    INF=-10**9
    ans = [INF for i in range(n)]
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            v=1
            x = d.popleft()
            for i in range(len(b[x])):
                y=b[x][i]
                if ans[y] == INF:
                    d.append(y)
                    if ans[x]==v:
                        v+=1
                    ans[y]=v
                    v+=1
        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)


c=clear_maze(0)
print(max(c))
for i in range(n-1):
    print(c[a[i][1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

n=int(input())
l=[[] for i in range(n)]
ans=[0]*(n-1)

def dfs(v,c,p):
  k=1
  for i in range(len(l[v])):
    u=l[v][i][0]
    id=l[v][i][1]
    if(u==p):continue
    if(k==c):k+=1
    ans[id]=k
    dfs(u,ans[id],v)
    k+=1
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append((b-1,i))
  l[b-1].append((a-1,i))
dfs(0,-1,-1)
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
node_dic = {}
ab_array = [list(map(int,input().split())) for _ in range(N-1)]

for a,b in ab_array:
    if a in node_dic:
        node_dic[a][b] = 0
    else:
        node_dic[a] = {b : 0}
    if b in node_dic:
        node_dic[b][a] = 0
    else:
        node_dic[b] = {a : 0}

# print(node_dic)

max_color = 0

queue = deque()
flag = [0] * N
first = ab_array[0][0]
queue.append((first,0))
flag[first-1] = 1

while len(queue):
    p, ban_color = queue.popleft()
    now_color = 1
    for key in node_dic[p].keys():
        if now_color == ban_color:
            now_color += 1
        if flag[key-1] == 0:
            queue.append((key,now_color))
            node_dic[p][key] = now_color
            node_dic[key][p] = now_color
            flag[key-1] = 1
            max_color = max(max_color,now_color)
            now_color += 1
print(max_color)
for a,b in ab_array:
    print(node_dic[a][b])

Submission status: Accepted

Solution code:
from collections import OrderedDict
from collections import deque
N = int(input())
G = [[] for _ in range(N)]
od = OrderedDict()

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    od[(a,b)] = 0 ## ここに色を入れてく

used = [False]*N # 親ノードは考えない
parent2colors = [0]*N ## その頂点をインデックスとしたと親との辺の色のリスト
que = deque()
que.append(0)
used[0] = True
colors = 0

while len(que) != 0:
    v = que.popleft()
    colors = max(colors,len(G[v]))
    cur_color = 1
    for nv in G[v]:
        if used[nv]:continue # 親への辺は無視
        if cur_color == parent2colors[v]:
            cur_color += 1

        if (v,nv) in od.keys():
            od[(v,nv)] = cur_color
        else:
            od[(nv,v)] = cur_color
        parent2colors[nv] = cur_color
        cur_color += 1
        used[nv] = True
        que.append(nv)

print(colors)
for edge_clr in od.values():
    print(edge_clr)

Submission status: Accepted

Solution code:
import copy ; import sys ; sys.setrecursionlimit(11451419)
n=int(input())
HEN=[list(map(int,input().split())) for _ in range(n-1)]
G=[[] for _ in range(n)]
for i,[a,b] in enumerate(HEN):
    a=a-1;b=b-1
    G[a].append([b,i])
    G[b].append([a,i])  #Gに、道番号も記録

visited=[0 for i in range(n)]
ans=[-1 for i in range(n-1)]

def search(v,c=-1):  #search(a)ならaと-1  search(a,b)ならaとb
    nc=1
    for to,i in G[v]:
        if visited[to]==1: continue
        visited[v]=1
        if c==nc:
            nc+=1
        ans[i]=nc
        search(to,nc)
        nc+=1
search(0)
print(max(ans))
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import heapq as h

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

flag=[0 for i in range(0,N+1)]
ans=[0 for i in range(0,N)]

count=0
subcount=0
q=[]
h.heapify(q)
h.heappush(q,1)
sub=[]
h.heapify(sub)
while q!=[]:
    if q==[1]:
        subcount=0
        usedcolor=0
        x=h.heappop(q)
        for p in hen[x]:
            if flag[p[0]]==0:
                subcount+=1
                h.heappush(sub,p[0])
            else:
                colored=p[0]
                usedcolor=ans[p[1]]
        count=subcount
        color=1
        for p in hen[x]:
            if flag[p[0]]==0:
                if color!=usedcolor:
                    ans[p[1]]=color
                    color+=1
                else:
                    color+=1
                    ans[p[1]]=color
                    color+=1
        flag[x]=1
        q=sub
        sub=[]
        h.heapify(sub)

    else:
        while q!=[]:
            subcount=0
            colored=0
            usedcolor=0
            x=h.heappop(q)
            for p in hen[x]:
                if flag[p[0]]==0:
                    subcount+=1
                    h.heappush(sub,p[0])
                else:
                    colored=p[0]
                    usedcolor=ans[p[1]]
            if subcount>=count:
                count=subcount+1
            color=1
            for p in hen[x]:
                if flag[p[0]]==0:
                    if color!=usedcolor:
                        ans[p[1]]=color
                        color+=1
                    else:
                        color+=1
                        ans[p[1]]=color
                        color+=1
            flag[x]=1
            if q==[]:
                q=sub
                sub=[]
                h.heapify(sub)
                break
print(count)
for i in range(1,N):
    print(ans[i])

Submission status: Accepted

Solution code:
n = int(input())
ab=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    ab.append(tmp)
link = [[] for _ in range(n)]
for tmp in ab:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

cnt=0
for l in link:
    if cnt < len(l):
        cnt=len(l)
print(cnt)

from collections import deque
from collections import defaultdict
Q = deque()
Q.append([0,0]) # now, color
cs = defaultdict(lambda: -1)
while Q:
    now,now_color= Q.popleft()

    nxt_c=now_color
    for nxt in link[now]:
        if cs[str(now)+"_"+str(nxt)] !=-1:
            continue

        nxt_c = (nxt_c+1) % cnt
        cs[str(now)+"_"+str(nxt)] = nxt_c
        cs[str(nxt)+"_"+str(now)] = nxt_c
        Q.append([nxt,nxt_c])

for tmp in ab:
    print(cs[str(tmp[0]-1) + "_" + str(tmp[1]-1)]+1)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
l = [0 for i in range(n)]
l2 = []
l3 = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l2.append([a,b])
    l3[a].append(b)
    l3[b].append(a)
    l[a-1] += 1
    l[b-1] += 1
a = max(l)
print(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([1,0])
rl[1] = 1
dic = {}
while len(d):
    now,c = d.popleft()
    rl[now] = 1
    if c == 0:
        count = 1
        for i in l3[now]:
            dic["{0},{1}".format(now,i)] = count
            d.append([i,count])
            count += 1
    else:
        count = 1
        for i in l3[now]:
            if rl[i] == 0:
                if c == count:
                    count += 1
                dic["{0},{1}".format(now,i)] = count
                d.append([i,count])
                count += 1
for i in range(n-1):
    print(dic["{0},{1}".format(l2[i][0],l2[i][1])])

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
 
E = [[] for _ in [0]*N]
for i,ab in enumerate(AB):
    a,b = ab
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
 
done = [False]*N
done[0] = True
ans = [0]*(N-1)
q = [(0,0)]
while q:
    i,c0 = q.pop()
    c = 1
    for j,ei in E[i]:
        if done[j]:continue
        done[j] = True
        if c==c0: c+=1
        q.append((j,c))
        ans[ei] = c
        c += 1
 
print(max(ans))
for out in ans:
    print(out)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [0 for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        K = set()
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            k = len(G[u])
            c = (G_c[u] % k) + 1
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    colors[u, v] = c
                    colors[v, u] = c
                    G_c[u] = c
                    G_c[v] = c
                    K.add(c)
                    c = c % k + 1
            G_color[u] = 'BLACK'
        return K
    K = bfs(0)
    print(len(K))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in range(N)]
dic = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    dic[(a, b)] = i

k = 0
for e in E:
    k = max(k, len(e))

ans = [0]*(N-1)
from collections import deque
q = deque()
q.append((0, 0))
used = [0]*N
used[0] = 1
while q:
    temp = q.pop()
    v = temp[0]
    num = temp[1]
    for t in E[v]:
        if used[t] == 1:
            continue
        used[t] = 1
        a = min(v, t)
        b = max(v, t)
        num += 1
        ans[dic[(a, b)]] = (num%k) + 1
        q.append((t, (num%k)))
print(k)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i 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))

visited = [0]*N
ans = [None]*(N-1)

def dfs(v,c=-1):
    nc = 1
    for to,i in es[v]:
        if visited[to]: continue
        visited[v] = 1
        if nc==c:
            nc += 1
        ans[i] = nc
        dfs(to,nc)
        nc += 1
dfs(0)
print(max(ans))
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for i in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, i))
  e[v].append((u, i))
res = [0] * (N - 1)
def dfs(x):
  global res
  c = 1
  vis = set()
  for y, i in e[x]: vis.add(res[i])
  #print(x, vis)
  for y, i in e[x]:
    if res[i] > 0: continue
    while c in vis: c += 1
    #print(x, c)
    res[i] = c
    vis.add(c)
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) # while文の回数上限

N = int(input())
G = [list() for _ in range(N)]
E = list()
D = dict()

for _ in range(N-1):
  a,b = map(int, input().split())
  a -= 1; b -= 1;
  G[a].append(b)
  G[b].append(a)
  if a > b:
    a,b=b,a
  E.append((a,b))

k = max(len(G[i]) for i in range(N))

q = [(0,-1,-1)]
while q:
  cc = 1
  v,p,c = q.pop()
  for x in G[v]:
    if x == p:
      continue
    if cc == c:
      cc += 1
    if v<x:
      D[(v,x)] = cc
    else:
      D[(x,v)] = cc
    q.append((x,v,cc))
    cc += 1

print(k)
for i in E:
  print(D[i])

Submission status: Accepted

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

n = int(input())
edge = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))
colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))
print(colors)
work_q = deque()
work_q.append((1, -1, -1))
color = [-1] * (n - 1)

while work_q:
    here, prev, col = work_q.popleft()
    cnt = 1
    for to, ind in edge[here]:
        if to == prev:
            continue
        if cnt == col:
            cnt += 1
        color[ind] = cnt
        work_q.append((to, here, cnt))
        cnt += 1
print(*color, sep="\n")

Submission status: Accepted

Solution code:
import collections

n=int(input())
edges=[list(map(int,input().split())) for _ in range(n-1)]
g=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=edges[i]
  g[a].append(b)
  g[b].append(a)
k=0
pos=0
for i in range(n+1):
  if len(g[i])>k:
    k=len(g[i])
    pos=i
print(k)
dic={}
q=collections.deque()
q.append((pos,0))
checked=[0]*(n+1)
checked[pos]=1
while 1:
  if len(q)==0:
    break
  u,c=q.popleft()
  l=len(g[u])
  tcs=[i+1 for i in range(l)]
  if c in tcs:
    tcs.remove(c)
  pos=0
  for i in range(len(g[u])):
    v=g[u][i]
    if checked[v]==0:
      checked[v]=1
      q.append((v,tcs[pos]))
      dic[(u,v)]=tcs[pos]
      dic[(v,u)]=tcs[pos]
      pos+=1
for i in range(n-1):
  a,b=edges[i]
  print(dic[(a,b)])

Submission status: Accepted

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


def dfs(v, c):
    nc = 0
    k = 0
    for nv, idx in edge[v]:
        if status[nv] == 0:
            nc = nc + 1 + ((nc + 1) == c)
            color[idx] = nc
            status[nv] = 1
            k = max(k, dfs(nv, nc))
    return max(nc, k)


N = int(input())
edge = [[] for _ in range(N)]
for idx, line in enumerate(sys.stdin.readlines()):
    a, b = map(lambda x: int(x) - 1, line.split())
    edge[a].append((b, idx))
    edge[b].append((a, idx))

status = [0] * N
color = [0] * (N - 1)
status[0] = 1
K = dfs(0, 0)

print(K)
for c in color:
    print(c)

Submission status: Accepted

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

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

def col(now,color):
  c=1
  for (b,j) in A[now]:
    if c==color:
      c+=1
    ans[j]=c
    col(b,c)
    c+=1
col(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
sortedAB = sorted(AB)
con = {i: [] for i in range(1, N+1)}
color = [0] * (N + 1)
for a, b in sortedAB:
    con[a].append(b)

for i in range(1, N + 1):
    now_c = 1
    for c in con[i]:
        if color[i] == now_c:
            now_c += 1
        color[c] = now_c
        now_c += 1

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

a = 0

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N + 1)]
ends = []

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

nodes = deque([1])
count = [0] * (N + 1)

while nodes:
    node = nodes.popleft()
    nodes.extend(edges[node])

    c = 0
    for n in edges[node]:
        c += 1 + (c + 1 == count[node])
        count[n] = c

print(max(count))
for i in ends:
    print(count[i])

Submission status: Accepted

Solution code:
n=int(input())
node={i:[] for i in range(1,n+1)}
visited=[False for i in range(n+1)]
q=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    q.append((a,b))

mother=q[0][0]
visited[mother]=True

d=[]
e=[]


paint={i:{} for i in range(1,n+1)}

mother_paint=[0 for i in range(n+1)]

#使う要素 node visited paint mother_paint の四つのリスト
c=1
for child in node[mother]:
    visited[child]=True
    paint[mother][child]=c
    paint[child][mother]=c
    mother_paint[child]=c
    c+=1
    d.append(child)
    
while d:
    for parent in d:
        p=1 
        for child in node[parent]:
            if visited[child]==False:
                visited[child]=True
                if p!=mother_paint[parent]:
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
                else:
                    p+=1
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
    if e:
        d=e
        e=[]
    else:
        d=[]
        e=[]
K=0
for i in range(1,n+1):
    K=max(K,len(node[i]))
print(K)
for i in range(n-1):
    s,t=q[i][0],q[i][1]
    print(paint[s][t])

Submission status: Accepted

Solution code:
n=int(input())
node={i:[] for i in range(1,n+1)}
visited=[False for i in range(n+1)]
q=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    q.append((a,b))

mother=q[0][0]
visited[mother]=True

d=[]
e=[]


paint={i:{} for i in range(1,n+1)}

mother_paint=[0 for i in range(n+1)]

#使う要素 node visited paint mother_paint の四つのリスト
c=1
for child in node[mother]:
    visited[child]=True
    paint[mother][child]=c
    paint[child][mother]=c
    mother_paint[child]=c
    c+=1
    d.append(child)
    
while d:
    for parent in d:
        p=1 
        for child in node[parent]:
            if visited[child]==False:
                visited[child]=True
                if p!=mother_paint[parent]:
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
                else:
                    p+=1
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
    if e:
        d=e.copy()
        e=[]
    else:
        d=[]
        e=[]
K=0
for i in range(1,n+1):
    K=max(K,len(node[i]))
print(K)
for i in range(n-1):
    s,t=q[i][0],q[i][1]
    print(paint[s][t])

Submission status: Accepted

Solution code:
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]

connects = [[] for i in range(n+1)]
for e in edges:
    connects[e[0]].append(e[1])
    connects[e[1]].append(e[0])

x = max([len(i) for i in connects])
print(x)

from collections import deque
nodeQ = deque([1])
begin = {1: 0}
ecolors = {}

while len(nodeQ):
    node = nodeQ.popleft()
    ncolor = begin[node]
    nconnect = list(filter(lambda n: n > node, connects[node]))
    
    for i, ni in enumerate(nconnect):        
        begin[ni] = (ncolor + i) % x + 1
        ecolors[(node, ni)] = begin[ni]
        # print(node, ni, begin[ni])
        nodeQ.append(ni)
             
for e in edges:
    print(ecolors[e])

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

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

k=[0]*N

from collections import deque

q=deque([0])
visited=[0]*N
ans={}
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    visited[x]=1
    cnt=1
    for i in G[x]:
        if visited[i]!=0:continue
        if p[x]==cnt:
            cnt+=1
        ans[(x,i)]=cnt
        ans[(i,x)]=cnt

        p[i] = cnt
        cnt += 1
        kmx=max(kmx,cnt-1)
        q.append(i)

print(kmx)
for i in range(N-1):
    print(ans[(a[i],b[i])])

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  n=int(input())
  
  edges=[]
  for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges.append([a,b,i])

  edges.sort(key=lambda i:i[0])
  color=[0]*(n-1)
  head=[0]*n #上から来る色
  before=[0]*n #直前に使った色
  
  for i in range(n-1):
    a=edges[i][0]
    b=edges[i][1]
    index=edges[i][2]
    if before[a]+1==head[a]:
      c=before[a]+2
    else:
      c=before[a]+1
    before[a]=c
    head[b]=c
    color[index]=c
    
  print(max(color))
  print(*color,sep='\n')
  
if __name__=='__main__':
  main()