Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
#隣接リスト
adjacent_list = [[] for i in range(n+1)]
#入力されたデータを保存しておくやつ
data = [None] * (n - 1)
#最終的に色を入れておくやつ。
#edgedata[(1,2)] => 1->2の辺の色を入れておく
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data[i] = [a, b]
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#つながってるノードが一番多いやつを保存しておく
max_node = 0
#探索が終わったやつを入れる
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i
#kには色の種類を入れる
k = len(adjacent_list[max_node])
#print("k => {}".format(k))
def dfs(node, num):
    #隣接リストの中身を、つながってるノード順にソート
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    #さっきつかったいろは使わないようにする
    color_list = [i for i in range(1,len(node_list) + 2) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        #まだ見てなかったら、dfsを掛ける
        if i not in finished:
            #小さいほうから大きいほうに文字を並べ、ハッシュに値を保存
            #print("{}".format(color_list))
            #print("c_i =>{}  node =>{}".format(c_i,node))
            edgedata[(min(node, i), max(node, i))] = color_list[c_i]
            #color_list[c_i]は使ったので、使った色として引数で渡す。
            dfs(i, color_list[c_i])
            #この色は使ったから、一個ずらす
            c_i += 1
#一番のノードを根とし、dfsをかける
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])
#output k

Submission status: Accepted

Solution code:
def d_coloring_edges_on_tree():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    # tree[a][b]: 頂点 a-b 間を結ぶ辺は何色で塗られているか
    tree = {i: dict() for i in range(N)}
    for a, b in Edges:
        tree[a - 1][b - 1] = -1
        tree[b - 1][a - 1] = -1

    k = max(len(tree[a]) for a in range(N))  # k (最大次数) 色で辺を塗れる
    used_color = [-1] * N
    used_color[0] = k - 1

    q = deque([0])
    while q:
        current = q.pop()
        color_current = used_color[current]  # ここで色は0オリジンとする
        for child in tree[current].keys():
            if used_color[child] != -1:
                continue  # もう塗っていた (current の親だった)
            color_current = (color_current + 1) % k
            tree[current][child] = color_current
            tree[child][current] = color_current
            used_color[child] = color_current
            q.appendleft(child)

    ans = [k] + [tree[a - 1][b - 1] + 1 for a, b in Edges]
    return ' '.join(map(str, ans))

print(d_coloring_edges_on_tree())

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

A = [0] * (N - 1)
Q = deque([1])
while Q:
    p, v = divmod(Q.popleft(), N + 1)
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append(c * (N + 1) + u)
        A[i] = c

print(max(A))
print("\n".join(map(str, A)))

Submission status: Accepted

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        t = 1
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

A = [0] * (N - 1)
Q = deque([(0, 1)])
while Q:
    p, v = Q.popleft()
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[i] = c

print(max(A), *A)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys
 
n = int(sys.stdin.readline().strip())
adj = [set() for _ in range(n)]
colors = dict()
edges = []
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    edges.append([a, b])
 
col = max(len(v) for v in adj)
 
s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break
 
Q = [[s, -1, -1]]
while Q:
    cur, prev, prev_color = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == prev_color:
            c += 1
        colors[min(cur, nex)*n + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in edges:
    print(colors[a*n + b])

Submission status: Accepted

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)

queue = deque()
queue.append(0)

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

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        k = max(k,c+1)
        c += 1
        queue.append(adj)
print(k)

for e in edge:
    print(color[e[1]-1]+1)

Submission status: Accepted

Solution code:
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
k = max(map(len, con))
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex==0 or ex==k)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
print(k)
for a, b in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k if t > k else t)

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[i] = c

print(K)
for a in A:
    print(a)

Submission status: Accepted

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)

queue = deque()
queue.append(0)

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

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        k = max(k,c+1)
        c += 1
        queue.append(adj)
print(k)

for e in edge:
    print(color[e[1]-1]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

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

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

color = max(len(g) for g in G)
print(color)

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

def dfs(v=1, p=0, p_col=-1):
    col = 1

    for side, idx in G[v]:
        if side != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(side, v, col)
            col += 1

dfs()
print("\n".join(map(str, ans)))

Submission status: Accepted

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

n = int(input())

edges = [[] for _ 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


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

q = deque([(0,0)])
visited[0] = True

mx = 0
while q:
    key,v = q.popleft()
    i = 1
    for x in edges[v]:
        if not visited[x]:
            if key != i:
                visited[x] = True
                ans[l[(v,x)]]=i
                q.append((i,x))
                mx = max(mx,i)
                i += 1
            else:
                visited[x] = True
                i += 1
                ans[l[(v,x)]]=i
                q.append((i,x))
                mx = max(mx,i)
                i += 1

print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

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

tree = [[] for _ in range(N)]
for n, (i, j) in enumerate(X):
    tree[i - 1].append((n, j - 1))

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

while len(q) > 0:
    # u: node number, c: color
    u, c = q.popleft()
    
    cnt = 1
    for i, (n, v) in enumerate(tree[u]):
        if cnt == c:
            cnt += 1

        ans[n] = cnt
        q.append((v, cnt))
        cnt += 1
        
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u, i in E[v]:
        E[u].remove((v, i))
        c = next(C)
        Q.append((c, u))
        A[i] = c

print(K)
for a in A:
    print(a)

Submission status: Accepted

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

n = int(input())

edges = [[] for _ 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

ans = [0]*(n-1)

visited = [-1]*n
q = deque([0])
visited[0] = 0

while q:
    v = q.popleft()
    i = 1
    for x in edges[v]:
        if visited[x] < 0:
            if i == visited[v]:
                i += 1
            visited[x] = i
            ans[l[(v,x)]] = i
            q.append(x)
            i += 1

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

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add(b)
    E[b].add(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

K = max(len(e) for e in E)

A = [0] * (N - 1)

Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u in E[v]:
        E[u].remove(v)
        c = next(C)
        Q.append((c, u))
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

Submission status: Accepted

Solution code:
from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  color[(a, b)] = 0
for a in range(N):
  c_p = color_parents[a]
  c = 1
  for b in tree[a]:
    if c == c_p:
      c += 1
    color[(a, b)] = c
    color_parents[b] = c
    c += 1
print(max(color.values()))
for k in color.keys():
  print(color[k])

Submission status: Accepted

Solution code:
N = int(input())

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    if a >= len(nodes):
        exit()
    if b >= len(nodes):
        exit()
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
if nodes is None:
    exit()

for i, links in enumerate(nodes):
    if links is None:
        exit()
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, edge, queue):
    while len(queue) > 0:
        ni, pc = queue.pop(0)
        links = nodes[ni]

        c = 1
        if pc == c:
            c += 1

        if links is None:
            exit()

        next_links = []
        for n, i in links:
            if n < 0 or i < 0:
                exit()
            if n >= len(nodes) or i >= len(edge):
                exit()

            if edge[i] != 0:
                continue
            edge[i] = c
            queue.append((n, c))

            c += 1
            if pc == c:
                c += 1

queue = [(max_i, 0)]    
fill(nodes, edge, queue)

print(max_l)
for e in edge:
    print(e)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
d=[]
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
    d+=(a-1,b-1),
s=[(0,0)]
f=[1]+[0]*n
dic=dict()
while s:
    v,color=s.pop()
    i=0
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        i+=1
        if i==color:i+=1
        s+=(w,i),
        dic[v,w]=i
ans=[]
for a,b in d:
    if (a,b)in dic:
        ans+=dic[a,b],
    else:
        ans+=dic[b,a],
print(max(ans))
for t in ans:print(t)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(succs, preds, start):
    saisyoku = {}
    queue = deque([start])
    used = 0
    while queue:
        v = queue.popleft()
        for u in preds[v]:
            used = saisyoku[preds[v][u]]
        c = 1
        for w in succs[v]:
            if used and c == used:
                c += 1
            saisyoku[succs[v][w]] = c
            queue.append(w)
            c += 1
    return saisyoku
  
n = int(input())
vertices = range(1, n+1)
edges = [list(map(int, input().split())) for _ in range(n-1)]
jisu = {v: 0 for v in vertices}
succs = {v: {} for v in vertices}
preds = {v: {} for v in vertices}
for i, (u, v) in enumerate(edges):
  succs[u][v] = i
  preds[v][u] = i
  jisu[u] += 1
  jisu[v] += 1
colors = max(jisu.values())
print(colors)
saisyoku = bfs(succs, preds, 1)
for _, c in sorted(saisyoku.items()):
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    #treeに(繋がっている頂点, 辺の番号)を加える
    tree[a-1].append((b-1,i))
    tree[b-1].append((a-1,i))
ans = [0]*N #それぞれの辺に対する答え
q = deque()
q.append((0,0))
ma = 0  #最大の値、１行目
while q:    #これ以下を書けるように、bfsの典型
    ape1, color1 = q.popleft()    #親
    color2 = 1
    for ape2, h in tree[ape1]:  #子
        if ans[h] != 0: #既に値がある=親ならスキップ
            continue
        if color1 == color2:    #親と同じ色なら+1
            color2 += 1
        ans[h] = color2
        q.append((ape2,color2))
        ma = max(ma,color2)
        color2 += 1
print(ma)
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
ansdict = {}
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			ansdict[(i,j)] = kk 
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(ansdict[(ai-1,bi-1)])

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
from queue import Queue
G = defaultdict(list)

C = Counter()
N = int(input())
ans = {}
o = []
for i in range(N-1):
    a, b = map(int, input().split())
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

cs = [0] * (N+1)
def bfs(v):
    ret = 0
    visited = set()
    q = Queue()
    visited.add(v)
    q.put(v)
    while not q.empty():
        v = q.get()
        counter = 1
        for c in G[v]:
            if not c in visited:
                visited.add(c)
                if counter == cs[v]:
                    counter += 1
                cs[c] = ans[(c,v)] = ans[(v,c)] = counter
                counter += 1
                q.put(c)

bfs(1)
print(C.most_common(1)[0][1])
for a,b in o:
    print(ans[(a,b)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N=input()

al=[ [] for i in range(N+1) ]
Q=[]    #クエリー
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
    Q.append((a,b))

K=0
start=None
for i,t in enumerate(al):
    K=max(K,len(t))
    if start is None and len(t)==1:
        start=i

edge={} #辺集合 (fro,to):色

#BFS
Visit=[ 0 for _ in range(N+1) ] #訪問した頂点
q=deque()
q.append(start)
Visit[start]=1
used=[ None for _ in range(N+1) ] #前の頂点との間で使用済みの色をセットする配列

while q:
    fro=q.popleft()
    for color in range(1,K+1):  #未使用の色番号で最小の番号をcolor変数にセットする
        if used[fro]!=color:
            break

    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	#ここで訪問済みVisitに1をセットする。popleftの直後でVisitをセットすると同じ頂点がqに入り、TLEする
            q.append(to)
            edge[(fro,to)]=color
            edge[(to,fro)]=color
            used[to]=color
            color+=1
            if used[fro]==color:    #次に使おうとした色が前の頂点との間で使用済みであれば、色番号を１ずらす
                color+=1

print K
for a,b in Q:
    print edge[(a,b)]

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(100000)
i8 = np.int64
i4 = np.int32


def solve(i, prev, prevc, t, d, ans):
    num = len(t[i])
    x = 1
    if prevc == 1:
        x = 2
    for c in t[i]:
        if c == prev:
            continue
        ans[d[(i, c)]] = x
        num = max(num, solve(c, i, x, t, d, ans))
        x += 1
        if x == prevc:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = {}
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
        d[(a - 1, b - 1)] = count
        d[(b - 1, a - 1)] = count
        count += 1
    num = solve(0, -1, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)

main()

Submission status: Accepted

Solution code:
N = int(input())
tree = {}
ans = [0 for _ in range(N - 1)]

for i in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree.setdefault(a, []).append(i)
    tree.setdefault(b, []).append(i)
for k, v in tree.items():
    a = set(range(1, len(v)+1))
    b = set([ans[i] for i in v])
    if 0 in b:
        b.remove(0)
    a = list(a - b)
    c = 0
    for i in v:
        if ans[i] == 0:
            ans[i] = a[c]
            c += 1
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

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


n = int(input())
routes = []
dic = [{}] * n
edges = [[]for _ in range(n)]
used = [0]*n

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

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        dic[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(dic[_from][to])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N=input()

al=[ [] for i in range(N+1) ]
Q=[]    #クエリー
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
    Q.append((a,b))

K=0
start=None
for i,t in enumerate(al):
    K=max(K,len(t))
    if start is None and len(t)==1:
        start=i

edge={} #辺集合 (fro,to):色

#BFS
Visit=[ 0 for _ in range(N+1) ] #訪問した頂点
q=deque()
q.append(start)
Visit[start]=1
used=[ None for _ in range(N+1) ] #前の頂点との間で使用済みのカラー

while q:
    fro=q.popleft()
    for color in range(1,K+1):
        if used[fro]!=color:
            break

    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	#ここで訪問済みVisitに1をセットする。4行上のpopleftの直後でVisitをセットすると同じ頂点がqに入り、TLEする
            q.append(to)
            edge[(fro,to)]=color
            edge[(to,fro)]=color
            used[to]=color
            color+=1
            if used[fro]==color:
                color+=1

print K
for a,b in Q:
    print edge[(a,b)]

Submission status: Accepted

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

N = int(input())
ad = [[] for _ in range(N)]
edge = []
# 0からn-1の値をとる木構造を管理する。
for _ in range(N-1):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append(b)
    ad[b].append(a)
    edge.append((a, b))

K = max(len(S) for S in ad)
d = dict()

def dfs(v=0, pv=-1, memo=-1):
    color = 0
    for nv in ad[v]:
        if nv == pv:
            continue
        if color == memo:
            color += 1
        d[(v, nv)] = color
        d[(nv, v)] = color
        dfs(nv, v, color)
        color += 1

dfs()

print(K)
for e in edge:
    print(d[e]+1)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
q = deque([(-1, 1)])
visited = {i: False for i in range(1, N+1)}
while q:
    p, v = q.popleft()
    visited[v] = True
    if p == -1:
        used = -1
    else:
        used = edge_color[edge_idx[(p, v)]] if p < v else edge_color[edge_idx[(v, p)]]
    c = 1
    for u in E[v]:
        if visited[u]: continue
        q.append((v, u))
        if c == used: c += 1
        if u < v:
            edge_color[edge_idx[(u, v)]] = c
        else:
            edge_color[edge_idx[(v, u)]] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)
 
 
def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color
 
    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color
 
 
print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for i in range(N)]
ans = [-1] * (N - 1)
lines = []

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

q = [(0, 0,)]
max_color = 0
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for nv, i in edges[v]:
        ans[i] = color
        q.append((nv, color,))
        color += 1
        if c == color:
            color += 1

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

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == "__main__":
	N = int(input())
	AB = []
	for _ in range(N - 1):
		a, b = map(int, input().split())
		AB.append((a, b))

	graph = [[] 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]
	# make ordered tree
	while stack:
		x = stack.pop()
		order.append(x)
		for y in graph[x]:
			if parent[x] == y:
				continue
			parent[y] = x
			stack.append(y)

	# assign color
	color = [-1] * (N + 1)
	for x in order:
		ng = color[x] # cannot assign the color of edge(x, parent[x])
		c = 1
		for y in graph[x]:
			if parent[x] == y:
				continue
			if c == ng:
				c += 1
			color[y] = c
			c += 1

	answer = []
	for a, b in AB:
		if parent[a] == b:
			answer.append(color[a])
		else:
			answer.append(color[b])
	K = max(answer)
	print(K)
	print('\n'.join(map(str, answer)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
# anslist = [[0]*N for i in range(N)]
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(Kpre[bi-1])

Submission status: Accepted

Solution code:
from collections import deque


def solve(n, a_list, b_list):

    # create graph
    g = {i: dict() for i in range(n)}
    for i in range(n - 1):
        a, b = a_list[i] - 1, b_list[i] - 1
        g[a][b] = -1
        g[b][a] = -1

    k = max([len(g[a]) for a in range(n)])

    used_color = [-1] * n
    used_color[0] = k - 1
    # BFS
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        c = used_color[p]
        for q in g[p].keys():
            if used_color[q] != -1:
                continue
            c += 1
            c %= k
            # print(p, q, c)
            g[p][q] = c
            g[q][p] = c
            used_color[q] = c
            queue.append(q)

    res_list = [0] * (n - 1)
    for i in range(n - 1):
        res_list[i] = g[a_list[i] - 1][b_list[i] - 1] + 1

    return k, res_list


def main():
    n = int(input())
    a_list = [0] * (n - 1)
    b_list = [0] * (n - 1)
    for i in range(n - 1):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b

    k, res_list = solve(n, a_list, b_list)
    print(k)
    for i in range(n - 1):
        print(res_list[i])


def test():
    print(solve(3, [1, 2], [2, 3]))
    print(solve(8, [1, 2, 2, 2, 4, 5, 6], [2, 3, 4, 5, 7, 6, 8]))


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
 
N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
    V[a].add(b)
    V[b].add(a)
#print(V)
maxc = 0
for v in V:
    maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
    CE[e] = 0
#print(CE)
 
def dfs(u,t,c):
    if t > 0:
        CE[(min(u,t),max(u,t))] = c
    cc = c+1
    if cc > maxc:
        cc = 1
    for v in V[u]:
        if CE[(min(u,v),max(u,v))] == 0:
            dfs(v,u,cc)
            cc += 1
            if cc > maxc:
                cc = 1
dfs(1,0,1)
print(maxc)
for e in E:
    print(CE[e])

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    from collections import defaultdict
    num_c = defaultdict(int)
    E = defaultdict(lambda:defaultdict(int))
    inputE = []
    for i in range(N-1):
        ai,bi = LMIIS()
        if bi < ai:
            ai,bi = bi,ai
        num_c[ai] += 1
        num_c[bi] += 1
        E[ai][bi]= -1
        inputE.append((ai,bi))
    max_c = max(num_c.values())
    


    def colour(e1,c):
        tmpc = 0
        for e2 in E[e1].keys():
            tmpc += 1
            if tmpc == c:
                tmpc += 1
            E[e1][e2] = tmpc
            colour(e2,tmpc)

            
        pass
    
    colour(1,0)
    # print(E)
    print(max_c)


    for ai,bi in inputE:
        if E[ai][bi] != -1:
            print(E[ai][bi])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
#K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)