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:
'''ika tako  色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、
まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
 |           `-- 3 ---⑥
 |--- 2 ---③--- 1 ---⑦
 |           `-- 3 ---⑧
 `--- 3 ---④--- 1 ---⑨
             `-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず
未確定である（後でその頂点の処理時に何とでも調整できる）ので、
この方法が使える。
'''
import sys
 
n = int(input())
links = [set() for _ in range(n)]
for i, line in enumerate(sys.stdin):
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add((i, b))
    links[b].add((i, a))

ans = [-1] * (n - 1)
k = max(map(len, links))
q = [(0, -1)]
fixed = set()
 
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for i, u in links[v]:
        if ans[i] != -1:
            continue
        ans[i] = color
        q.append((u, color))
        color += 1
        if c == color:
            color += 1
print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

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

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

# coloring
def dfs(now, color):
    cnt = 1
    for to, num in graph[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1    

dfs(0, 0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque

graph = defaultdict(list)
N, *AB = map(int, open(0).read().split())
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)


stack = deque([1])
C = [0] * (N + 1)
while stack:
    v = stack.popleft()
    c = 0
    for w in graph[v]:
        c += 1 + (c + 1 == C[v])
        C[w] = c
        stack.append(w)
        
print(max(C))
print("\n".join(str(C[b]) for b in AB[1::2]))

Submission status: Accepted

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

N = int(input())
G = [dict() for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1][b-1] = i
    G[b-1][a-1] = i
ans = [0]*(N-1)
visited = [0]*N
def dfs(i,color):
    visited[i] += 1
    c = 1
    for j in G[i]:
        if visited[j]:
            continue
        if c==color:
            c += 1
        ans[G[i][j]] = c
        dfs(j,c)
        c += 1
dfs(0,0)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
#AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)
#for val in AB:
for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for color in colors:
    print(color)

Submission status: Accepted

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

n = int(input())
neighbors = [[] for i in range(n+1)]
ab = []
for i in range(n-1):
    line = list(map(int, input().split()))
    neighbors[line[0]].append(line[1])
    neighbors[line[1]].append(line[0])
    ab.append((line[0], line[1]))
maximum = 0
neighbors_max = 0
for i in range(n):
    if maximum < len(neighbors[i]):
        neighbors_max = i
        maximum = len(neighbors[i])
edgecolors = {}
reached = {neighbors_max}
def make_other_colors(c, m):
    res = []
    if c > m:
        res += [i+1 for i in range(m)]
    else:
        res += [i+1 for i in range(c-1)]
        res += [maximum-i for i in range(m-c+1)]
    return res
def coloring(v, c):
    if c == 0:
        reached.add(v)
        for i in range(len(neighbors[v])):
            edgecolors[(v, neighbors[v][i])] = i + 1
            edgecolors[(neighbors[v][i], v)] = i + 1
            reached.add(neighbors[v][i])
            coloring(neighbors[v][i], i+1)
        return
    l = len(neighbors[v])
    if l == 1 and neighbors[v][0] in reached:
        reached.add(v)
        return
    other_colors = make_other_colors(c, l-1)
    i = 0
    j = 0
    while i < l:
        if neighbors[v][i] in reached:
            i += 1
            continue
        edgecolors[(v, neighbors[v][i])] = other_colors[j]
        edgecolors[(neighbors[v][i], v)] = other_colors[j]
        reached.add(neighbors[v][i])
        coloring(neighbors[v][i], other_colors[j])
        i += 1
        j += 1
coloring(neighbors_max, 0)
print(maximum)
for i in ab:
    print(edgecolors[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = {i: set() for i in range(n)}
edge = []
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edge.append('{} {}'.format(a, b))
    g[a].add(b)
    g[b].add(a)

k = 0
ans = dict()
p_color = [0] * n
used = [1] + [0] * (n - 1)
que = deque([0])
while que:
    now = que.popleft()
    k = max(k, len(g[now]))
    color = 1
    for i in g[now]:
        if used[i]:
            continue
        if p_color[now] == color:
            color += 1
        p_color[i] = ans['{} {}'.format(now, i)] = ans['{} {}'.format(i, now)] = color
        color += 1
        used[i] = 1
        que.append(i)

print(k)
for e in edge:
    print(ans[e])

Submission status: Accepted

Solution code:
import queue

n = int(input())

e = []
f = [{} for i in range(n)]

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

k = 0
for i in range(n-1):
    k = max(k,len(f[i]))

q = queue.Queue()
q.put(0)
used = [[0] for i in range(n)]

while not q.empty():
    p = q.get()
    for key,c in f[p].items():
        if c == 0:
            if used[p][-1]<k:
                col = used[p][-1]+1
            else:
                col = 1
            f[p][key] = col
            f[key][p] = col
            used[p].append(col)
            used[key].append(col)
            q.put(key)

print(k)
for a,b in e:
    print(max(f[a][b],f[b][a]))

Submission status: Accepted

Solution code:
import queue

n = int(input())

e = []
f = [{} for i in range(n)]

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

k = 0
for i in range(n-1):
    k = max(k,len(f[i]))

q = queue.Queue()
q.put(0)
used = [[0] for i in range(n)]
visited = [0]*n
visited[0]=1

while not q.empty():
    p = q.get()
    for key,c in f[p].items():
        if c == 0 and visited[key]==0:
            if used[p][-1]<k:
                col = used[p][-1]+1
            else:
                col = 1
            f[p][key] = col
            used[p].append(col)
            used[key].append(col)
            q.put(key)
            visited[key]=1

print(k)
for a,b in e:
    print(max(f[a][b],f[b][a]))

Submission status: Accepted

Solution code:
n = int(input())
branch = [[] for _ in range(n)]
a, b, inda, indb = [], [], [], []
for _ in range(n-1):
    i, j = map(int, input().split())
    i -= 1
    j -= 1
    branch[i].append(j)
    branch[j].append(i)
    a.append(i)
    b.append(j)
    inda.append(len(branch[i])-1)
    indb.append(len(branch[j])-1)

kind = max([len(i) for i in branch])
print(kind)

# DFS
color = [0 for _ in range(n)]
todo = [0]
color[0] = 1
while len(todo) > 0:
    num = todo.pop(-1)
    col = color[num]
    if col == kind:
        col = 1
    else:
        col = col + 1
    for i in range(len(branch[num])):
        if color[branch[num][i]] == 0:
            color[branch[num][i]] = col
            todo.append(branch[num][i])
            branch[num][i] = -col
            if col == kind:
                col = 1
            else:
                col = col + 1
            

for i in range(n-1):
    if branch[a[i]][inda[i]] < 0:
        print(-branch[a[i]][inda[i]])
    else:
        print(-branch[b[i]][indb[i]])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_d

n = int(input())

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

ans = [0] * (n - 1)
stack = [0]
visited = [-1] * n
visited[0] = 0
while stack:
    node = stack.pop()
    color = 1
    for p in graph[node]:
        if visited[p] < 0:
            if visited[node] == color:
                color += 1
            visited[p] = color
            t = edges[(p, node)]
            ans[t] = color
            stack.append(p)
            color += 1

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

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    que = queue.Queue()
    used = [0 for _ in range(N)]
    parent = [0 for _ in range(N)]
    max_color = 0
    edge_num = {}
    que.put(0)
    used[0] = 1
    while not que.empty():
        cn = que.get()
        color_num = 0
        for nn in G[cn]:
            if used[nn] != 1:
                color_num += 1
                used[nn] = 1
                if (color_num == parent[cn]):
                    color_num += 1
                edge_num[(cn, nn)] = color_num
                parent[nn] = color_num
                que.put(nn)
        max_color = max(max_color, color_num)

    print(max_color)
    for a, b in edge:
        print(edge_num[(a, b)])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def search(x,col_befedge):
    #print("top", x, count)
    global col

    k=1
    for n in adj[x]:
        
        e=tuple(sorted((n,x)))
        #print(e,k,col_befedge)
        if col[e]>0:
            continue
        if k==col_befedge:
            k+=1
        #if k==col_pa:
        #    k+=1
        
        col[e]=k
        search(n,k)
        k+=1
    
            
        

N=int(input())

adj=[[] for i in range(N+1)]

edges=[]
col={}
for i in range(N-1):
    tmp=acinput()
    adj[tmp[0]].append(tmp[1])
    
    adj[tmp[1]].append(tmp[0])
    col[tuple(sorted(tmp))]=0
    edges.append(tuple(sorted(tmp)))

    
#col=[-1]*(N+1)

#col[1]=1
#print(adj)

search(1,0)
#print(reduce(lambda a,b:max(a,b),col.keys))
#print(col)
print(max(col.values()))
#print(col[max(col)])
for se in edges:
    print(col[se])

Submission status: Accepted

Solution code:
import sys
from collections import deque, OrderedDict
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
inputs = OrderedDict()

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    inputs["-".join(list(map(str, sorted([a - 1, b - 1]))))] = 0

K = 0
for e in edge:
    K = max(K, len(e))
print(K)

def dfs(root, edge, inputs):
    done = [True for _ in range(N)]
    done[root] = False
    d = deque([])
    tmp = 1
    for e in edge[root]:
        if done[e]:
            d.append([e, root, tmp])
            tmp += 1
            done[e] = False
    while d:
        data = d.pop()
        inputs["-".join(list(map(str, sorted(data[:2]))))] = data[2]
        tmp = 1
        for e in edge[data[0]]:
            if done[e]:
                if tmp != data[2]:
                    d.append([e, data[0], tmp])
                else:
                    tmp += 1
                    d.append([e, data[0], tmp])
                tmp += 1
                done[e] = False
    
    return inputs

inputs = dfs(0, edge, inputs)

for i in inputs.values():
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque, OrderedDict
sys.setrecursionlimit(10 ** 7)

N = int(input())
count = [[] for _ in range(N)]
inputs = OrderedDict()

for _ in range(N - 1):
    a, b = map(int, input().split())
    count[a - 1].append(b - 1)
    count[b - 1].append(a - 1)
    inputs["-".join(list(map(str, sorted([a - 1, b - 1]))))] = 0

K = 0
for c in count:
    K = max(K, len(c))
print(K)

def dfs(root, count, inputs):
    done = [-1 for _ in range(N)]
    done[root] = 0
    d = deque([root])
    r = d.pop()
    childs = count[r]
    tmp = 1
    for c in childs:
        if done[c] == -1:
            d.append([c, r, tmp])
            tmp += 1
            done[c] += 1
    while d:
        data = d.pop()
        inputs["-".join(list(map(str, sorted(data[:2]))))] = data[2]
        childs = count[data[0]]
        tmp = 1
        for c in childs:
            if done[c] == -1:
                if tmp != data[2]:
                    d.append([c, data[0], tmp])
                else:
                    tmp += 1
                    d.append([c, data[0], tmp])
                tmp += 1
                done[c] += 1
    
    return inputs

inputs = dfs(0, count, inputs)

for i in inputs.values():
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    l = len(connected[temp[0]-1])
    if l > 1:
        used = deque(range(1,l+1))
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                color = used.popleft()
                if color == ans[temp[1]]:
                    ans[edge[1]] = used.popleft()
                else:
                    ans[edge[1]] = color
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
INF = 1145141919810364364334
n = int(input())
c = []
b = [0] * (n-1)
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b[i] = map(int,input().split())
    edge[a-1].append(b[i]-1)
    edge[b[i]-1].append(a-1)
    c.append(a)
    c.append(b[i])

d = Counter(c)
hen = d.most_common()[0][1]

col = [INF] * n
col[0] = 0

q = deque()
q.append(0)

while q:
    x = q.popleft()
    no = (col[x] + 1) % hen
    for i in edge[x]:
        if col[i] == INF:
            col[i] = no
            no = (no+1) % hen 
            q.append(i)
            
print(hen)
for i in range(n-1):
    print(col[b[i]-1] + 1)

Submission status: Accepted

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

n = int(input())
g = [[] for _ 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 dfs(now, color):
    cnt = 1
    for to, num in g[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)

dfs(0, -1)

print(max(colors.values()))
for a, b in ab:
    print(colors[(a, b)])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque
 
N = int(stdin.readline().rstrip())
adj = defaultdict(set)
edges = []

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    edges.append((a,b))
    
visited = [False]*(N+1)
color_edges = defaultdict(bool)
visit_p = deque()
visit_p.append((1,0))
 
while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        color_edges[(node,i)] = cnt
        visit_p.append((i,cnt))
print(max(color_edges.values()))
for i in edges:
    if not color_edges[i]:
        print(color_edges[(i[1],i[0])])
    else:
        print(color_edges[i])

Submission status: Accepted

Solution code:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  G[a-1].append((i,b-1))
  G[b-1].append((i,a-1))
ans=[0]*(N-1)  
def dfs(now_node,pre_node,pre_c):
  color=1
  
  for t in G[now_node]:
    num,next_node=t
    if next_node==pre_node:
      continue
    next_color=color
    if next_color==pre_c:
      next_color+=1
    ans[num]=next_color
    #print(i,next_color)
    dfs(next_node, now_node,next_color)
    color=next_color+1
dfs(0,-1,-1)
print(max(ans))
for a in ans:
  print(a)

Submission status: Accepted

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

N=int(input())
G=[[] for _ 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 dfs(now,color):
  cnt=1
  for to,j in G[now]:
    if cnt==color:
      cnt+=1
    ans[j]=cnt
    dfs(to,cnt)
    cnt+=1

dfs(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 _ 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 dfs(now, color):
  cnt = 1
  for to, j in G[now]:
    if cnt == color:
      cnt += 1
    ans[j] = cnt
    dfs(to, cnt)
    cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# Problem D - Coloring Edges on Tree

from collections import deque

# input
N = int(input())
node_list = {} # 隣接リストの作成
color_count_list = [0]*(N+1)
ans_list = []
for i in range(N-1):
    a, b = map(int, input().split())
    if a in node_list:
        node_list[a].append(b)
    else:
        node_list[a] = [b]
    color_count_list[a] += 1
    color_count_list[b] += 1
    ans_list.append([a, b])

# initialization
color_list = {}
color_max_count = max(color_count_list)

# bfs search
visit_queue = deque([[-1, 1]]) # [[既に使った色], 遷移ノード]
while len(visit_queue)>0:
    p = visit_queue.popleft()

    used_color = p[0]
    if p[1] in node_list:
        nodes = node_list[p[1]]
        nodes_len = len(nodes)
        color_num = 1
        if nodes_len>=1:
            coloring_count = 0
            while coloring_count<nodes_len:
                if color_num==used_color:
                    color_num += 1
                    continue
                # 隣接リストによる表現
                if p[1] in color_list:
                    color_list[p[1]][nodes[coloring_count]] = color_num
                else:
                    color_list[p[1]] = {nodes[coloring_count]:color_num}
                if nodes[coloring_count] in color_list:
                    color_list[nodes[coloring_count]][p[1]] = color_num
                else:
                    color_list[nodes[coloring_count]] = {p[1]:color_num}
                # queue insert
                visit_queue.append([color_num, nodes[coloring_count]])
                # color update
                coloring_count += 1
                color_num += 1

# output
print(color_max_count)
for a in ans_list:
    print(color_list[a[0]][a[1]])

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())
G = {i:[] for i in range(1,N+1)}
E = {}
A = []
for _ in range(N-1):
    a,b = map(int,input().split())
    A.append((a,b))
    G[a].append(b)
    G[b].append(a)
    E[(a,b)] = 0
hist = [0 for _ in range(N+1)]
heap = deque([1])
c = 1
for y in G[1]:
    E[(1,y)]=c
    c += 1
K = c-1
hist[1]=1
while heap:
    x = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            K = max(K,len(G[y]))
            col = [0 for _ in range(min(K,len(G[y]))+1)]
            for z in G[y]:
                if y<z and E[(y,z)]<len(col):
                    col[E[(y,z)]]=1
                elif z<y and E[(z,y)]<len(col):
                    col[E[(z,y)]]=1
            cur = 1
            for z in G[y]:
                if y<z and E[(y,z)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(y,z)]=i
                            cur = i+1
                            break
                elif z<y and E[(z,y)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(z,y)]=i
                            cur = i+1
                            break
            heap.append(y)
            hist[y]=1
print(K)
for e in A:
    print(E[e])

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

color = {}    
from collections import deque
q = deque([(0, 0)])
while len(q) > 0:
    src, c_prev = q.popleft()
    c = 1
    for dst in graph[src]:
        if c == c_prev: c += 1
        key = '{0}-{1}'.format(min(src, dst), max(src, dst))
        if color.setdefault(key, 0) == 0:
            color[key] = c
            q.append((dst, c))
            c += 1

print(max(color.values()))
for ai, bi in ab:
    key = '{0}-{1}'.format(min(ai, bi) - 1, max(ai, bi) - 1)
    print(color[key])

Submission status: Accepted

Solution code:
from collections import deque
import collections
n = int(input())
edge = []
cl = dict()
edge_ar = []
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    edge_ar.append((a,b))

q = deque([(0,1)])
used = set()
used.add(1)
while q:
    this = q.popleft()
    pre = this[0]
    here = this[1]
    k = 1
    for i in edge[here]:
        if i not in used:
            while True:
                if k != pre:
                    cl[(i,here)] = k
                    cl[(here,i)] = k
                    k += 1
                    break
                else:
                    k += 1
            used.add(i)
            q.append((k-1,i))
cl_num = collections.Counter(cl)
cl_num = max(list(cl_num.values()))
print(cl_num)
for i in edge_ar:
    print(cl[i])

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ 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))
    G[b].append((a,i))

ans=[-1]*(N-1)
cmx=0
stk=[0]
while stk:
    v=stk.pop()
    cs=set()
    for to,toi in G[v]:
        if ans[toi]>=0: cs.add(ans[toi])
    c=1
    for to,toi in G[v]:
        if ans[toi]>=0: continue
        while c in cs: c+=1
        ans[toi]=c
        cmx = max(cmx, c)
        cs.add(c)
        stk.append(to)

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

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

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

ans = [-1] * (N - 1)
st = [(0, -1)]
while st:
    now, pr = st.pop()

    C = []
    D = set()
    for i, _ in edges[now]:
        D.add(ans[i])
    for i in range(len(edges[now]) + 1)[::-1]:
        if i in D:
            continue
        C.append(i)

    for i, to in edges[now]:
        if to == pr:
            continue
        ans[i] = C.pop()
        st.append((to, now))

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

Submission status: Accepted

Solution code:
n=int(input())
edge=[[]for _ in range(n)]
point=[0]*n
edges=[]
point_color=[-1]*n
edge_color={}
edge_to_int=lambda x,y:min(x,y)*100007+max(x,y)
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges.append((a,b))
  edge[a].append(b)
  edge[b].append(a)
  point[a]+=1
  point[b]+=1
ans=max(point)
ind=point.index(ans)
Q=[ind]
visited={ind}
while Q:
  P=[]
  for i in Q:
    color=0
    for j in edge[i]:
      if j in visited:continue
      visited.add(j)
      P.append(j)
      color+=1
      if point_color[i]==color:color+=1
      point_color[j]=color
      edge_color[edge_to_int(i,j)]=color
  Q=P
print(ans)
for a,b in edges:
  print(edge_color[edge_to_int(a,b)])

Submission status: Accepted

Solution code:
from queue import deque

N = int(input())

A = []
B = [[]for i in range(N)]

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

q = deque([0])
color = [-1]*N
ans = {}
saidai = 0
while q:
    nord = q.popleft()
    c = 0
    for i, v in enumerate(B[nord]):
        if color[nord] == i:
            c += 1
        color[v] = c + i 
        ans[(nord, v)] = c + i
        q.append(v)
        saidai = max(saidai,i+c+1)

print(saidai)

for i, j in A:
    print(1+ans[(i-1, j-1)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    dfs(u,v,k)
    k+=1
dfs(0)
for c in l: print(c)

Submission status: Accepted

Solution code:
from collections import deque

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

edges = [[]for _ in range(n)]
for x, y in e_list:
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)

# bfsの準備
q = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
q.append(0)
eColor_dic = {}
max_color = 0
# bfs
while q:
    here = q.popleft()
    color = 1
    for i in edges[here]:
        if visited[i]:
            continue
        q.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        eColor_dic[(here, i)] = color
        color_list[i] = color
        max_color = max(max_color, color)
        color += 1

print(max_color)
for x, y in e_list:
    print(eColor_dic[(x-1, y-1)])