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 collections import deque

n = int(input())

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

ver = [[] for i in range(n)]

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

#print(ver)

color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1

#print(q)

while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1

#print(color)
k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])

Submission status: Accepted

Solution code:
from collections import deque

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


used = [0]*N
used[0] = 1
a = dict()
parent = [0]*N
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            a[(r,j)] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(a[pair])

Submission status: Accepted

Solution code:
n=int(input())
import sys
sys.setrecursionlimit(10**6)
s=[[] for _ in range(n)]

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

l=[0]*(n-1)

def dfs(node,pre_col,par):
    col=1
    for nei,i in s[node]:
        if nei==par:
            continue
        if col==pre_col:
            col+=1
        l[i]=col
        dfs(nei,col,node)
        col+=1
dfs(0,-1,-1)
print(max(l))
for i in l:
    print(i)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    adj = [[] for _ in range(n)]
    order = []
    for a,b in ab:
        adj[a-1].append(b-1)
        order.append(b-1)

    

    c = [0]*n
    d = deque([0])
    while d:
        v = d.popleft()
        cnt = 1
        for nv in adj[v]:
            if c[v] == cnt:
                cnt += 1
            c[nv] = cnt
            cnt += 1
            d.append(nv)

    print(max(c))

    for i in order:
        print(c[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

cols = [set(list([x+1 for x in range(len(gp[i]))])) for i in range(N)]

seen = set()
stk = [0]
max_col = 0
while stk:
    pt = stk.pop()
    #print(pt)
    if(pt in seen):
        continue
    seen.add(pt)
    for nxt, ind in gp[pt]:
        if(nxt in seen):
            continue
        col = cols[pt].pop()
        max_col = max(col, max_col)
        edge_col[ind] = col
        try:
            cols[nxt].remove(col)
        except:
            pass

        stk.append(nxt)

print(max_col)
for i in edge_col:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N)]
edge_index = {}
ab = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
for i, (a, b) in enumerate(ab):
    edges[a].append(b)
    edges[b].append(a)
    edge_index[(a, b)] = edge_index[(b, a)] = i
# print(edges)

max_degree = 0
root = 0
for i in range(N):
    if len(edges[i]) > max_degree:
        max_degree = len(edges[i])
        root = i

color = [-1]*(N-1)
visited = [False]*N
visited[root] = True

stack = deque()  # (vertex, color_index)
for i, to in enumerate(edges[root]):
    color[edge_index[(root, to)]] = i+1
    visited[to] = True
    stack.append((to, i+1))

while stack:
    v, v_col = stack.pop()
    color_condidate = 0
    for to in edges[v]:
        assert color_condidate <= max_degree, "hello"
        if visited[to]:
            continue
        visited[to] = True
        color_condidate += 1
        if color_condidate == v_col:
            color_condidate += 1
        idx = edge_index[(v, to)]
        color[idx] = color_condidate
        stack.append((to, color_condidate))

print(max_degree)
print(*color, sep='\n')

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)]
AB = [lr() for _ in range(N-1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [(root, 0)]
color = [0] * (N+1)
# 頂点と、親方向の辺を対応させる
while stack:
    cur, ng = stack.pop()
    c = 1
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        if c == ng:
            c += 1
        parent[next] = cur
        color[next] = c
        stack.append((next, c))
        c += 1

answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])

print(max(answer))
print(*answer, sep='\n')
# 02

Submission status: Accepted

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

def bfs():
    q = deque([(0, 0)])
    visited = [False]*N
    visited[0] = True
    
    while q:
        v, c = q.popleft()
        now = 1
        
        for nv in G[v]:
            if not visited[nv]:
                if now==c:
                    now += 1
                    
                k = 10**6*min(v, nv)+max(v, nv)
                ans[k] = now
                q.append((nv, now))
                visited[nv] = True
                now += 1

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

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

ans = defaultdict(int)
bfs()
K = max(list(ans.values()))

print(K)

for a, b in edges:
    print(ans[10**6*a+b])

Submission status: Accepted

Solution code:
#python3
from collections import deque

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

def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        g[a].append(Edge(b, i))
        g[b].append(Edge(a, i))

    dq = deque() 
    dq.append(0) 
    done = [0 for _ in range(n)]
    done[0] = 1
    ans = [0 for _ in range(n-1)]


    while len(dq):
        v = dq.pop()
        c = -1
        for i in range(len(g[v])):
            u = g[v][i].to
            ei = g[v][i].d
            if done[u]:
                c = ans[ei]
        k = 1
        for i in range(len(g[v])): 
            u = g[v][i].to
            ei = g[v][i].d
            if done[u]:
                continue 
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dq.append(u)
            done[u] =  1
            

    mx = 0
    for i in range(len(g)):
        mx = max(mx, len(g[i]))

    print(mx)
    for i in ans:
        print(i)
main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)]
graph = [[] for _ in range(N+1)] # 1-indexed
for i in range(N-1):
    a, b = AB[i]
    AB[i] = tuple(sorted([a, b]))
    graph[a].append(b)
    graph[b].append(a)

AB_to_C = defaultdict(int)
root = 1
parent = [0] * (N+1)
stack = [root]
while stack:
    cur = stack.pop()
    used = 0
    if parent[cur] != 0:
        used = AB_to_C[tuple(sorted([cur, parent[cur]]))]
    color = 1
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        while True:
            if color == used:
                color += 1
            else:
                AB_to_C[tuple(sorted([cur, next]))] = color
                color += 1
                break
        stack.append(next)

answer = [0] * (N-1)
for i in range(N-1):
    answer[i] = AB_to_C[AB[i]]

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

Submission status: Accepted

Solution code:
from collections import deque, OrderedDict

n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]
# print(edges)
tree = [[] for _ in range(n)]
# Zero-based index. グラフを陽に持つ。
edge_color = OrderedDict()  # 辺のタプルをキーにした順序付き辞書
for e in edges:
    a = e[0] - 1
    b = e[1] - 1
    tree[a].append(b)
    tree[b].append(a)
    edge_color[(min(a, b), max(a, b))] = 0

print(max(len(v) for v in tree))

seen = [False] * n  # 踏破
que = deque()
que_append = que.append
que_popleft = que.popleft
start = 0
seen[start] = True
que_append(start)
# ある頂点に接する辺にすでに塗られた色のセット。
v_based_color = [set() for _ in range(n)]
while len(que):
    v = que_popleft()
    color_i = 1  # One-based index.
    for adj in tree[v]:
        if seen[adj]:
            continue
        seen[adj] = True
        que_append(adj)
        while color_i in v_based_color[v]:
            # その頂点からの辺で使われていない色になるまで足す。
            color_i += 1
        edge_color[(min(v, adj), max(v, adj))] = color_i
        # 辺の両端の頂点が触れている色のセットに追加。
        v_based_color[v].add(color_i)
        v_based_color[adj].add(color_i)
        color_i += 1

{print(c) for c in edge_color.values()}

Submission status: Accepted

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

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

# topological順序の計算
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    x = s.pop()
    order.append(x)
    for nx in g[x]:
        if nx == parent[x]:
            continue
        parent[nx] = x
        s.append(nx)

color = [0]*n
for v in order:
    ng = color[v]
    c = 1
    for u in g[v]:
        if u == parent[v]:
            continue
        if c == ng:
            c += 1
        color[u] = c
        c += 1

ans = []
for a, b in e:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[list(map(int,input().split())) for _ in range(n-1)]
tree=[[] for _ in range(n)]
for a,b in graph:
    tree[a-1].append(b-1)
color=[0]*n
q=deque([0])
while q:
    c=1
    x=q.popleft()
    for i in tree[x]:
        if c==color[x]:
            c+=1
        color[i]=c
        c+=1
        q.append(i)
print(max(color))
for j in range(n-1):
    print(color[graph[j][1]-1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
ab = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
T = [[] for i in range(N)]
for a,b in ab:
    T[a].append(b)
q = deque([0])
color = [0]*N
while q:
    x = q.popleft()
    c = 1
    for y in T[x]:
        if c==color[x]:
            c+=1
        color[y] = c
        c+=1
        q.append(y)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])

Submission status: Accepted

Solution code:
N=int(input())
#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)
S=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  S[a-1].append((b-1, i))
  S[b-1].append((a-1, i))

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)

print(max(L))
for l in L:
  print(l)

Submission status: Accepted

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

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n)]
z = []
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    g[a].append(b)
    g[b].append(a)
    if a<b:
        z.append((a,b))
    else:
        z.append((b,a))

from collections import deque

parent = [0]*n
mc = 0
en = dict()

q = deque()
used = [0]*n
q.append(0)
used[0] = 1
while q:
    p = q.popleft()
    color = 0
    for i in g[p]:
        if used[i] != 1:
            color += 1
            used[i] = 1
            if color==parent[p]:
                color += 1
            if p<i:
                en[(p,i)]=color
            else:
                en[(i,p)]=color
            parent[i] = color
            q.append(i)
    mc = max(mc,color)

print(mc)
for i in z:
    print(en[i])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
lines=[[] for i in range(n)]
for a,b in ab:
  lines[a-1].append(b-1)
q=deque([0])
color=[0]*n
while q:
  x=q.popleft()
  c=1
  for y in lines[x]:
    if c==color[x]:
      c+=1
    color[y]=c
    c+=1
    q.append(y)
print(max(color))
for i in range(n-1):
  print(color[ab[i][1]-1])

Submission status: Accepted

Solution code:
#abc146d
n=int(raw_input())
e={}
t=[[] for i in range(n)]
c=[1]*(n-1)
for i in range(n-1):
 a,b=map(int,raw_input().split())
 a,b=a-1,b-1
 t[a].append(b)
 e[(a,b)]=i
cp=[[] for i in range(n)]
for i in range(n):
 x=1
 for vc in t[i]:
  while x in cp[i]:
   x+=1
  c[e[(i,vc)]]=x
  cp[vc].append(x)
  x+=1
print max(c)
for i in range(len(c)):
 print c[i]

Submission status: Accepted

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

n=int(input())
L=[[] for i in range(n)]
V=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
    V.append([a,b])
k=max(len(l) for l in L)

C=[-1]*n
D=[-1]*n
C[0]=0
D[0]=0
q=queue.Queue()
q.put(0)
while not q.empty():
    now=q.get()
    c=C[now]
    for i in L[now]: #子に対して
        if D[i]==-1:
            c=(c+1)%k
            C[i]=c
            D[i]=D[now]+1
            q.put(i)

print(k)
for v in V:
    if D[v[0]]>D[v[1]]:
        print(C[v[0]]+1)
    else:
        print(C[v[1]]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n=int(input())
L=[[] for i in range(n)]
V=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
    V.append([a,b])
k=max(len(l) for l in L)
C=[-1]*n
D=[-1]*n
def dfs(s,p=-1,d=0): #深さ優先探索(親,上の辺の色,深さ)
    c=C[s]
    for i in L[s]: #子に対して
        if i!=p: #親と一緒じゃないとき
            c=(c+1)%k
            C[i]=c
            D[i]=d
            dfs(i,s,d+1) #色をつけ、スタートを更新し、再探索

dfs(0)
print(k)
for v in V:
    if D[v[0]]>D[v[1]]:
        print(C[v[0]]+1)
    else:
        print(C[v[1]]+1)

Submission status: Accepted

Solution code:
N = int(input())

import sys
sys.setrecursionlimit(10**6)

def dfs(v, c, p):
    k = 1
    for _v, _id in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

V = [[] for _ in range(N)]
C = [-1 for _ in range(N-1)]

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

dfs(0, -1, -1)
print(max(C))
for i in range(N-1):
    print(C[i])

Submission status: Accepted

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

V = [[] for _ in range(N)]
C = [-1 for _ in range(N - 1)]


# v:頂点, c:色, p:親
def dfs(v, c, p):
    k = 1
    for _v, _id  in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    V[a].append([b, i])
    V[b].append([a, i])
#print(V)
dfs(0, -1, -1)
print(max(C))
for i in C:
    print(i)

Submission status: Accepted

Solution code:


from collections import deque


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

    return n, edges, edge_list


def submit():
    n, edges, edge_list = read_input()

    # node 0からスタートし、bfsで色を塗っていく
    # あるnode xについて、現在のcolor_maxのうち、自身にたどり着いた色以外を用いて、
    # 探索をすすめる
    curr_color_max = -1
    color = {}
    q = deque()
    q.appendleft((0, 0))

    while len(q):
        curr, from_color = q.pop()
        color_count = 1
        for e in edges[curr]:
            key = (min(curr, e), max(curr, e))
            if key in color.keys():
                continue
            else:
                if color_count == from_color:
                    color_count += 1
                if color_count > curr_color_max:
                    curr_color_max = color_count     
                color[key] = color_count
                q.appendleft((e, color_count))
                color_count += 1

    print(curr_color_max)
    for e in edge_list:
        print(color[e])


if __name__ == "__main__":
    submit()

Submission status: Accepted

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


def dfs(v, p, p_col, tree, res):
    col = 1
    for u, id in tree[v - 1]:
        if u == p:
            continue
        if col == p_col:
            col += 1
        res[id] = col
        dfs(u, v, col, tree, res)
        col += 1


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

    ans = [0 for _ in range(n-1)]
    dfs(1, -1, -1, tree, ans)
    print(max(ans))
    print("\n".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
el = defaultdict(lambda :[])
for i in range(n-1):
    a, b = iip()
    el[a-1].append((b-1, i))
    el[b-1].append((a-1, i))

#print(el)

def main():
    color = [None for i in range(n-1)]
    cmax = 0
    que = deque()
    que.append((0, 0))

    while que:
        parent, used_color =que.popleft()
        children = el[parent]
        cn = 1

        for child, edge_num in children:
            el[child].remove((parent, edge_num))

            if cn == used_color:
                cn += 1
            color[edge_num] = cn
            cmax = max(cn, cmax)
            que.append((child, cn))
            
            cn += 1



    print(cmax)
    for i in color:
        print(i)



main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    graph = [set() for _ in range(N+1)]
    for a, b in ab:
        graph[a].add(b)
        graph[b].add(a)

    d = deque()
    d.append(1)

    ans = [-1] * (N+1)

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    print(max(ans))
    print('\n'.join([str(ans[b]) for _, b in ab]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    graph = [set() for _ in range(N+1)]
    for a, b in ab:
        graph[a].add(b)
        graph[b].add(a)

    d = deque()
    d.append(1)

    ans = [-1] * (N+1)

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    print(max(ans))
    for _, b in ab:
        print(ans[b])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
ans = [0] * (n-1)
abi = [[] for _ in range(n+1)]
#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)
for i,(a,b) in enumerate(ab):
    abi[a].append((i,b))
    abi[b].append((i,a))

def dfs(v,parent=-1,color=-1):
    k=1
    for i in abi[v]:
        if parent==i[1]:continue
        if(k==color):k+=1
        ans[i[0]]=k
        k+=1
        dfs(i[1],v,ans[i[0]])

dfs(1)

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

Submission status: Accepted

Solution code:
#146_D
import queue

def swap(x, y):
    if x > y:
        x, y = y, x
    return (x, y)

n = int(input())

edges = [[] for _ in range(n)]
edges_dict = {}
ans = [0 for _ in range(n-1)]
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    edges_dict[(a-1, b-1)] = i
    
k, k_idx = 0, 0
for i in range(n):
    if len(edges[i]) > k:
        k = len(edges[i])
        k_idx = i

que = queue.Queue()
que.put((k_idx, 0))
while not que.empty():
    q, x = que.get()
    tmp = 1
    for to in edges[q]:
        if ans[edges_dict[swap(q, to)]] != 0:
            continue
        if tmp == x:
            tmp += 1
        ans[edges_dict[swap(q, to)]] = tmp
        que.put((to, tmp))
        tmp += 1
            
print(k)
print(*ans, sep= '\n')

Submission status: Accepted

Solution code:
n=int(input())
X=[[] for _ in range(n)]

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

ANS=[0]*(n-1)
VC=[0]*n
k=1
for v,c in enumerate(X):
    t=1
    for b, i in c:
        if VC[v]==t:
            t+=1
        VC[b]=t
        ANS[i]=t
        k=max(k,t)
        t+=1
print(k)
for i in range(n-1):
    print(ANS[i])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
lines = [[] for _ in range(N+1)]
for a, b in ab:
    lines[a].append(b)
    
q = deque([1])
color = [0]*(N+1)
while q:
    x = q.popleft()
    c = 1
    for y in lines[x]:
        if c == color[x]:
            c += 1
        color[y] = c
        c += 1
        q.append(y)
print (max(color))
for i in range(N-1):
    print (color[ab[i][1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
G = None
ans = None

def dfs(v, parent_c=-1, parent_id=-1):
    global G, ans
    k = 1
    for i in range(len(G[v])):
        edge_id, to = G[v][i]['edge_id'], G[v][i]['to']
        if to == parent_id: continue
        if k == parent_c: k+=1
        ans[edge_id] = k
        k += 1
        dfs(to, parent_c=ans[edge_id], parent_id=v)

def main():
    global G, ans
    N = int(input())
    G = [[] for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    for edge_id in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append({'to': b, 'edge_id': edge_id})
        G[b].append({'to': a, 'edge_id': edge_id})
    
    dfs(0)
    print(max(ans))
    for a in ans:
        print(a)

main()

Submission status: Accepted

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

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


# print(ki)


def d(index, color):
    cnt = 1
    for (t, jid) in ki[index]:
        if cnt == color:
            cnt += 1
        ans[jid] = cnt
        d(t, cnt)
        cnt += 1


d(0, 0)
print(max(ans))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
e = [[] for i in range(n)]
num = 0

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

    e[a-1].append([b-1,i])
    e[b-1].append([a-1,i])
    num = max(num,len(e[a-1]),len(e[b-1]))

ans = [-1]*(n-1)

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

while q:
    bef,pn = q.popleft()
    c = 0
    for nex in e[bef]:
        if ans[nex[1]] == -1:
            c += 1
            if c == pn:
                c += 1
            ans[nex[1]] = c
            q.append((nex[0],c))

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
e = [[] for i in range(n)]
num = 0

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

    e[a-1].append([b-1,i])
    e[b-1].append([a-1,i])
    num = max(num,len(e[a-1]),len(e[b-1]))

ans = [-1]*(n-1)

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

while q:
    bef,pn = q.popleft()
    c = 0
    for cn,nex in enumerate(e[bef]):
        if ans[nex[1]] == -1:
            c += 1
            if c == pn:
                c += 1
            ans[nex[1]] = c
            q.append((nex[0],c))

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = int(input())

edge = [tuple(map(int, input().split())) for _ in range(n-1)]
adj = [set() for _ in range(n)]
ans_dict = {}
c_max = 1
for a, b in edge:
    adj[a-1].add(b-1)

que = deque()
c = 1
for l in adj[0]:
    #l is the next vertext, c is the color used.
    que.append([l,c])
    ans_dict[(1,l+1)] = c
    c += 1
c_max = max(c-1, c_max)
while que:
    c = 1
    #new_v is [current vertex, color used to reach the vortex]
    new_v = que.popleft()
    for l in adj[new_v[0]]:
        if c == new_v[1]:
            c += 1
        #l is the next vertex
        que.append([l,c])
        ans_dict[(new_v[0]+1, l+1)] = c
        c += 1
    c_max = max(c-1, c_max)

print(c_max)
for l in edge:
    print(ans_dict[l])

Submission status: Accepted

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

ans = {(-1, 0): -1}
que = {(-1, 0)}
while que:
    queque = set()
    for p, v in que:
        c = 1
        for w in connect[v]:
            if w != p:
                if c == ans[(p, v)]:
                    c += 1
                ans[(v, w)] = c
                queque.add((v, w))
                c += 1
    que = queque
pri = [0] * (n-1)
for i, (a, b) in enumerate(edge):
    a -= 1
    b -= 1
    if (a, b) in ans:
        pri[i] = ans[(a, b)]
    else:
        pri[i] = ans[(b, a)]
print(max(pri))
for x in pri:
    print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for j in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append((b, j))
    e[b].append((a, j))

co = [0]*(n-1)


def dfs(i=0, r=-1, dis=-1):
    global co
    c = 1
    for j in e[i]:
        if j[0] == r:
            continue
        if c == dis:
            c += 1
        co[j[1]] = c
        dfs(j[0], i, c)
        c += 1


dfs()

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