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())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
path = sorted(path, key=lambda x: x[1])
path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())

connect_dic = defaultdict(list)

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

    connect_dic[a].append(b)
    connect_dic[b].append(a)


dq = deque([])
dq.append(a)

color_dic = defaultdict(set)
used_set = set()

comp = defaultdict(int)
max_ = 0

while dq:
    n = dq.popleft()

    can = connect_dic[n]
    l = len(can)
    max_ = max(max_, l)

    a_color = color_dic[n]

    num = 0
    for c in can:
        if c in used_set:
            continue

        while num in a_color:
            num += 1

        color_dic[n].add(num)
        color_dic[c].add(num)
        a_color.add(num)
        comp[(n, c)] = num
        comp[(c, n)] = num

        if c not in used_set:
            dq.append(c)

    used_set.add(n)

print(max_)
for a, b in edge:
    print(comp[(a, b)] + 1)

Submission status: Accepted

Solution code:
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Submission status: Accepted

Solution code:
from queue import deque

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

for i,j in l:
    i,j = i-1,j-1
    li[i].append(j)
    li[j].append(i)

stack = 0
color = [0]*n

work_queue = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
work_queue.append(stack)
path = {}
ma = 0
while work_queue:
    here = work_queue.popleft()
    color = 1
    for i in li[here]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        path[(here,i)] = color
        color_list[i] = color
        ma = max(ma,color)
        color += 1

print(ma)
for i,j in l:
    i,j = i-1,j-1
    print(path[(i,j)])

Submission status: Accepted

Solution code:
from collections import deque 
import sys 
input = sys.stdin.readline 
n=int(input())
child= [[] for _ in range(n)]
edge_order =[]
for i in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1, b-1 
    child[a].append((i,b))
    edge_order.append(b)

queue=deque([0])
color=[0]*n 
while queue:
    v = queue.popleft()
    c = 1
    for i,u in child[v]:
        if c==color[v]:
            c+=1
        color[u]=c
        c+=1
        queue.append(u)
print(max(color))
for i in edge_order:
    print(color[i])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = []
nb = [[] for _ in range(N)]
maxdeg = 0
root = None
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((min(a, b), max(a, b)))
    nb[a].append(b)
    nb[b].append(a)
    if len(nb[a]) > maxdeg:
        maxdeg = len(nb[a])
        root = a
    if len(nb[b]) > maxdeg:
        maxdeg = len(nb[b])
        root = b

colors = {}
for i, x in enumerate(nb[root]):
    colors[x, root] = colors[root, x] = i + 1
    q = deque([(x, root, i + 1)])
    while q:
        node, parent, pcolor = q.popleft()
        colors[node, parent] = colors[parent, node] = pcolor
        color = 0
        for c in nb[node]:
            if c != parent:
                color += 1
                if color == pcolor:
                    color += 1
                q.append((c, node, color))

print(maxdeg)
for a, b in edges:
    print(colors[a, b])

Submission status: Accepted

Solution code:
N = int(input())
edges = []
nb = [[] for _ in range(N)]
maxdeg = 0
root = None
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((min(a, b), max(a, b)))
    nb[a].append(b)
    nb[b].append(a)
    if len(nb[a]) > maxdeg:
        maxdeg = len(nb[a])
        root = a
    if len(nb[b]) > maxdeg:
        maxdeg = len(nb[b])
        root = b

colors = {}
done = [False] * N
done[root] = True
for i, x in enumerate(nb[root]):
    colors[x, root] = colors[root, x] = i + 1
    stack = [(x, root, i + 1)]
    while stack:
        node, parent, pcolor = stack.pop()
        if done[node]:
            continue
        done[node] = True
        colors[node, parent] = colors[parent, node] = pcolor
        color = 0
        for c in nb[node]:
            if c != parent and not done[c]:
                color += 1
                if color == pcolor:
                    color += 1
                stack.append((c, node, color))

print(maxdeg)
for a, b in edges:
    print(colors[a, b])

Submission status: Accepted

Solution code:
from queue import Queue

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

color = {}

# BFS
queue = Queue()
dist = [-1] * n
queue.put((-1, 0))  # (distが等しいノードの中で何番目のノードか, ノード番号)
dist[0] = 0
K = 1

while True:
    num, node = queue.get()
    next_nodes = edges[node]
    tmp_color = 1
    for next_node in next_nodes:
        if dist[next_node] != -1:
            continue
        dist[next_node] = dist[node] + 1

        if tmp_color == num:
            tmp_color += 1
        color[(node, next_node)] = tmp_color
        color[(next_node, node)] = tmp_color
        if tmp_color > K:
            K = tmp_color

        queue.put((tmp_color, next_node))
        tmp_color += 1

    if queue.empty():
        break

print(K)
for edge in edges_original:
    print(color[edge])

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
graph[0] = [0]
edct = {}
par = [-1] * (N+1)
par[1] = 0

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)
    edct[(a, b)] = 0

nmax = 0

for i, g in enumerate(graph[1:], 1):
    nmax = max(nmax, len(g))
    clr = 1
    for j in g:
        if par[j] != -1: continue
        if clr == par[i]:clr += 1
        edct[(min(i, j), max(i, j))] = clr
        par[j] = clr
        clr += 1

print(nmax)
for a, b in ab:
    print(edct[(a, b)])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
child = [[] for _ in range(n)]
edge_order = []
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1 #リストに入れるために数字を1ずつ下げる
    child[a].append((i, b))
    edge_order.append(b)
#aを親として、（辺番号、子ども)この時、aを親に持つ辺はすべてchild[a]に入れられる
queue = deque([0])
color = [0] * n
while queue:
    v = queue.popleft()
    c = 1 #色の初期は位置からスタート
    for i, u in child[v]: #aを親に持つ子頂点すべてを探索する
        if c == color[v]: #親と色が同じとき
            c += 1
        color[u] = c
        c += 1
        queue.append(u)
#子頂点を親頂点としてqueueに突っ込む（a-bとb-aはないのでこれで全探索できる）
print(max(color))
for i in edge_order:
    print(color[i])

Submission status: Accepted

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

data = int(input())

array = [[] for i in range(data)]

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

result = [None]*(data-1)

def func(prt, col):
    cnt = 1
    for cld, org in array[prt]:
        if cnt==col:
            cnt += 1
        result[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

print(max(result))
for i in range(data-1):
    print(result[i])

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:
N = int(input())
E = [[] for _ in range(N)]

#辺の定義
#辺E(u,v)の重みがw
l = []
for i in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)
  l.append((u,v))

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]
ans= {}
#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [0]
color[0] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      tmp = [u,v]
      tmp.sort()
      ans[tuple(tmp)] = color[v]
      i += 1
#各頂点の色を出力
print(max(color))
for a,b in l:
  print(ans[(a,b)])

Submission status: Accepted

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


def main():
    N = int(input())
    g = [[] for _ in range(N)]
    edge_order = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append((i, b))
        edge_order.append(b)
    # 頂点1からBFS
    queue = deque([0])
    color = [0] * N
    while queue:
        v = queue.popleft()
        c = 1  # 色の初期値は一からスタート
        for i, u in g[v]:
            if c == color[v]:  # 親と色が同じ時
                c += 1
            color[u] = c
            c += 1
            queue.append(u)
    print(max(color))
    for i in edge_order:
        print(color[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n = int(input())
#隣接リスト
G = defaultdict(lambda:[])
li = [] #答え用辺を保存するリスト
for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    li.append((a, b))
    G[a].append(b)
    G[b].append(a)
parent = [0]*n #p[i]:頂点iの親
color = [-1]*n #color[i]:頂点iとその子vの色

#深さ優先探索でトポロジカル順序を決める
order = []
def dfs():
    parent[0] = -1
    stack = []
    u = 0
    stack.append(u)
    while stack:
        x = stack.pop()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            parent[v] = x
            stack.append(v)

dfs()

#トポロジカル順序を決めたのでその順番で色を決めて行く
for x in order:
    temp = color[x]
    c = 1
    for y in G[x]:
        if y == parent[x]:
            continue
        if c == temp:
            c += 1
        color[y] = c
        c += 1
        
answer = []
for a, b in li:
    if parent[a] == b:
        answer.append(color[a])
    else:
        answer.append(color[b])

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

Submission status: Accepted

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


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


def dfs(u, c=-1, p=-1):
    k = 1
    for v, i in g[u]:
        if v == p: continue
        if k == c: k += 1
        ans[i] = k
        k += 1
        dfs(v, ans[i], u)


dfs(0)
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

#BFS
from collections import deque, defaultdict
def bfs(G, v, p):
    q=deque()
    q.append((v, p, 0))

    while q:
        #qの先頭を取り出す
        V, P, C = q.popleft()
        next_color = 1 if C != 1 else 2
        for next_v in G[V - 1]:
            if next_v == P:continue
            if next_color == C:next_color += 1

            q.append((next_v, V, next_color))
            color[(V, next_v)] = next_color
            next_color += 1


n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n - 1)]
color = defaultdict(lambda :1)

G = Graph(ab)
#print(G)
color_num = 0
for i in G:
    temp = len(i)
    if temp > color_num:color_num = temp

print(color_num)
bfs(G, 1, -1)

for i in ab:
    print(color[i])

Submission status: Accepted

Solution code:
import sys
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
from collections import deque
l=[0]*(n-1)
q=deque([0])
b=[1]+[0]*(n-1)
while q:
  v=q.pop()
  c=-1
  k=1
  for u,e in g[v]:
    if b[u]: c=l[e]
  for u,e in g[v]:
    if b[u]: continue
    if k==c: k+=1
    l[e]=k
    k+=1
    q.appendleft(u)
    b[u]=1
for c in l: print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
tree=[[] for _ in range(N)]
ans=[-1]*(N-1)
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append((b-1,i))
    tree[b-1].append((a-1,i))
    
def dfs(now,prev=-1,color=0):
    color_num=1
    for i,j in tree[now]:
        if i==prev:
            continue
        if color_num==color:
            color_num=color_num+1
        ans[j]=color_num
        dfs(i,now,color_num)
        color_num=color_num+1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5*2)
n=int(input())
child=[[]for _ in range(n)]
color=[-1]*(n-1)
#adj は(子供,辺番号)
for i in range(n-1):
	a,b=map(int,input().split())
	child[a-1].append((b-1,i))
#x=現在見ている頂点
#r=その頂点の親とその頂点の間のnodeの色
def f(now,parent_node):
	color_num=1
	for i,j in child[now]:
		if color_num==parent_node:
			color_num+=1
		color[j]=color_num 
		f(i,color_num)
		color_num+=1
f(0,0)
print(max(color))
for x in color:
	print(x)

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
            #print(p_col)
            dfs(u, v, col) #u;調べる頂点 v;直前に調べた辺で、調べる頂点と結ばれている頂点　col;直前に調べた辺の色番号
            col += 1 #最深部まで調べたら デフォルトの色=最後に調べた辺の色+1とする
            #最深部に繋がった辺の色+1してやれば、次の辺の色は必ず条件を満たしてくれる

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

Submission status: Accepted

Solution code:
#d3と同一解法
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:
#キューとdictionaryを利用したBFS
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())
g = [[] for _ in range(n)]
ab = []

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

q = deque([0])
par = [0] * n
order = []

while q:
    x = q.pop()
    order.append(x)
    for y in g[x]:
        if y == par[x]:
            continue
        par[y] = x
        q.append(y)

color = [-1] * n
for x in order:
    ng = color[x]
    c = 1
    for y in g[x]:
        if y == par[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

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

k = max(ans)
print(k)
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappop
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

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

def bfs(graph, start, n):
    visited = [-1] * n
    que = deque()
    color = [0] * (n - 1)
    visited[start] = 0
    que.append(start)
    while que:
        node = que.popleft()
        c = 1
        for e in graph[node]:
            if visited[e] < 0:
                if visited[node] == c:
                    c += 1
                visited[e] = c
                color[edge[(e, node)]] = c
                que.append(e)
                c += 1
    return color

r = bfs(graph, 0, n)
ans = max(r)
print(ans)
for k in r:
    print(k)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
g = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append([b, i])
    g[b].append([a, i])
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
def mxmi(a,b):
    if a<b:
        return a,b
    else:
        return b,a
from collections import deque
n = int(input())
tree = [[] for i in range(n)]
color = [0]*(n-1)
d = dict()
for i in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    d[(a-1,b-1)] = i
ans = 0
q = deque([(0,0,0)])
while q:
    cnt = 0
    f = 1
    now,prev,col = q.popleft()
    for node in tree[now]:
        cnt+=1
        if node !=prev:
            if f==col:f+=1
            q.append((node,now,f))
            a,b = mxmi(now,node)
            color[d[(a,b)]] = f
            f+=1
    ans = max(ans,cnt)


ls = list(d.items())
ls.sort(key=lambda x:x[1])
print(ans)
for i in range(n-1):
    print(color[i])

Submission status: Accepted

Solution code:
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 heapq import heapify, heappop, heappush

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

N = INT()
L = [LIST() for i in range(N-1)]
graph = defaultdict(list)
edge = defaultdict(int)

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

K = 0
# 子の数が最大となるものの子の数が，塗れる色の最大値
for v in graph.values():
    K = max(K, len(v))

# this is color pallet
color = list(range(1, K + 1))
# color = [1, ..., K]
q = deque()
q.append((0, None))
while q:
    i, color_from = q.popleft()
    tmp = -1
    # colorの後ろから見れるように
    for node in graph[i]:
        str_ = "{},{}".format(i, node)
        # まだedge辞書になければ
        if not edge[str_]:
            use_color = color[tmp]
            if use_color == color_from:
                # さらに小さい色のやつ
                tmp -= 1
                use_color = color[tmp]
            # 次対策
            tmp -= 1
            edge[str_] = use_color
            edge["{},{}".format(node, i)] = use_color
            q.append((node, use_color))
print(K)
for a, b in L:
    print(edge["{},{}".format(a-1, b-1)])

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)
#template
N = int(input())
li = [0]*(N-1)
dic = {}
graph = [[]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a,b = inputlist()
    if a >= b:
        a,b = b,a
    graph[a].append(b)
    graph[b].append(a)
    k = tuple([a,b])
    dic[k] = i
ans = 0
indexa = -1
seen = [False]*(N+1)
for i in range(1,N+1):
    k = len(graph[i])
    if k > ans:
        indexa = i
    ans = max(ans,k)
def dfs(i,v):
    for v1 in graph[v]:
        if seen[v1]:
            continue
        seen[v1] = True
        i +=1
        i %= ans
        aa = min(v,v1)
        bb = max(v,v1)
        ka = tuple([aa,bb])
        li[dic[ka]] = i
        dfs(i,v1)
dfs(-1,indexa)
print(ans)
for i in range(N-1):
    print(li[i]+1)

Submission status: Accepted

Solution code:
# D - Coloring Edges on Tree
import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

C = {}

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[(node, chi)] = cid
            C[(chi, node)] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[(a,b)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        while(cnt in s[v]):
                cnt+=1
        s[v].add(cnt)
        s[nv].add(cnt)
        dic[tuple(sorted([v,nv]))]=cnt
        dfs(G,nv,v,cnt)
        
N=int(input())
G=[[] for i in range(N)]
e=[]
s=[set() for i in range(N)]
dic={}
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append(sorted([a,b]))
l=0
for i in range(N):
    l=max(l,len(G[i]))
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    print(dic[e[i][0],e[i][1]])

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)
#template
N = int(input())
li = [0]*(N-1)
dic = {}
graph = [[]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a,b = inputlist()
    if a >= b:
        a,b = b,a
    graph[a].append(b)
    graph[b].append(a)
    k = tuple([a,b])
    dic[k] = i
ans = 0
indexa = -1
seen = [False]*(N+1)
for i in range(1,N+1):
    k = len(graph[i])
    if k > ans:
        indexa = i
    ans = max(ans,k)
def dfs(i,v):
    for v1 in graph[v]:
        if seen[v1]:
            continue
        seen[v1] = True
        i +=1
        i %= ans
        aa = min(v,v1)
        bb = max(v,v1)
        ka = tuple([aa,bb])
        li[dic[ka]] = i
        dfs(i,v1)
dfs(-1,indexa)
print(ans)
for i in range(N-1):
    print(li[i]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dic[str(v)+'t'+str(nv)]=cnt
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dic={}
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    if str(e[i][0])+'t'+str(e[i][1]) in dic:
        print(dic[str(e[i][0])+'t'+str(e[i][1])])
    else:
        print(dic[str(e[i][1])+'t'+str(e[i][0])])

Submission status: Accepted

Solution code:
N = int(input())
vert = [0 for _ in range(N - 1)]
D = {}
E = {i: [i] for i in range(N)}
F = {i: [] for i in range(N)}
for i in range(N - 1):
  a, b = map(int, input().split())
  D[(a-1)*N+b-1], D[(b-1)*N+a-1] = i, i
  E[a-1].append(b-1)
  E[a-1][0] += N
  E[b-1].append(a-1)
  E[b-1][0] += N
m = max(E[i][0] for i in E)
K = m // N
par = [-1 for _ in range(N)]
root = m % N
par[root] = N + 1
p = [root]
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in range(1, E[p[i]][0] // N + 1):
      tmp = E[p[i]][j]
      if par[tmp] == -1:
        par[tmp] = p[i]
        F[p[i]].append(tmp)
        cnt += 1
        p.append(tmp)
  pnt = n
q = [root]
t = 1
m = -1
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    t = 1
    if par[q[i]] != N + 1:
      m = vert[D[q[i]*N+par[q[i]]]]
    for j in F[q[i]]:
      if t == m:
        t += 1
      vert[D[j*N+q[i]]] = t
      q.append(j)
      t += 1
      cnt += 1
  pnt = n
print(K)
for i in range(N-1):
  print(vert[i])

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = mylistinput(n-1)

g = [ [] for _ in range(n) ]
for i in range(n-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

color = [-1] * n

def bfs(g):
    used_color = [ [-1] ]*n
    q = deque()
    q.append([0,0])
    while q:
        tmp = q.popleft()
        v = tmp[0]
        c = tmp[1]
        color[v] = c
        ls_nc = list(reversed(list(range(1,len(g[v])+1))))
        if c==0:
            pass
        elif c in ls_nc:
            ls_nc.remove(c)
        else:
            pass
        for nv in g[v]:
            if color[nv]!=-1:
                pass
            else:
                nc = ls_nc.pop()
                q.append([nv,nc])
    return True

if bfs(g):
    print(max(color))
    for i in range(n-1):
        b = ab[i][1] - 1
        print(color[b])
else:
    print("Error")

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for node in path[pre]:
            if visited[node]:
                continue
            if c == k:
                k += 1
            visited[node] = True
            ans[(pre, node)] = k
            que.append((node, k))
            k += 1

    print(max(ans.values()))
    print('\n'.join([str(ans[key]) for key in ab]))

if __name__ == '__main__':
    main()