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

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)
        # path[b-1].append(a-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            
            if c == k:
                k += 1
            visited[next_node] = True
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            k += 1
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

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)
        path[b-1].append(a-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        # k = 0
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            
            if c == k:
                k += 1
            visited[next_node] = True
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            k += 1
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

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)
        path[b-1].append(a-1)
        # ab.append(str(a-1)+str(b-1))
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        # k = 1
        k = 0
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            k += 1
            if c == k:
                k += 1
            visited[next_node] = True
            # ans[str(pre)+str(next_node)] = k
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = {}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append((a,b))
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[tuple(sorted((p,i)))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color.values()))
for i in ab:
  print(color[i])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append((b-1,i))
    G[b-1].append((a-1,i))
check=[False]*n
p=0
stack=[(0,0)]
ans=[0]*(n-1)
while len(stack)>0:
    now=stack.pop()
    x=now[0]
    y=now[1]
    check[x]=True
    if len(G[x])>p:
        p=len(G[x])
    j=1
    for i in G[x]:
        if check[i[0]]:
            continue
        if j==y:
            j+=1
        ans[i[1]]=j
        stack.append((i[0],j))
        j+=1
print(p)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
es=[[] for i in range(n)]
l=[list(map(int,input().split())) for i in range(n-1)]
for i in range(n-1):
   l[i][0]-=1
   l[i][1]-=1
   es[l[i][0]].append(l[i][1])
   es[l[i][1]].append(l[i][0])
dic={}
use=[1]*n
def dfs(v,k):
    cnt=0
    use[v]=0
    for i in es[v]:
        if use[i]:
            if cnt==k:
                cnt+=1
            dic[(min(v,i),max(v,i))]=cnt
            dfs(i,cnt)
            cnt+=1
dfs(0,-1)
ans=[0]*(n-1)
k=0
for i in range(n-1):
    ans[i]=dic[l[i][0],l[i][1]]+1
    k=max(k,ans[i])
print(k)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
es=[[] for i in range(n)]
l=[list(map(int,input().split())) for i in range(n-1)]
for i in range(n-1):
   l[i][0]-=1
   l[i][1]-=1
   l[i][0],l[i][1]=min(l[i][0],l[i][1]),max(l[i][0],l[i][1])
   es[l[i][0]].append(l[i][1])
   es[l[i][1]].append(l[i][0])
dic={}
use=[1]*n
def dfs(v,k):
    cnt=0
    use[v]=0
    for i in es[v]:
        if use[i]:
            if cnt==k:
                cnt+=1
            dic[(min(v,i),max(v,i))]=cnt
            dfs(i,cnt)
            cnt+=1
dfs(0,-1)
ans=[0]*(n-1)
k=0
for i in range(n-1):
    ans[i]=dic[l[i][0],l[i][1]]+1
    k=max(k,ans[i])
print(k)
for i in ans:
    print(i)

Submission status: Accepted

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

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

    for edge in edges:
        a, b = edge
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    colors = defaultdict(int)
    def bfs():
        q = deque() # (index, parent color)
        q.append((0, 0))
        while len(q):
            now, par_col = q.popleft()
            color = 0
            for v in to[now]:
                x, y = sorted([v, now])
                if colors[(x, y)]:
                    continue
                else:
                    color += 1
                    if color == par_col:
                        color += 1

                    colors[(x, y)] = color
                    q.append((v, color))
    bfs()

    ans = max(colors.values())
    print(ans)
    
    for edge in edges:
        x, y = edge
        x -= 1
        y -= 1
        print(colors[(x, y)])

                


        



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
edges = list(
    map(lambda s: 
        tuple(map(int,s.strip().split())), sys.stdin.readlines()
    )
)

children = [ [] for _ in range(n+1)]
for e in edges:
    children[e[0]].append(e[1])
    children[e[1]].append(e[0])

colors = [{} for _ in range(n+1)]

check = [False for _ in range(n+1)]

que = deque()
que.append((1, 0))

def solve(i, x):
    # log(i, x)
    check[i] = True

    color = 0
    for node in children[i]:
        if check[node]:
            continue

        color += 1
        if color == x:
            color += 1

        # log(i, node, color)
        colors[i][node] = color
        colors[node][i] = color
        que.append((node, color))

while que:
    e = que.popleft()
    solve(e[0], e[1])

maxColor = 0

for i in range(1, n+1):
    c = colors[i]
    maxColor = max(maxColor, max(c.values()))

print(maxColor)

for e in edges:
    print(colors[e[0]][e[1]])

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  N = int(readline())
  graph = [[] for _ in range(N+1)]
  m = map(int, read().split())
  AB = list(zip(m,m))
  
  for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
  
  root = 1
  parent = [0] *(N+1)
  order = []
  stack = [root]
  Q = deque(stack)
  while Q:
    x = Q.popleft()
    order.append(x)
    for y in graph[x]:
      if y == parent[x]:
        continue
      parent[y] = x
      Q.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
  ans = []
  for a, b in AB:
    if parent[a] == b:
      ans.append(color[a])
    else:
      ans.append(color[b])
  K = max(ans)
  print(K)
  print('\n'.join(map(str, ans)))
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

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

# 使用する色数 K = 最大次数
K = 0
root = -1
for i in range(N):
    K = max(K, len(edges[i]))
    if K == len(edges[i]):
        root = i

# rootから彩色していく
que = deque()
que.append((root, -1, -1))  # vertex, parent, parent color
ans = [-1 for i in range(N - 1)]

while len(que) > 0:
    now, par, par_col = que.popleft()
    color = 1
    for edge in edges[now]:
        if edge == par:
            continue
        if color == par_col:
            color += 1
        if (now, edge) in edgeind:
            ans[edgeind[(now, edge)]] = color
        else:
            ans[edgeind[(edge, now)]] = color
        que.append((edge, now, color))
        color += 1

print(K)
print('\n'.join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for i in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append((i, v-1))
    edge[v-1].append((i, u-1))


ans[0] = 1
parents = [-1]*n
que = deque([[0, 0]])
while que:
    a, b = que.popleft()
    color = 1
    for i, j in edge[a]:
        if parents[a] == j:
            continue
        if color == b:
            color += 1
        ans[i] = color
        parents[j] = a
        que.append([j, color])
        color += 1
print(max(ans))
for i in ans: print(i)

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = map(int,input().split())
    graph[a].append((i,b))
    graph[b].append((i,a))
colors = [0 for _ in range(n)]
parents = [0]*(n+1)
stack = [(1,0)]
while stack:
    x,c = stack.pop()
    color = 1
    for i,y in graph[x]:
        if parents[x] == y:
            continue
        else:
            parents[y] = x
            if color == c:
                color += 1
            colors[i] = color
            stack.append((y,color))
            color += 1
print(max(colors))
for i in range(1,n):
    print(colors[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = [0]*(n-1)
    next_node = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        node[i] = (a-1, b-1)
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [0]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = k
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            
    
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = mi()
    data[a-1].append((b-1,i))
    data[b-1].append((a-1,i))
    if i == 0:
        num = a-1
        col = 0

ans = [0]*(n-1)
from collections import deque
ima = deque()
ima.append([num,col])
while ima:
    num,col = ima.popleft()
    tmp = 1
    for lis in data[num]:
        if ans[lis[1]] != 0:
            continue
        if tmp == col:
            tmp += 1
        ans[lis[1]] = tmp
        ima.append([lis[0],tmp])
        tmp += 1
a = 0        
for i in range(n-1):
    a = max(a,ans[i])
print(a)
for i in range(n-1):
    print(ans[i])

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
def bfs(v,p,color):
    q=deque()
    q.append((v,p,0))
    ans={}
    while q:
        #qの先頭を取り出す
        V,P,NUM=q.popleft()
        num=min(0,NUM)+1
        for new_v in G[V-1]:
            if new_v==P:continue
            if NUM==num:num+=1
            ans[(V,new_v)]=num
            q.append((new_v,V,num))
            num=num+1
    return ans

n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
G=Graph(ab)
#print(G)

color=0
for i in G:
    temp=len(i)
    if color<temp:color=temp
print(color)

ans=bfs(1,-1,color)
#print(ans)
for i in ab:
    print(ans[i])

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  G=[[]*n for _ in range(n)]
  vp=[]

  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    vp.append((a,b))

  k=0
  d={}
  cs=[0]*n

  used=[False]*n
  used[0]=True
  q=collections.deque()
  q.append(0)
  while q:
    v=q.popleft()
    k=max(k,len(G[v]))
    cur=1
    for u in G[v]:
      if used[u]:
        continue
      if cur==cs[v]:
        cur+=1
      cs[u]=d[(u,v)]=d[(v,u)]=cur
      cur+=1
      used[u]=True
      q.append(u)

  print(k)
  for a,b in vp:
    print(d[(a,b)])

main()
# print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# キュー
from collections import deque

n = int(input())
graph = [set() for _ in range(n+1)]

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

k = 0
root = 0
for i in range(1,n):
    if( k < len(graph[i]) ):
        root = i
        k = len(graph[i])

ans = [0] * (n+1)
d = deque()
d.append((root,0,0))

while(d):
    child,parent,color = d.pop()
    edges = graph[child]
    next_color = 1
    for tmp in edges:
        x,i = tmp
        if(x != parent):
            if(next_color == color):
                next_color += 1
            ans[i] = next_color
            d.append((x,child,next_color))
            next_color += 1

print(k)
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
n=int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append((b-1,i))
node_color = [0]*n
branch_color = [0]*(n-1)
for start_node, goal  in enumerate(g):
    #スタートの色
    color = 1
    for goal_node , i in goal:
        if node_color[start_node] == color:
            color += 1
        node_color[goal_node] = color
        branch_color[i] = color
        color += 1
        
print(max(branch_color))
for i in branch_color:
    print(i)

Submission status: Accepted

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

used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].add(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.add(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)

Submission status: Accepted

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

vc=[0] * n
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        if vc[p] == color:
            color += 1
        vc[c] = color
        ec[i] = color
        color += 1
        

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()


def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(root):
        ' root から BFS し条件を満たすように彩色していく。各辺の色情報を color に記載。最後に使用した色の数を返す。'
        paths = deque([root])
        max_branch = 0
        while len(paths) != 0:
            edge_color = 0
            current = paths.popleft()
            parent_edge_color = color[current]
            for v in adj[current]:
                paths.append(v)
                edge_color += 1
                if edge_color == parent_edge_color:
                    edge_color += 1
                color[v] = edge_color
                max_branch = max(max_branch, edge_color)
        return max_branch
        
 
    n = ii()
    # 各辺の両端の頂点 index を保存したペア (tuple) の list
    L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    # 隣接リスト 親->子のみリンクをはれば十分
    adj = [[] for _ in range(n)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
    # 各辺の子供の index と色情報 (int) の対応記載される隣接行列 
    color = [0] * n
    
    print(bfs_tree_traverse(0))
    for pair in L:
        _, b = pair
        print(color[b])
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

num_colors = max(list(map(len, edges)))
edge_colors = [0] * (n-1)


def set_color(current, parent, color):
    next_color = 1
    for node, i in edges[current]:
        if next_color == color:
            next_color += 1
        if node != parent:
            edge_colors[i] = next_color
            set_color(node, current, next_color)
            next_color += 1


set_color(0, -1, 0)
print(num_colors)
for v in edge_colors:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
n=int(input())
E=[[] for _ in range(n)]
col=defaultdict(list)
l=[]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
  col[(a,b)]=-1
  col[(b,a)]=-1
  l.append((a,b))
s=-1
k=-1
for i in range(n):
  if len(E[i])>k:
    k=len(E[i])
    s=i
par=[-1]*n
stack=deque([s])
seen=[-1]*n
seen[s]=1
while stack:
  u=stack.pop()
  if u==s:
    cnt=1
  else:
    cnt=col[(par[u],u)]+1
  for v in E[u]:
    if seen[v]!=1:
      par[v]=u
      seen[v]=1
      if cnt<=k:
        col[(u,v)]=cnt
        cnt+=1
      else:
        col[(u,v)]=1
        cnt=2
      stack.append(v)
print(k)
for a,b in l:
  if col[(a,b)]==-1:
    print(col[(b,a)])
  else:
    print(col[(a,b)])

Submission status: Accepted

Solution code:
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        # どうせ左から見ていくので, 辺を右から左へ考える必要は無い.
        # tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  # One-based index.
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

# なんでか分からないが, こうして main() に仕舞ってあげたほうが少し早い.

Submission status: Accepted

Solution code:
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  # One-based index.
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

# なんでか分からないが, こうして main() に仕舞ってあげたほうが少し早い.

Submission status: Accepted

Solution code:
from collections import OrderedDict, deque

n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
coloring = OrderedDict()
for e in edges:
    a, b = e[0] - 1, e[1] - 1
    tree[a].append(b)
    tree[b].append(a)
    coloring[(a, b)] = 0

q = deque()
q_append = q.append
q_popleft = q.popleft
seen = [False] * n
q_append(0)
col_count_by_v = [set() for _ in range(n)]
while len(q):
    new_v = q_popleft()
    seen[new_v] = True
    color_i = 1  # One-based index.
    for adj in tree[new_v]:
        if seen[adj]:
            continue
        q_append(adj)
        while color_i in col_count_by_v[new_v]:
            color_i += 1
        coloring[(new_v, adj)] = color_i
        col_count_by_v[new_v].add(color_i)
        col_count_by_v[adj].add(color_i)
        color_i += 1

print(len(set(coloring.values())))
for c in coloring.values():
    print(c)

Submission status: Accepted

Solution code:
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  # One-based index.
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)
            color_i += 1

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    seen = [False] * n
    q.append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q.popleft()
        seen[new_v] = True
        color_i = 1  # One-based index.
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q.append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)
            color_i += 1

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, color, prev_c):
    """G: graph, v: vertex, p: parent"""
    c = 1
    # Loop for each child
    for e in G[v]:
        if e[0] == p:
            continue
        if c == prev_c:
            c += 1
        color[e[1]] = c
        dfs(G, e[0], v, color, c)
        c += 1


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

    color = [-1] * (N - 1)
    dfs(G, 0, -1, color, -1)
    K = max(color)
    print(K)
    print(*color, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
n=int(input())
es=[[] for i in range(n)]
es2=[]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
    es2.append((a-1,b-1))
k=0
col=[1]+[0]*(n-1)

a=defaultdict()
par= [0]*n
total = 0
q = deque()
q.append(0)

while q:
    c = 1
    p = q.popleft()
    for i in es[p]:
        if col[i] == 0:
            col[i] = 1
            if c == par[p]:
                c += 1
            a[(p,i)] = c
            par[i] = c
            c += 1
            q.append(i)
    total = max(total,c-1)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = [list(map(int, readline().split())) for i in range(n - 1)]
gragh = [[] for j in range(n + 1)]
for a, b in ab:
    gragh[a].append(b)
    gragh[b].append(a)
root = 1
parent = [0] * (n + 1)
stack = [root]
order = []

while stack:
    x = stack.pop()
    order.append(x)
    for y in gragh[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
color = [-1] * (n + 1)

for x in order:
    ng = color[x]
    cnt = 1
    for y in gragh[x]:
        if y == parent[x]:
            continue
        if cnt == ng:
            cnt += 1
        color[y] = cnt
        cnt += 1

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

Submission status: Accepted

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

n = int(input())
edge = [[] for i in range(n)]

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

k = max(len(e) for e in edge)
print(k)

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

def dfs(v=0, p=-1, to_p_col = -1):
    col = 1
    for u, idx in edge[v]:
        if u != p:
            if col == to_p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
print('\n'.join(map(str,ans)))