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:
# 深さ優先探索
from sys import setrecursionlimit


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


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

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

colors = {}
q = [(0, -1, -1)]
while q:
    currentNode, usedColor, parentNode = q.pop()
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        q.append((childNode, color, currentNode))
        color += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    e = [[] for _ in range(n + 1)]
    # q = deque([1])
    q = [1]
    c = [0] * (n + 1)
    for a, b in zip(*[iter(ab)] * 2):
        e[a].append(b)
    while q:
        s = q.pop(0)
        d = 0
        for t in e[s]:
            d += 1 + (d + 1 == c[s])
            c[t] = d
            q.append(t)
    return str("{}\n{}".format(max(c), "\n".join(str(c[b]) for _, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edge = [set() for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].add((b, i))
    edge[b].add((a, i))
    
r = [0] * (N-1)
q = deque([(0, 1)])

while q:
    preC, fromv = q.popleft()
    c = 0
    for tov, i in edge[fromv]:
        edge[tov].remove((fromv, i))
        c += 1 + (c + 1 == preC)
        q.append((c, tov))
        r[i] = c

print(max(r))
for x in r:
    print(x)

Submission status: Accepted

Solution code:


N = int(input())
edges = [[] for i in range(N+1)]
A = [-1 for i in range(N-1)]

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

def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"

    next = 1
    for (v, i) in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[i] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(root))

for a in A:
  print(a)

Submission status: Accepted

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    Y = G[x]
    k = D[x] + 1
    while Y:
        y = Y.pop(0)
        if x in G[y]:
            G[y].remove(x)
        if k > K:
            k -= K
        list.append(y)
        d[(x,y)] = k
        D[y] = k 
        k += 1
        if k > K:
            k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])

Submission status: Accepted

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


n = int(input())

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

def dfs(now, prev = 0):
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    color = 1
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
    
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        dfs(next, now)

COLORS = {(0, 1):0}
dfs(1)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    '''
    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l
    '''

q = deque([(1, -1)])
while(q):
    a, ng = q.popleft()
    bs = PT[a]

    c = 1
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        cab = COLOR[(na, nb)]

        if cab == ng:
            continue

        if cab == 0:
            if c == ng:
                c += 1
            clr = c
            COLOR[(na, nb)] = clr
            q.append((b, clr))
            c += 1

print(max(COLOR.values()))

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))

Submission status: Accepted

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


n = int(input())

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

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

COLORS = {(0, 1):0}
Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Submission status: Accepted

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


n = int(input())

GRAPH = {i:[] for i in range(1, n + 1)}
EDGES = []
COLORS = {(0, 1):0}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    EDGES.append((a, b))
    COLORS[(a, b)] = 0

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Submission status: Accepted

Solution code:
# 要復習，tmpわかってない
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    uv = [LIST() for i in range(N - 1)]

    # graphがあればまずグラフを辞書で書く
    graph = defaultdict(list)

    # 辺，edge，key: ，value:色情報
    edge = defaultdict(int)

    for u, v in uv:
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)
    
    K = 0
    for v in graph.values():
        # 最も長いリストの長さになる
        K = max(K, len(v))
    color = list(range(1, K + 1))
    
    # 使う色の数，これだけつかえばいい
    # print("K", K)
    # print("color:", color)
    que = deque()
    que.append((0, None))

    # bfs
    # use_color:その辺で使うカラー
    while que:
        i, color_from = que.popleft()
        tmp = -1
        for node in graph[i]:
            str_ = "{},{}".format(i, node)
            if not edge[str_]:
                # 一番最後のカラー
                use_color = color[tmp]
                if use_color == color_from:
                    # 同じなら，一番最後から前に下がっていく
                    use_color = color[tmp - 1]
                    tmp -= 1
                tmp -= 1

                edge[str_] = use_color
                # 逆も然り
                edge["{},{}".format(node, i)] = use_color
                que.append((node, use_color))
    print(K)
    for u, v in uv:
        print(edge["{},{}".format(u-1, v-1)])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))
 
 
ans = max(count)
c = 1
 
 
 
def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i in pr:
            continue
        if c == col:
            c+=1
        x, y = sorted([i, idx])
        color[(x, y)] = c
        dfs(i, (x, y))
        c+=1
 
color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Submission status: Accepted

Solution code:
from collections import deque
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
# bfsによる色付けを行う
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])

Submission status: Accepted

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

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            c+=1
            if c==m+1:
                c=1
            dcolars[tuple(sorted([point,i]))]=c
            BFS(d,i,c)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Accepted

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

G = defaultdict(list)
EdaNum = defaultdict(int)

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

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**7)
n=int(input())
s=[[]for i in range(n+1)]
t=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    s[a-1].append([b-1,i])
def f(x,r):
    c=1
    for (i,j) in s[x]:
        c+=(c==r)
        t[j]=c 
        f(i,c)
        c+=1
f(0,0)
print(max(t))
for i in t:
    print(i)

Submission status: Accepted

Solution code:
def main():

    from collections import deque


    N = int(input())
    B = []
    L = []
    for i in range(N-1):
        ta,tb = map(int,input().split())
        B.append(ta)
        B.append(tb)
        L.append([ta,tb])
    B =B[1::2]
    E = [[] for _ in range(N + 1)]
    for a, b in L:
        E[a].append(b)

    Q = deque([1])
    C = [0] * (N + 1)
    while Q:
        v = Q.popleft()
        c = 0
        for u in E[v]:
            c += 1 + (c + 1 == C[v])
            C[u] = c
            Q.append(u)

    print(max(C))
    print("\n".join(str(C[b]) for b in B))
main()

Submission status: Accepted

Solution code:
from collections import deque


N = int(input())
B = []
L = []
for i in range(N-1):
    ta,tb = map(int,input().split())
    B.append(ta)
    B.append(tb)
    L.append([ta,tb])
B =B[1::2]
E = [[] for _ in range(N + 1)]
for a, b in L:
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
print("\n".join(str(C[b]) for b in B))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)
n = int(input())
bfs_dic = [{} for i in range(n)]
ans = [0 for i in range(n-1)]

def bfs(pn, pc, node):
    c = 1
    max_c = 0
    
    if len(bfs_dic[node]) != 1 or pc == 0: #葉は見ない(葉でも最初だけは子を見る)
        for k,v in bfs_dic[node].items():
            if k == pn: continue #親と同じなら無視
            if pc == c:                 #親と色被っちゃったら色変え
                c+=1
            ans[v] = c
            maxable_c = bfs(node, c, k)
            if max_c < maxable_c:
                max_c = maxable_c
            c+=1                        #子と自分の間に色割り当てて色変える
        if max_c < c-1:
            return c-1
        else:
            return max_c
    return 1                                        #葉やったら1色しか使っとらん
            
for i in range(n-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    bfs_dic[a][b] = i
    bfs_dic[b][a] = i

print(bfs(-1, 0, 0))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import collections 
import sys
sys.setrecursionlimit(1000000)

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

visited = [False]*n
colors = [0]*(n-1)

max_colors = max(len(t) for t in T)
que = deque([(0,0)])


while que:
    node, p_color = que.popleft()
    visited[node] = True
    color = 1
    
    for nxt_n, nxt_e in T[node]:
        if visited[nxt_n] == True:
            continue
        if color == p_color:
            color += 1
        colors[nxt_e] = color
        que.append((nxt_n, color))
        color += 1

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

Submission status: Accepted

Solution code:

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


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

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
'''input
6
1 2
1 3
1 4
1 5
1 6
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import defaultdict
import sys, threading


def get_source(graph):
	for i in graph:
		return i


def make(first, second):
	return str(first) + ' ' + str(second)


def dfs(graph, node, visited, color, medges, mx_c):
	visited[node] = True
	c = 1
	for i in graph[node]:
		if i not in visited:
			if color[node] == c:
				c += 1
			color[i] = c
			medges[make(node, i)] = c
			medges[make(i, node)] = c
			mx_c[0] = max(mx_c[0], c)
			c += 1
			dfs(graph, i, visited, color, medges, mx_c)


# main starts
def main():
	graph = defaultdict(list)
	n = int(input().strip())
	edges = []
	for _ in range(n - 1):
		u, v = list(map(int, input().split()))
		graph[u].append(v)
		graph[v].append(u)
		edges.append([u, v])

	s = get_source(graph)
	color = dict()
	visited = dict()
	color[s] = 0
	medges = dict()
	mx_c =[0]
	dfs(graph, s, visited, color, medges, mx_c)

	print(mx_c[0])
	for i, j in edges:
		print(medges[make(i, j)])


if __name__ == '__main__':
	sys.setrecursionlimit(100005)
	threading.stack_size(1 << 27)
	thread = threading.Thread(target = main)
	thread.start()

Submission status: Accepted

Solution code:
from collections import deque

def edge_key(node1, node2):
    return '-'.join([str(min(node1, node2)), str(max(node1, node2))])

def bfs(si):
    q = deque()
    q.append([si, -1])
    used.add(si)

    while len(q) > 0:
        prv_node, prv_col = q.popleft()
        col = 1
        for node in g[prv_node]:
            if node in used:
                continue
            else:
                if col == prv_col:
                    col += 1

                cols[eds[edge_key(prv_node, node)]] = col
                q.append([node, col])
                used.add(node)
                col += 1

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

used = set()
cols = [-1 for _ in range(N-1)]
bfs(0)
print(max(cols))
[print(col) for col in cols]

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

dic = {}
color = {}
root = [0]*N

for i in range(N):
    dic[i+1] = []
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    dic[i].append(j)
    dic[j].append(i)
    root[i-1] += 1
    root[j-1] += 1
    color[(i,j)] = 0
root_node = root.index(1)+1
ma = max(root)
def rec(now_node,prevcolor):
    nowcolor = 0
    tg_list = dic[now_node][:]
    for elem in tg_list:
        nowcolor += 1
        if nowcolor == prevcolor:
            nowcolor += 1
        dic[elem].remove(now_node)
        color[(elem,now_node)] = nowcolor
        color[(now_node,elem)] = nowcolor
        rec(elem,nowcolor)
rec(root_node,0)
print(ma)
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    print(color[(i,j)])

Submission status: Accepted

Solution code:
from collections import deque

n=int(input()) 
#S = []
#for _ in range(n-1):
#    S.append(list(map(int, input().split())))

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

#print(max([len(p) for p in pt]))
ans=[0]*(n-1)
visit=[-1]*n
q=deque([0])
visit[0]=0

while q:
    v=q.popleft()
    count=1
    for x in edges[v]:
        if visit[x]<0:
            if count==visit[v]:
                count+=1
            q.append(x)
            visit[x]=count
            ans[l[(v,x)]]=count
            count+=1
            
print(max(ans))
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

graph = [[] for _ in range(n)]

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

que = deque([(0, None)])
visited = [False] * n
visited[0] = True
# edge = [None] * n
edge = [{} for _ in range(n)]

color_n = -1
while que:
    now, skip = que.popleft()
    i = 0
    for t in graph[now]:
        if not visited[t]:
            if i == skip:
                i += 1
            que.append((t, i))
            visited[t] = True
            # edge[t] = i + 1
            edge[now][t] = i + 1
            color_n = max(color_n, i + 1)
            i += 1

print(color_n)
for f, t in inputs:
    print(edge[f].get(t) or edge[t].get(f))

Submission status: Accepted

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

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab2 = [[] for i in range(n)]
for i in range(n-1):
  ab2[ab[i][0]-1].append([ab[i][1]-1, i])
  ab2[ab[i][1]-1].append([ab[i][0]-1, i])
coloring = [0]*(n-1)

def f(x, y, z):
  c = 0
  for i in ab2[x]:
    if i[0] != y:
      c += 1
      if c == z:
        c += 1
      coloring[i[1]] = c
      x1 = i[0]
      y1 = x
      z1 = c
      f(x1, y1, z1)

f(0, None, None)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[a[i] - 1].append((b[i] - 1, i))
        conns[b[i] - 1].append((a[i] - 1, i))
    k = 0
    for i in range(N):
        k = max(k, len(conns[i]))
    ret = [0] * (N - 1)
    def dfs(idx, prev, visited):
        visited[idx] = True
        color = 0 if prev != 0 else 1
        for node, idx in conns[idx]:
            if not visited[node]:
                ret[idx] = color + 1
                dfs(node, color, visited)
                color += 1
                if color == prev:
                    color += 1
    visited = [False] * N
    dfs(0, -1, visited)
    print(k)
    for r in ret:
        print(r)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
K=max([len(i) for i in G])
print(K)
q=deque([])
q.append(0)
reached=[0 for i in range(N)]
parentsnum=[-1 for i in range(N)]
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    index=0
    if parentsnum[r]!=-1:
        index=(parentsnum[r]+1)%K
    for p in G[r]:
        if reached[p]==1:
            continue
        edges[(min(r,p),max(r,p))]=index
        parentsnum[p]=index
        index+=1
        index%=K
        q.append(p)
for i in range(N-1):
    print(edges[min(a[i],b[i]),max(a[i],b[i])]+1)

Submission status: Accepted

Solution code:
import queue
n = int(input())
tree_node = [set() for _ in range(n)]
hen = []
hen_col = {}
for i in range(n-1):
    a,b = map(int,input().split())
    tree_node[a-1].add(b)
    hen.append([a,b])
    hen_col[str(a)+'-'+str(b)] = 0
q = queue.Queue()
q.put(1)
parent_node = [0] * n
parent_color = [0] * n
maxcol = 0
while not q.empty():
    col = 0
    nod = q.get()
    for i,c in enumerate(tree_node[nod-1]):
        if i+1 == parent_color[nod-1]:col+=1
        tempcol = i+1+col
        parent_color[c-1]=tempcol
        maxcol = max(maxcol,tempcol)
        q.put(c)
        l = min(nod,c)
        r = max(nod,c)
        hen_col[str(l)+'-'+str(r)] = tempcol
        parent_node[c-1] = nod

print(maxcol)
for t in hen:
    tempstr = str(t[0])+'-'+str(t[1])
    print(hen_col[tempstr])