Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加

N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)

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

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(range(1,k+1))
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
print(solve(n, a, b))

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())
B = AB[1::2]

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

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Submission status: Accepted

Solution code:
from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

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

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	for b in B:
		print(C[b])

main()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[[] for i in range(n)]#0-indexed
edges=[tuple(map(int,input().split())) for i in range(n-1)]#1-indexed
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}#0-indexed
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
if most_connected>graph[most_connected][0]:
  most_connected,graph[most_connected][0]=graph[most_connected][0],most_connected
edge_color[(most_connected,graph[most_connected][0])]=1
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    
    edge_color[(V,I)]=vertex[v]%color+1
    vertex[V],vertex[I]=edge_color[(V,I)],edge_color[(V,I)] 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

Submission status: Accepted

Solution code:
from collections import deque
n = int(raw_input())
edges = []
for i in range(n - 1):
    edges.append(map(int, raw_input().split()))
edge_num = {}
G = [[] for i in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = deque([0])
vis.add(0)
while q:
    u = q.popleft()
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            vis.add(v)
            q.append(v)
    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1
print len(set(ans))
for i in ans:
    print i

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

def dfs(v, c):
    res = -1
    i = 0
    used[v] = 0
    for u in e[v]:
        if used[u] == 1:
            i += 1
            if i == c:
                i += 1
            ans[ord[(u, v)]] = i
            res = max(res, dfs(u, i))
    res = c if res == -1 else res
    res = max(i, res)
    return res

N = int(input())
e = [[] for i in range(N)]
es = defaultdict(int)
ord = defaultdict(int)
ans = [None] * (N-1)
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    e[a].append(b)
    e[b].append(a)
    es[(a, b)] = es[(b, a)] = -1
    ord[(a, b)] = ord[(b, a)] = i
used = [1] * N
print(dfs(0, 0))
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
dc={}
g,c=GI(n,n-1)
for a,b in c:
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col
#                show(i,c,col)
                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Accepted

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

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

e = [[] for _ in range(n)]

p = [0] * n
c = [0] * n
d = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0

q = [0]
p[0] = -1

while q:
    x = q.pop()
    temp = c[x]
    color = 1
    me = max(me, len(e[x]))
    #print(x, temp)
    for y in e[x]:
        if color == temp:
            color += 1
        if d[y] == 0:
            q.append(y)
            c[y] = color
            p[y] = x
            color += 1
    d[x] = 1

#print(c)
#print(p)

print(me)

for a, b in ab:
    if p[a] == b:
        print(c[a])
    else:
        print(c[b])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(sys.stdin.buffer.readline())

neighbor = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, sys.stdin.buffer.readline().split())
    neighbor[a-1].append([b-1, i])
    neighbor[b-1].append([a-1, i])

K = max(len(l) for l in neighbor)
print(K)
ans = [-1]*(N-1)

def dfs(current_point, parent_point, parent_edge_color):
    color = 1
    for next_point, idx in neighbor[current_point]:
        if next_point != parent_point:
            if parent_edge_color == color:
                color += 1
            ans[idx] = color
            dfs(next_point, current_point, color)
            color += 1

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    b-=1
    bi[i]=b
    children[a-1].append(b)

queue = deque([0])
colors = [0] * N
#maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    #maxColor = max(maxColor, color-1)

print(max(colors))
for i in range(N-1):
    print(colors[bi[i]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    b-=1
    bi[i]=b
    children[a-1].append(b)

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

print(maxColor)
for i in range(N-1):
    print(colors[bi[i]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    bi[i]=b-1
    children[a-1].append(bi[i])

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

print(maxColor)
for i in range(N-1):
    print(colors[bi[i]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    bi[i]=b-1
    children[a-1].append(b-1)

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

print(maxColor)
for i in range(N-1):
    print(colors[bi[i]])

Submission status: Accepted

Solution code:
n = int(input())
dim = [0 for _ in range(n+1)] #次数のカウント
parent = [0 for _ in range(n+1)] #頂点iの親
col = [ 0 for _ in range(n+1)]  #頂点iの親からiに伸びる枝が使っている色
using = [[] for _ in range(n+1)]
AB = []
for i in range(n-1):
    a, b = map(int, input().split())
    AB.append([a, b, i])
    parent[b] = a
    dim[a] += 1
    dim[b] += 1
#幅優先探索のためにソート
AB_sorted = sorted(AB)
prev_a = -1
for j in range(n-1):
    a = AB_sorted[j][0]
    b = AB_sorted[j][1]
    index = AB_sorted[j][2]
    if a != prev_a:
        paint = 1
    
    while paint == col[a] or paint in using[a]:#親から自分に伸びてる枝以外の色にする
        paint += 1
    
    col[b] = paint
    using[a].append(paint)
    AB[index].append(paint) #辺の色を追加
    prev_a = a

print(max(dim))
for i in range(n-1):
    print(AB[i][3])

Submission status: Accepted

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

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

ans = [None]*(N-1)
def dfs(cur, p_color, p=-1):
    color = 1
    for (to, i) in graph[cur]:
        if to == p: continue
        if color == p_color:
            color = color+1
        ans[i] = color
        dfs(to, color, p=cur)
        color = color+1

dfs(0, -1)
print(max(ans))
[print(a) for a in ans]

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N=int(input());AB=[tuple(map(int,input().split())) for _ in range(1,N)]

co=[0 for _ in range(N)]
prev=0
color=1
for a,b in sorted(AB):
  if prev!=a:
    color=1
  if co[a-1]==color:
    color+=1
  co[b-1]=color
  prev=a
  color+=1

print(max(co))
for _,b in AB:
  print(co[b-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    keys = [tuple(int(i)-1 for i in input().split()) for _ in range(N-1)]
    for e in keys:
        G[e[0]].append(e[1])
        G[e[1]].append(e[0])
    max_deg = 0
    for g in G:
        max_deg = max(max_deg, len(g))
    edge_color = {k: 0 for k in keys}

    G_color = ['WHITE' for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            c = 0
            if G_parent[u] != "NIL":
                c = ((edge_color[(G_parent[u], u)])+1) % max_deg
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = c
                    c = (c+1) % max_deg
            G_color[u] = 'BLACK'

    bfs(0)
    print(max_deg)
    for k in keys:
        print(edge_color[k] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ans = [0]*(N-1)

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

print(max([len(x) for x in edge]))

que = [[0,0]]
while(que):
    p_num,p_color = que.pop()
    color = 1
    for c_num,edgenum in edge[p_num]:
        if ans[edgenum] != 0:
            continue
        if color == p_color:
            color += 1
        ans[edgenum] = color
        que.append([c_num,color])
        color += 1
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

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

stack = deque([0])
parent = [None]*n
colors = [0]*n
while stack:
    node = stack.popleft()
    color = 1
    for child in graph[node]:
        if child == parent[node]:
            continue
        parent[child] = node
        if color == colors[node]:
            color += 1
        colors[child] = color
        color += 1
        stack.append(child)

 
k = max(colors)
print(k)
for a, b in ab:
    if (a-1) == parent[b-1]:
        print(colors[b-1])
    else:
        print(colors[a-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1]) # root = 1
    parent = [None] * (n + 1)
    color = [None] * (n + 1) # color of the edge(parent[y], y)

    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 1
            
    print(max(color[2:]))

    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
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1]) # root = 1
    parent = [None] * (n + 1)
    color = [0] * (n + 1) # color of the edge(parent[y], y)

    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 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
from collections import deque
import numpy as np

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2)

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    parent = np.zeros(n + 1, dtype=np.int64)
    color = np.zeros(n + 1, dtype=np.int64) # color of the edge(parent[y], y)

    q = deque([1]) # root = 1
    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 1

    print(np.amax(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
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    root = 1
    q = deque()
    q.append(root)
    parent = [None] * (n + 1)
    color = [0] * (n + 1) # color[y]はx = parent[y]としてcolor[x] に依存する。

    while q:
        x = q.popleft()
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if color[x] == c:
                c += 1
            color[y] = c
            c += 1
            q.append(y)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  svis = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  #print(x, viss)
  for y, i in e[x]:
    #print(x, y, t)
    while t in viss:
      t += 1
    if i in vis:
      continue
    #print(x, y, t)
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
    dfs(y)
  #print(res)
dfs(1)
print(max(res))
for r in res: print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  svis = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  #print(x, viss)
  for y, i in e[x]:
    #print(x, y, t)
    while t in viss:
      t += 1
    if i in vis:
      continue
    #print(x, y, t)
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
  for y in svis:
    dfs(y)
  #print(res)
dfs(1)
print(max(res))
for r in res: print(r)

Submission status: Accepted

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

N = int(input())
ki =[[] for _ in range(N)]
ab = []
dict = {}
k = 0
def dfs(v, p = 0, ban_color = 0):
    global k
    color = 1
    for i in ki[v]:
        if i == p:
            continue
        if ban_color == color:
            color += 1
        dict[(v, i)] = color
        dfs(i, v, color)
        color += 1
    k = max(k, color - 1)
    return


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

dfs(0)
print(k)
for key in ab:
    print(dict[key])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

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

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
from collections import deque
# from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n=int(input())
	E=[[] for i in range(n+1)]
	O=[]
	for i in range(n-1):
		a,b=map(int,input().split())
		E[a].append(b)
		O.append(b)
		
	C=[0]*(n+1)
	q = deque([1])
	while q:
		now = q.popleft()
		cnt=1
		for i in E[now]:
			if cnt==C[now]:
				cnt+=1
			C[i]=cnt
			cnt+=1
			q.append(i)
	print(max(C))
	for i in O:
		print(C[i])
	
	
if __name__ == "__main__":
		main()

Submission status: Accepted

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

N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


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

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])

Submission status: Accepted

Solution code:
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

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

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	print("\n".join(str(C[b]) for b in B))

main()

Submission status: Accepted

Solution code:
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

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

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C), *(C[b] for b in B))

main()

Submission status: Accepted

Solution code:
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

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

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	for b in B:
		print(C[b])

main()

Submission status: Accepted

Solution code:
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

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

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q += u,

	print(max(C))
	for b in B:
		print(C[b])

main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())
    A, B = AB[::2], AB[1::2]

    E = [[] for _ in range(N + 1)]
    for a, b in zip(A, B):
        E[a].append(b)

    Q = deque([1])
    C = [0] * (N + 1)
    while Q:
        v = Q.popleft()
        c = 0
        for u in E[v]:
            c += 1 + (c + 1 == C[v])
            C[u] = c
            Q.append(u)

    print(max(C))
    for b in B:
        print(C[b])

main()

Submission status: Accepted

Solution code:
from collections import deque

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

    E = [[] for _ in range(N + 1)]
    B = AB[1::2]
    for a, b in zip(*[iter(AB)] * 2):
        E[a].append(b)

    Q = deque([1])
    C = [0] * (N + 1)
    while Q:
        v = Q.popleft()
        c = 0
        for u in E[v]:
            c += 1 + (c + 1 == C[v])
            C[u] = c
            Q.append(u)

    print(max(C))
    for b in B:
        print(C[b])

main()

Submission status: Accepted

Solution code:
from collections import deque

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

    E = [[] for _ in range(N + 1)]
    I = []
    for a, b in zip(*[iter(AB)] * 2):
        E[a].append(b)
        I.append(b)

    Q = deque([1])
    C = [0] * (N + 1)
    while Q:
        v = Q.popleft()
        c = 0
        for u in E[v]:
            c += 1 + (c + 1 == C[v])
            C[u] = c
            Q.append(u)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

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

E = [[] for _ in range(N + 1)]

memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].append(b)
    E[b].append(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

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

A = [0] * (N - 1)

cand = {i for i in range(1, K + 1)}

visited = [False] * (N + 1)

Q = deque([(-1, 1)])
visited[1] = True
while Q:
    p, v = Q.popleft()
    c = 0
    for u in E[v]:
        if visited[u]:
            continue
        visited[u] = True
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[memo[(v, u)]] = c

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

Submission status: Accepted

Solution code:
def p_d():
    n = int(input())
    t = [[] for _ in range(n)]
    p = [-1] * n
    for i in range(n - 1):
        a, b = map(int, input().split())
        t[a - 1].append((i, b - 1))
        p[b - 1] = a - 1
    q = [(0, -1)]
    ans = [-1] * (n - 1)
    while q:
        x, c0 = q.pop()
        c = 1
        for i, y in t[x]:
            if c == c0:
                c += 1
            ans[i] = c
            q.append((y, c))
            c += 1
    print(max(ans))
    for a in ans:
        print(a)
        
p_d()