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())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)

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

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

print(max(MA))
for i in range(N-1):
    print(edge[ans[i]])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)
M = 0

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

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                M = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    M = max(M,MA[now])
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

print(M)
for i in range(N-1):
    print(edge[ans[i]])

Submission status: Accepted

Solution code:
import sys
import resource
sys.setrecursionlimit(10**5)
n = int(input())
l = [[] for _ in range(n+1)]
s = [0 for _ in range(n+1)]
ll = []
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append([bi,i])
  l[bi].append([ai,i])
  s[ai] += 1
  s[bi] += 1
mx = 0
for i in range(1,n+1):
  if s[i] > mx:
    mx = s[i]
    mxi = i
print(mx)
ans = [0 for _ in range(n-1)]
def dfs(a,b,c):
  i = 1
  for h,j in l[a]:
    if h != b:
      if i == c:
        i += 1
      ans[j] = i
      dfs(h,a,i)
      i += 1
  return
dfs(mxi,0,0)
for x in ans:
  print(x)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    B=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        B.append(b)

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                color+=1
        color-=1
        K=max(K,color)

    print(K)
    for x in B:
        print(link[x])
if __name__=="__main__":
    main()

Submission status: Accepted

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

def dfs(x, c=-1, p=-1):
    k = 1
    for y, ei in G[x]:
        if y == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k; k+=1
        dfs(y, ans[ei], x)

n = int(input())
G = [[] for _ in range(n)]
ans = [0] * (n-1)
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 g in G:
    mx = max(mx, len(g))
print(mx)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import queue

N = int(input())

e = []
v2e = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    v2e[a].append((b, i))
    v2e[b].append((a, i))
    
count = 0
f = [False] * N
f[0] = True
c = [-1] * (N - 1)
q = queue.Queue()
q.put((-1, 0))
while q.qsize() > 0:
    ie, v = q.get()
    t = 0
    for i, j in v2e[v]:
        if f[i] == False:
            if t == ie:
                t += 1
            q.put((t, i))
            c[j] = t
            f[i] = True
            t += 1
                
print(max(c) + 1)
for i in range(len(c)):
    print(c[i] + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

N = int(input())

edges = [[] for i in range(N+1)]
color = [0 for i in range(N-1)]

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

root = -1
MAX = 0

for i in range(N+1):
    if MAX < len(edges[i]):
        root = i
        MAX = len(edges[i])

K = MAX

def dfs(parent,v,c):
    flag = 0
    for i in range(len(edges[v])):
        if edges[v][i][0] == parent:
            flag = 1
        else:
            color[edges[v][i][1]] = (c+i+1-flag)%K
            dfs(v,edges[v][i][0],(c+i+1-flag)%K)

dfs(-1,root,0)

print(K)

for i in color:
    if i == 0:
        print(K)
    else:
        print(i)

Submission status: Accepted

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

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

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  visited[v] = True
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

Submission status: Accepted

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

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

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

Submission status: Accepted

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

def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    l=[[] for _ in range(n+1)]
    for i in range(n-1):
        l[ab[i][0]].append(ab[i][1])
    col=[0]*(n+1)
    chk=deque([1])
    while chk:
        x=chk.popleft()
        c=0
        for y in l[x]:
            c+=1
            if col[x]==c:
                c+=1
            col[y]=c
            chk.append(y)
    print(max(col))
    for i in range(n-1):
        print(col[ab[i][1]])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
E = [[] for _ in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
color = [0]*(N+1)

start = 1
q = deque([start])
while(q):
    v = q.pop()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == color[v])
        color[u] = c
        q.append(u)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
A=[]
B=[0]*(n-1)
G=[[] for i in range(n)]
GG=[[0]*2 for i in range(n-1)]
for i in range(n-1):
  a,b=map(int,input().split())
  GG[i]=[a,b]
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  A.append(a*10**6+b)
D=dict(zip(A,B))
ans=0
for i in range(n):
  if len(G[i])>ans:
    ans=len(G[i])
    a=i
print(ans)
VC=[10**6]*n #各頂点と親を結ぶ辺の色を記憶
#aを根とする木をDFS
E=[0]*n
E[a]=1
F=deque([a])
while len(F)>0:
  s=F[0]
  F.popleft()
  c=1
  for i in range(len(G[s])):
    if E[G[s][i]]==0:
      F.append(G[s][i])
      E[G[s][i]]=1
      if c==VC[s]:
        c=c+1
      VC[G[s][i]]=c
      t=s
      D[min(s+1,G[s][i]+1)*10**6+max(s+1,G[s][i]+1)]=VC[G[s][i]]
      c=c+1
for i in range(n-1):
  print(D[GG[i][0]*10**6+GG[i][1]])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    ab = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
        ab.append([a, b])
    queue = deque([1])

    # 木の親を決める
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    # 色番号を割り当てる
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]

path=[[] for _ in range(n)]
for i,(a,b) in enumerate(AB):
  a,b=a-1,b-1
  path[a].append((b,i))
  path[b].append((a,i))
  
visited=[0]*n
ans=[None]*(n-1)
  
def dfs(v,c=-1):
  nc=1
  for to,i in path[v]:
    if visited[to]: continue
    visited[v]=1
    if nc==c: nc+=1
    ans[i]=nc
    dfs(to,nc)
    nc+=1
dfs(0)
print(max(ans))
print(*ans,sep='\n')

Submission status: Accepted

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

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

cs = []
ans = {}
def dfs(v, p, c):
    color = 0
    for g in G[v]:
        if g == p:
            continue
        color += 1
        if color == c:
            color += 1
        dfs(g, v, color)
        ans[(v+1, g+1)] = color

dfs(0, -1, 0)
print(max(ans.values()))
for e in E:
    print(ans[e])

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

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

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

N = int(input())


class Node:
    def __init__(self, index):
        self.index = index
        self.edges = []

class Edge:
    def __init__(self, index, a, b):
        self.a = a
        self.b = b
        self.index = index
        self.color = 0

    def to(self, fm):
        if fm == self.a:
            return self.b
        elif fm == self.b:
            return self.a
        else:
            return None


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

passed = set()


def rec(node, via_color, K):
    passed.add(node.index)
    color = 1
    for edge_index in node.edges:
        edge = edges[edge_index]
        to_node_index = edge.to(node.index)
        if to_node_index in passed:
            continue
        if color == via_color:
            color += 1
        edge.color = color
        K = rec(nodes[to_node_index], color, K)
        color += 1
    return max(color-1, K)


K = rec(nodes[0], 0, 1)
print(K)
for edge in edges:
    print(edge.color)

Submission status: Accepted

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

N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for b,i in E[p]:
    if m == n: m+=1
    ans[i]=m
    sub(b,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Accepted

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

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

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

visited = [0]*n
ans_color = [0]*(n-1)

# DFS
def dfs(v, fromColor):
    color = 1
    visited[v] = 1
    for to, i in es[v]:
        if visited[to]: continue

        if color == fromColor:
            color += 1
        ans_color[i] = color
        dfs(to, color)
        color += 1

root = 0 # 頂点1が存在することが問題文中で保証されてるからここを根ノードとしよう
dfs(root, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Submission status: Accepted

Solution code:
from collections import deque

import sys
sys.setrecursionlimit(10**6)

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

#入力を木構造に入力する
root = 1
nodes[root][0] = root
for i in range(N-1):
    a,b = AB[i]
    nodes[a][1].append(b)
    nodes[b][0] = a
#print(nodes)

K = len(nodes[1][1])

for i in range(2,N+1):
    K = max(K,len(nodes[i][1])+1)

Q = deque([root])

while len(Q) != 0:
    q = Q.popleft()
    children = nodes[q][1]
    root_color = nodes[q][2]
    i = 1
    for child in children:
        Q.append(child)
        if i == root_color:
            i += 1
        nodes[child][2] = i
        i += 1

#print(nodes)
print(K)
for a,b in AB:
    print(nodes[b][2])

Submission status: Accepted

Solution code:
N = int(input())
e = []
ed = {}
g = [[] for i in range(N)]
c = [0]*(N-1)
ny = [0]*N
for i in range(N-1):
    a, b = (int(i) for i in input().split())
    ny[a-1] += 1
    ny[b-1] += 1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    e.append((a-1,b-1))
    ed[(a-1, b-1)] = i

mac = max(ny)
for i in range(N):
    if ny[i] == mac:
        oya = i
        break

Q = [(0, oya)]
prev = [False]*N
while Q:
    col, v = Q.pop()
    prev[v] = True
    l = g[v]
    ucol = 0
    for u in l:
        if not prev[u]:
            ucol += 1
            if col == ucol:
                ucol += 1
            Q.append((ucol, u))
            a, b = min(u, v), max(u, v)
            c[ed[(a, b)]] = ucol
print(mac)
for i in range(N-1):
    print(c[i])

Submission status: Accepted

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

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

adj = defaultdict(list)
for i, (a, b) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))

k = max([len(li) for li in adj.values()])
print(k)

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

def dfs(u, p_col):
	col = 1
	for v, i in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1


dfs(0, -1)

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

def enable_color(vertex, color_count, used_color):
    used = used_color[vertex]
    for i in range(1, color_count+1):
        if i not in used:
            return i

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

    leafs = [[] for _ in range(N+1)]
    for a, b in AB:
        leafs[a].append(b)

    # 各頂点についてBFS
    q = deque()
    q.append(1)
    color = [0] * (N + 1)

    while q:
        root = q.popleft()
        used_color = color[root]
        c = 1
        for leaf in leafs[root]:
            if c == used_color:
                c += 1
            color[leaf] = c
            c += 1
            q.append(leaf)
    print(max(color))
    for _, b in AB:
        print(color[b])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 参考：https://atcoder.jp/contests/abc146/submissions/10412733

from collections import deque

N = int(input())
# グラフ準備
graph = [[] for _ in range(N + 1)]
seq = []

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

# BFS

q = deque([1])
color = [0] * (N + 1)

while q:
    checking_parent = q.popleft()
    parent_color = color[checking_parent]
    c = 1
    for child in graph[checking_parent]:
        if c == parent_color:
            c += 1
        # 使用したcolorをchildの色として格納する
        color[child] = c
        c += 1
        # childを探索候補へ追加
        q.append(child)

print(max(color))
for i in range(N - 1):
    print(color[seq[i]])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

readline = sys.stdin.readline
n = int(readline())
ab = [None] * (n-1)
G = [list() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    ab[i] = a, b
colors = defaultdict(int)
q = deque([0])
used = [0] * n
used[0] = 10**6
K = 0
while q:
    x = q.popleft()
    c = 1
    for y in G[x]:
        if used[y]:
            continue
        if used[x] == c:
            c += 1
        used[y] = colors[x, y] = colors[y, x] = c
        c += 1
        q.append(y)

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

Submission status: Accepted

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

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

    col = 0
    for x in edge:
        col = max(col,len(x))
        
    print(col)
    ans = [-1 for _ in range(N)]
    go = [False for _ in range(N)]
    q = deque([0])
    while q:
        now = q.pop()
        go[now] = True
        c = 0
        for fol in edge[now]:
            if go[fol]:
                continue
            if c != ans[now]:
                ans[fol] = c
            else:
                ans[fol] = col-1
            c += 1
            q.append(fol)
    
    for i in range(N-1):
        print(ans[e[i]-1]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import heapq
import collections
from collections import deque

n = int(input())
ab = []
visit = [-1 for _ in range(n+1)]
tree = [[]  for _ in range(n+1)]
colors = {}
for i in range(n-1):
    a, b = map(int,input().split())
    ab.append((a, b))
    tree[a].append(b)
    tree[b].append(a)
    colors[(a,b)] = -1
    colors[(b,a)] = -1

# abの色を格納
visit[1]=1

q = deque([(1,0)]) #V,color のtuple
K = 0
while q:
    v,from_color = q.popleft()
    c = 1
    for next_v in tree[v]:
        if visit[next_v] == -1:
            visit[next_v] = 1
            if c == from_color:
               c += 1
            colors[(v,next_v)] = colors[(next_v,v)] = c
            q.append((next_v,c))
            c += 1
anss = []
K = 0
for temp in ab:
    a,b = temp
    K = max(K, colors[(a,b)] )
    anss.append(colors[(a,b)])

print(K)
for c in anss:
    print(c)





# for k,v in di:
#     color = max(colors,len(v))

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

#print(ab)
outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        count += 1
        if dicthoji[v1] == count: #前に色を使っていたら飛ばす
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])
#print(dicthoji)

print(max(dicthoji.values()))
for i in range(N-1):
    print(dicthoji[ab[i][1]])

Submission status: Accepted

Solution code:
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    ans = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()
            cnt=1

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if ans[x]!=cnt:
                        ans[y]=cnt
                        cnt+=1
                    else:
                        cnt+=1
                        ans[y]=cnt
                        cnt+=1

        return ans
    return bfs()

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

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

x=tree(0)
print(max(x))
for i in range(n-1):
    print(x[a[i][1]-1])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

#print(ab)
outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
hoji = []
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        count += 1
        if dicthoji[v1] == count: #前に色を使っていたら飛ばす
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])
        hoji.append(count)
#print(dicthoji)

print(max(hoji))
for i in range(N-1):
    print(dicthoji[ab[i][1]])

Submission status: Accepted

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


def Treemake(node,parent,root,num):
    A.append([node,parent,root,num])
    for i,j in root:
        Treemake(i,node,Tree[i],j)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
Tree=[[] for _ in range(n)]
A=[]
for a,b,c in AB:
    Tree[a-1].append([b-1,c])
Treemake(0,-1,Tree[0],0)

color=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        i=i+1
        if color[num]==i:flag=1
        color[j[1]]=i+flag

print(max(color))
for i in range(1,n):
    print(color[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextV  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextV.append(b)
    
q = deque([1]) # 頂点1から幅優先探索
color = [0]*(N+1)
while q:
  v = q.popleft()
  parentC = color[v]
  c = 1
  for child in graph[v]:
    if c == parentC: # 親と同じ色だったら次の色へスキップ
      c += 1
    color[child] = c # 使用した色を保持
    c += 1 # 次の色へスキップ
    q.append(child)
    
print(max(color))    
for b in nextV:
  print(color[b])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextEdege  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextEdege.append(b)
  
q = deque([1]) # 頂点1から幅優先探索
color = [0]*(N+1)
while q:
  v = q.popleft()
  c = 1
  for u in graph[v]:
    if c == color[v]:
      c += 1
    color[u] = c
    c += 1
    q.append(u)
    
print(max(color))    
for b in nextEdege:
  print(color[b])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

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


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        ans[j[1]]=i+1+flag

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        ans[j[1]]=i+1+flag

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