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 bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI_()
        G[a].append((b, i))
        G[b].append((a, i))

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

    def dfs(c, color_p):
        visited[c] = True
        color = 0
        for n, i in G[c]:
            if not visited[n]:
                if color == color_p:
                    color += 1
                ans[i] = color
                dfs(n, color)
                color += 1

    dfs(0, -1)

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
ab=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a].append([b,i])
que=deque()
que.append(1)
visited=[0]*(n)
ans=[0]*(n-1)
while que:
    x=que.popleft()
    k=1
    for j in ab[x]:
        if visited[x-1]!=k:
            ans[j[1]]+=k
            visited[j[0]-1]+=k
            k+=1
            que.append(j[0])
        else:
            ans[j[1]]+=(k+1)
            visited[j[0]-1]+=(k+1)
            k+=2
            que.append(j[0])
print(max(ans))
for l in ans:
    print(l)

Submission status: Accepted

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

n = int(input())

ab = []
adj = [[] * (n+1) for _ in range(n+1)]

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

m = [0] * (n+1)
for a, b in ab:
    m[a] += 1
    m[b] += 1

k = max(m)
print(k)

visited = [False] * (n+1)
label = [(0, 0)] * (n+1)

j = m.index(k)

q = deque([j])
visited[j] = True
while len(q) > 0:
    v = q.popleft()
    l = 0
    for w in adj[v]:
        if not visited[w]:
            l += 1
            if label[v][1] == l:
                l += 1
            label[w] = (v, l)
            visited[w] = True
            q.append(w)

#print(adj)

for a, b in ab:
    if label[a][0] == b:
        print(label[a][1])
    else:
        print(label[b][1])

Submission status: Accepted

Solution code:
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = {}
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[(prev, num)]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        if (a, b) in color.keys():
            continue
        else:
            if count == col:
                color[(a, b)] = count + 1
                count += 2
            else:
                color[(a, b)] = count
                count += 1
            queue.append((i, num))
print(max([len(graph[i]) for i in range(n + 1)]))
for i, j in edge:
    print(color[(i, j)])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

N = int(input())
ad = [[] for i in range(N+1)]

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

ans_max = 0
for i in range(1,N+1):
    ans_max = max(ans_max, len(ad[i]))

print(ans_max)

visited = [0 for i in range(N+1)]
seen = [0 for i in range(N+1)]
edge_color = defaultdict(int)
node_color = [0 for i in range(N+1)]

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    node_color[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        c = 1
        for w in ad[v]:
            if seen[w] == 0:
                stack.append(w)
                if c != node_color[v]:
                    edge_color[(v, w)] = c
                    node_color[w] = c
                else:
                    c += 1
                    edge_color[(v, w)] = c
                    node_color[w] = c
                c += 1
                seen[w] = 1

        if stack == []: break

bfs(1)

for edge in edges:
    if edge_color[edge] != 0:
        print(edge_color[edge])
    else:
        print(edge_color[edge.reverse()])

Submission status: Accepted

Solution code:
N = int(input())
ad = {}
status = {}
edge=[]

for n in range(N):
    ad[n+1]=set([])
    status[n+1] = -1
    
for n in range(N-1):
    a,b = list(map(int,input().split()))
    edge.append((a,b))
    ad[a].add(b)
    ad[b].add(a)
    
color = set([])
parent = [0] * (N+1) 
ans={}

#BFS
from collections import deque

start = 1
status[start] = 0
que = deque([start])

while len(que) > 0:
    start = que[0]
#     print(start,parent[start])
    c = 1
    for v in ad[start]:
        if status[v] == -1:
            que.append(v)
            status[v]=0
            if parent[start] == c:
                c += 1
            parent[v] = c
            color.add(c)
            
            s = min(start,v)
            e = max(start,v)
            
            ans[s,e]=c
            
            c+=1
            
#     print(parent,que)
    que.popleft()

print(len(color))
for e in edge:
    print(ans[e])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
edge = []
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  edge.append((a,b))
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
ans = {}
while Q:
  temp = Q.popleft()
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now == col[temp]:
      now += 1
    col[n] = now
    ans[min(temp,n),max(temp,n)] = now
    now += 1
    Q.append(n)
    
print(m)
for a,b in edge:
  print(ans[(a,b)])

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, ABs):
    tree_top = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        tree_top[ABs[i][0]].append(i)
        tree_top[ABs[i][1]].append(i)

    max_color = 0
    for tt in tree_top:
        max_color = max(max_color, len(tt))

    ans = [0 for _ in range(N - 1)]
    for tt in tree_top:
        colored = []
        for i in tt:
            if ans[i] != 0:
                colored.append(ans[i])
        colored.sort()
        now_color = 1
        colored_point = 0
        for i in tt:
            if ans[i] != 0:
                continue
            if colored_point < len(colored) \
                    and now_color == colored[colored_point]:
                now_color += 1
                colored_point += 1
            ans[i] = now_color
            now_color += 1

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


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    ABs = [[int(i) for i in input().split()] for _ in range(N - 1)]
    solve(N, ABs)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    tree = [[] for  _ in range(N)]
    abs = []
    for _ in range(N-1):
        a, b = read_ints()
        a -= 1
        b -= 1
        abs.append((a, b))
        tree[a].append(b)
    Q = [(0, -1)]
    colors = {}
    color_count = 0
    while Q:
        node, color = Q.pop()
        c = 1
        for child in tree[node]:
            if color == c:
                c += 1
            colors[(node, child)] = c
            Q.append((child, c))
            color_count = max(color_count, c)
            c += 1
    print(color_count)
    for ab in abs:
        print(colors[ab])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
G = [[] for _ in range(n + 1)]
G_order = []
# a<bが保証されている、aを親、bを子とする
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append(b)
    G_order.append(b)

# どこでも良いが、ここでは0をrootとする
que = deque([0])

# 各頂点と「親」を結ぶ辺の色
# 頂点0をrootとするのでC[0]=0で確定, 他を調べる
colors = [0] * n

while que:
    # prt = 親
    # 幅優先探索
    prt = que.popleft()
    color = 0

    # cld = 子
    for cld in G[prt]:
        color += 1
        # 「今考えている頂点とその親を結ぶ辺の色」と同じ色は使えない
        if color == colors[prt]:
            color += 1
        colors[cld] = color
        que.append(cld)

# それぞれの頂点とその親を結ぶ辺の色
# print(colors)

# 必要な最小の色数
print(max(colors))

# 辺の番号順に色を出力
for i in G_order:
    print(colors[i])

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
sys.setrecursionlimit(1000000)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p, prev):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		if now == prev:
			now = (now+1)%mx
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u, col[edges[i, u]])

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0,-1)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
sys.setrecursionlimit(1000000)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p, prev):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		if now == prev:
			now = (now+1)%mx
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u, col[edges[i, u]])

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0,-1)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
g = [[] for _ in range(n)] #隣接リスト
ab = []
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    ab.append((a,b))
    g[a].append(b)
    g[b].append(a)

root = 0
parent = [0]*n
deq = deque([root])
order = [root]

color = [-1]*n
deq = deque([root])
while deq:
    fr = deq.pop()
    ng = color[fr]
    c = 0
    for go in g[fr]:
        if go == parent[fr]:
            continue
        if c == ng:
            c += 1
        parent[go] = fr
        color[go] = c
        c += 1
        deq.append(go)
        order.append(go)
rank = [0]*n
for i,j in enumerate(order):
    rank[j] = i
print(max(color)+1)
for a,b in ab:
    if rank[a] < rank[b]:
        print(color[b]+1)
    else:
        print(color[a]+1)

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 + 1)]
for i, (a, b) in enumerate(X):
    tree[a].append((b, i))
    tree[b].append((a, i))

color = [0] * (N - 1)
nodes = [set() for _ in range(N + 1)]
visited = [False] * (N + 1)

q = deque([1])
visited[1] = True
while q:
    u = q.popleft()
    c = 1
    for v, i in tree[u]:
        if visited[v]:
            continue

        while c in nodes[v] or c in nodes[u]:
            c += 1
        color[i] = c
        nodes[u].add(c)
        nodes[v].add(c)
        visited[v] = True
        q.append(v)

print(max(len(v) for v in tree))
print(*color, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

M=max(F)

C=[0]*(N-1)
G=[set() for _ in range(N+1)]
A=[-1]*(N+1)

T={i:False for i in range(1,N+1)}
T[1]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    y=1
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)
            
            p,q=min(v,w),max(v,w)

            c=(A[v]+y)%M
            
            A[w]=c
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)
            y+=1

print(max(C)+1)
print("\n".join(map(lambda x:str(x+1),C)))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
edges=[[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edges[a].append((b, i))
    edges[b].append((a, i))

next_set = deque([(0,0)])
colors = [0]*(N-1)
while next_set:
    p, i = next_set.popleft()
    cnt = 1 if colors[i] != 1 else 2
    for q, j in edges[p]:
        if colors[j] != 0:
            continue
        colors[j] = cnt
        cnt += 1
        if cnt == colors[i]:
            cnt += 1
        next_set.append((q, j))
print(max(colors))
print(*colors, sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()

#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print(ans[key])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

g = [[] for _ in range(N)]
deg = [0] * N
ab = defaultdict(int)

for _ in range(N - 1):
    a, b = map(int1, readline().split())
    g[a].append(b)
    g[b].append(a)
    deg[a] += 1
    deg[b] += 1
    ab[(a, b)] = -1

color = [-1] * N

print(max(deg))

C = [0] * N
C[0] = -1

que = deque([0])

while len(que) != 0:
    idx = que.popleft()
    tmp = 1
    for i in g[idx]:
        if C[i] != 0:
            continue
        a, b = idx, i
        if tmp == C[idx]:
            tmp += 1
        ab[(a, b)] = tmp
        C[i] = tmp
        que.append(i)
        tmp += 1

for v in ab.values():
    print(v)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    side = []
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
        side.append([a,b])
    I = collections.defaultdict(lambda : 0)
    k = 0
    for i in edge:
        k = max(k,len(i))
    print(k)
    color = [INF]*(n)
    d = [INF]*(n)
    d[0] = 0
    q = collections.deque([0])
    while q:
        p = q.popleft()
        color_num = 1
        for v in edge[p]:
            if d[v] == INF:
                q.append(v)
                d[v] = d[p] + 1
                if color_num == color[p]:
                    color_num+=1
                color[v] = color_num
                I[(p,v)] = color_num
                I[(v,p)] = color_num
                color_num+=1
    for i,j in side:
        print(I[(i,j)])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
E = [[] for _ in range(N)]
  
for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  # 出力のために、何番目のEdgeだったかを保有させる必要がある
  E[a].append([i,b])
  E[b].append([i,a])
  
k = 0
for e in E:
  k = max(k, len(e))
print(k)


def bfs():
  colors = [-1 for _ in range(N-1)]
  visited = [False for _ in range(N)]
  d = deque()
  d.append([0,-1])
  while d:
    now,edge_color = d.pop()
    visited[now] = True
    cand_color = 1
    for i, nxt in E[now]:
      #print(i, nxt, visited[i], colors[i])
      if visited[nxt]:
        continue # TreeでBFSだとここは通らない・・・？
      if colors[i] > -1:
        assert("１エッジに２色塗ろうとする・・・？")
        continue
      if cand_color == edge_color:
        cand_color += 1
      colors[i] = cand_color
      d.append([nxt, colors[i]])
      cand_color += 1
  return colors

colors = bfs()

for i in range(len(colors)):
  print(colors[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10010010)

def abc146_d():
    n = int(input())
    Q = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]

    deg = [0] * n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1: nouse = color[(min(s, p), max(s, p))]
        c = 1
        for t in adj[s]:
            if t == p: continue
            if c == nouse: c += 1
            color[(min(s, t), max(s, t))] = c
            dfs(t, s)
            c += 1

    dfs(1, -1)

    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

if __name__ == '__main__':
    abc146_d()

Submission status: Accepted

Solution code:
import queue
n=int(input())
cf=[0]*n
cg=[0]*(n-1)
ce=[[] for _ in range(n)]
e=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
  ce[a-1]+=[i]
  ce[b-1]+=[i]
k=len(max(e,key=len))
q=queue.Queue()
q.put(0)
while not q.empty():
  now=q.get()
  cf[now]=1
  c=0
  for i in ce[now]:
    if cg[i]:c=cg[i]
  j=1
  for i in ce[now]:
    if j==c:j+=1
    if cg[i]:continue
    cg[i]=j
    j+=1
  for i in e[now]:  
    if cf[i]:continue
    q.put(i)
print(k)
for i in cg:
  print(i)

Submission status: Accepted

Solution code:
n=int(input())
e=[[] for i in range(n)]
for i in range(n-1):
  inp=list(map(int,input().split()))
  e[inp[0]-1].append((inp[1]-1,i))
  e[inp[1]-1].append((inp[0]-1,i))

col=[0 for i in range(n-1)]
fl=[0 for i in range(n)]
s=[[0,0]]
mc=0
while len(s):
  ns=[]
  for i in s:
    fl[i[0]]=1
    cc=1
    for j in e[i[0]]:
      if not(fl[j[0]]):
        if cc==i[1]:
          cc+=1
        col[j[1]]=cc
        mc=max(mc,cc)
        ns.append([j[0],cc])
        cc+=1
  s=ns

print(mc)
for i in col:
  print(i)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
u=[0]*n
q=[(0,0)]
while q:
  v,s=q.pop()
  u[v]=1
  t=1
  for c,i in g[v]:
    if u[c]: continue
    if t==s: t+=1
    l[i]=t
    q+=[(c,t)]
    t+=1
print(max(l))
for i in l: print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
def dfs(v,p=-1,s=-1):
  t=1
  for c,i in g[v]:
    if c==p: continue
    if t==s: t+=1
    l[i]=t
    dfs(c,v,t)
    t+=1
dfs(0)
print(max(l))
for i in l: print(i)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col = [0]*(n-1)
visited = [0]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(not visited[next_v[1]]):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            c+=1
            visited[next_v[1]] = 1
            que.append(next_v)
print(max(col))
for i in col:
    print(i)

Submission status: Accepted

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

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

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

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    g = {}
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append((b-1, i))
        g.setdefault(b-1, [])
        g[b-1].append((a-1, i))
        
    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        color = 1 if prevcol != 1 else 2
        for nxt, colidx in g[node]:
            if colors[colidx] is None:
                colors[colidx] = color
                nodes.append((color, nxt))
                color += 1 if prevcol != color+1 else 2

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



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    g = {}
    edges_to_idx = {}
    edges = []
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges_to_idx.setdefault("{}-{}".format(a-1, b-1), i)
        edges_to_idx.setdefault("{}-{}".format(b-1, a-1), i)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx]
            coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            if colors[coloridx] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
                coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            colors[coloridx] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for col in colors:
        print(col)
            
            




if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
                maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Submission status: Accepted

Solution code:
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Submission status: Accepted

Solution code:
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        #nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(sys.stdin.readline())
G = [[] for _ in range(n+1)]
G_order = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G_order.append(b)

que = deque([0])
C = [0]*(n+1)
while que:
    nw = que.popleft()
    c = 1
    for nx in G[nw]:
        if c==C[nw]:
            c+=1
        C[nx] = c
        c += 1
        que.append(nx)

print(max(C))
for i in G_order:
    print(C[i])

Submission status: Accepted

Solution code:
n = int(input())
ab = []
for i 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]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        
color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue # 子に対応させる
        if c == ng:
            c += 1
        color[y] = c
        c += 1

print(max(color))
for a,b in ab:
    if parent[a] == b:
        print(color[a])
    else:
        print(color[b])