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 math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append((b,i))
        way[b].append((a,i))

    q = queue.Queue()
    q.put((1,-1,-1)) #nowplace,pastplace,hen
    col = [-1]*(n-1)
    while not q.empty():
        np,pp,hen = q.get()
        nc = 1
        for i,wn in way[np]:
            if i == pp:
                continue
            if nc == hen:
                nc += 1
            col[wn] = nc
            q.put((i,np,nc))
            nc += 1
    print(max(col))
    for i in col:
        print(i)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

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

mx_color = 0    
for i in range(n):
    mx_color = max(mx_color,len(adj[i]))

dist = [-1]*n

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

q = deque([])
q.append([0,-1])
dist[0] = 0

while len(q) > 0:
    v,c = q.popleft()
    color = 1
    
    if color == c:
        color += 1
        
    for nv,nc in adj[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            q.append([nv,color])
            res[nc] = color
            color += 1
            if color == c:
                color += 1

print(mx_color)

for i in res:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


class Edge:
    def __init__(self, to_, id_):
        self.to = to_
        self.id = id_


ans = None
G = None
K = None


def dfs(to, c):
    global G
    global ans
    nc = c % K + 1
    for g in G[to]:
        if ans[g.id] != -1:
            continue
        ans[g.id] = nc
        dfs(g.to, nc)
        nc = nc % K + 1


def solve():
    global G
    global ans
    global K
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = Scanner.map_int()
        x -= 1
        y -= 1
        G[x].append(Edge(y, i))
        G[y].append(Edge(x, i))

    K = 0
    for i in range(N):
        K = max(K, len(G[i]))

    ans = [-1 for _ in range(N - 1)]
    dfs(0, 0)
    print(K)
    print(*ans, sep='\n')


def main():
    sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

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

ans = [0] * (n - 1)

q = deque([[1, 0, 0]])
while q:
    v, pcol, root = q.popleft()
    cnt = 1
    for node in graph[v]:
        if node[0] == root:
            continue
        if cnt == pcol:
            cnt += 1
        ans[node[1]] = cnt
        q.append([node[0], cnt, v])
        cnt += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
d = {}

for a, b in ab:
  graph[a] += [b]
  graph[b] += [a]

def dfs(u, pre, c):
  color = 0
  for v in graph[u]:
    if v != pre:
      color += 1
      if color == c:
        color += 1
      d[(u, v)] = color
      d[(v, u)] = color
      dfs(v, u, color)

dfs(0, -1, -1)
s = set()
for a, b in ab:
  s.add(d[(a, b)])

print(len(s))
for a, b in ab:
  print(d[(a, b)])

Submission status: Accepted

Solution code:
# 深さ優先探索
from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(10 ** 6)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

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

ans = [0] * (n - 1)

q = deque([[1, 0, 0]])
while q:
    v, pcol, root = q.popleft()
    cnt = 1
    for node in graph[v]:
        if node[0] == root:
            continue
        if cnt == pcol:
            cnt += 1
        ans[node[1]] = cnt
        q.append([node[0], cnt, v])
        cnt += 1

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

Submission status: Accepted

Solution code:
n=int(input())
edges=[[] for i in range(1+n)]
e={}
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    e[(_,__)]=i
    e[(__,_)]=i
    """
"""#weighted->erase
f=max(len(j)for j in edges)
print(f)
ret=[0]*(n-1)
from collections import deque
dq=deque([(1,1)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
while dq:
    a,c=dq.popleft()
    for to in edges[a]:
        if ret[e[(a,to)]]:continue
        ret[e[(a,to)]]=c
        c=c%f+1
        dq.append((to,c))
        
print(*ret,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
node_branch = [[] for _ in range(N+1)]
branch = [0] * (N)
link = [0] * (N+1)
checked = [False] * (N+1)

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

maxlen = 0
for i, node in enumerate(node_branch):
    if maxlen < len(node):
        maxlen = len(node)
        maxnode = i

print(maxlen)

d = deque()
d.append(maxnode)
link[1] = 0
checked[maxnode] = True

while len(d)>0:
    now = d.popleft()
    color = 1
    for n, b in node_branch[now]:
        if checked[n]:
            continue
        if color == link[now]:
            color += 1
        branch[b] = color
        link[n] = color
        color += 1
        checked[n] = True
        d.append(n)

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

Submission status: Accepted

Solution code:
N=int(input())

A=[[] for _ in range(N-1)]
B=[0]*N
C=[0]*N
D=[0]*N

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

for i in range(N-1): 
    c=0
    for j in A[i]:
        while True:
            c+=1
            if c!=B[i]:
                B[j-1]=c
                break

print(max(B))            

for i in range(1,N):
    D[C[i]]=B[i]

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
matrix= []
lis = [[] for i in range(n)]
ans = {}
for i in range(n):
    ans[i] = {}
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print(ans[root[0]][root[1]])

Submission status: Accepted

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

settansaku = set([])
setmada = {0}
listmada = [(0, None)]  #left: Vertex, right: Color
kouho = 1
num = [0 for _ in range(n-1)]

while kouho != 0:
	for i, cnt in listmada[:]:
		colors = {cnt}
		settansaku.add(i)
		setmada.remove(i)
		listmada.remove((i, cnt))
		kouho -= 1
		c = 0
		for k, j in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					while True:
						if c not in colors:
							listmada.append((k, c))
							colors.add(c)
							num[j] = c
							break
						c += 1
					kouho += 1

print(max(num)+1)
print("\n".join([str(i+1) for i in num]))

Submission status: Accepted

Solution code:
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
edges = []
for _ in range(n - 1):
	u,v = map(int, raw_input().split(' '))
	edges.append((u,v))
	adj[u].append(v)
	adj[v].append(u)
root = 1
q = collections.deque([root])
h = {}
while(q):
	u = q.popleft()
	c = 1

	used = set([h[tuple(sorted([u,v]))] for v in adj[u] if tuple(sorted([u,v])) in h]) 

	for v in adj[u]:
		t = tuple(sorted([u,v])) 
		if t not in h:
			while(c in used): c+=1
			h[t] = c	
			c+=1
			q.append(v)
print max(h.values())
for u,v in edges:
	print h[(u,v)]

Submission status: Accepted

Solution code:
import collections

n = int(input())
graph = [tuple(map(int, input().split())) for _ in range(n - 1)]
tree = [[] for _ in range(n)]
deg = [0] * n
color = {}
for a, b in graph:
    a, b = min(a - 1, b - 1), max(a - 1, b - 1)
    deg[a] += 1
    deg[b] += 1
    tree[a].append(b)
    tree[b].append(a)
    color[(a, b)] = 0
color_max = max(deg)
print(color_max)

c = [0] * n
c[0] = -1
que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    tmp = 1
    for j in tree[i]:
        if c[j] != 0: continue
        a, b = min(i, j), max(i, j)
        if tmp == c[i]: tmp += 1
        color[(a, b)] = tmp
        c[j] = tmp
        que.append(j)
        tmp += 1

for a, b in graph:
    a, b = min(a - 1, b - 1), max(a - 1, b - 1)
    print(color[(a, b)])

Submission status: Accepted

Solution code:
n = int(input())
L = []
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    L.append((a, b))
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
k = 0
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
key = sorted(d.keys())
dd = {1: 0}
ans = {}
for i in key:
    v = d[i]
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        ans[(i, j)] = c
        dd[j] = c
for a, b in L:
    print(ans[(a, b)])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

#頂点の色
path = [0 for _ in range(N-1)]
#木グラフ
tree = [[] for _ in range(N)]

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

que = deque([])
que.append((0, 0))

while que:
    v, pc = que.popleft()
    c = 1
    for nv, i in tree[v]:
        # print(f"nv{nv}, i{i}")
        if path[i] == 0:
            c = c+1 if c == pc else c
            path[i] = c
            que.append((nv, c))
            c += 1
    # print("path", path)
    # print("que", que)
print(max(path))
print(*path, sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import deque


N = int(input())
edge = [[] for _ in range(N)]
for i, s in enumerate(sys.stdin.readlines()):
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append((b, i))
    edge[b].append((a, i))


path = [None] * (N - 1)
q = deque()
q.append((0, 0))

while q:
    v, pc = q.popleft()
    c = 1
    for nv, i in edge[v]:
        if path[i] is None:
            c = c + 1 if c == pc else c
            path[i] = c
            q.append((nv, c))
            c += 1

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edges=[[]for i in range(n)]
nodes=[None]*n
for i in range(1,n):
    a , b = map(int, input().split())
    edges[a-1].append(i)
    edges[b-1].append(i)
    nodes[i]=(a-1,b-1)
ma =0
for i in range(n):
    ma=max(ma,len(edges[i]))

col=[None]*n
d = deque([(0,0)])
while d:
    t=1
    v , ex_col = d.pop()
    for i in edges[v]:
        if col[i] is None:
            if t==ex_col:
                t+=1
            col[i]=t
            a1,b1=nodes[i]
            if a1==v:
                d.append((b1,t))
            else:
                d.append((a1,t))
            t+=1

print(ma)
for i in range(1,n):
    print(col[i])

Submission status: Accepted

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

n = int(input())
tree = [[] for _ in range(n)]
dic = {}

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

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        before = min(pos, next_pos)
        after = max(pos, next_pos)
        ans_ind = dic[(before, after)]
        if pos < next_pos:
            ans[ans_ind] = color
        else:
            ans[ans_ind] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

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

Submission status: Accepted

Solution code:
n = int(input())

numOfColors = 0
edges = [[] for j in range(n+1)]
ngColor = [-1]*(n+1)
outsI = [[] for j in range(n+1)]
outs = [0]*(n-1)

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

numOfColors = len(edges[1])
for i in range(2, len(edges)):
  numOfColors = max(len(edges[i])+1, numOfColors)

#print(edges)
#print(outsI)

for i in range(len(edges[1])):
  ngColor[edges[1][i]] = i+1
  outs[outsI[1][i]] = i+1
  
queue = []
queue.extend(edges[1])
while queue != []:
  v = queue.pop(0)
  c = 0
  for i in range(len(edges[v])):
    c += 1
    if c == ngColor[v]:
      c += 1
    ngColor[edges[v][i]] = c
    outs[outsI[v][i]] = c
  queue.extend(edges[v])
#print(ngColor)
print(numOfColors)
for out in outs:
  print(out)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]

    node_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        node_data[a].add(b)
        node_data[b].add(a)

    ans_num = 0
    for i in range(1, num + 1):
        ans_num = max(ans_num, len(node_data[i]))

    edge_data = defaultdict(int)
    ans_count = 0

    for i in range(1, num + 1):
        now_list = list(node_data[i])
        now_list.sort()
        count = bisect.bisect_left(now_list, i) + 1

        use_set = set()
        for ele in now_list[:count - 1]:
            use_set.add(edge_data[(i, ele)])
        now_indx = 1

        for ele in now_list[count - 1:]:
            while now_indx in use_set:
                now_indx += 1

            edge_data[(i, ele)] = now_indx
            edge_data[(ele, i)] = now_indx
            use_set.add(now_indx)

        ans_count = max(ans_count, now_indx)

    print(ans_count)
    for i in range(num - 1):
        a, b = data[i]
        ans = edge_data[(a, b)]
        print(ans)








if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

N = int(input())
adj = [[] for _ in range(N)]
degrees = [0 for _ in range(N)]
edges = {}
for i in range(N - 1):
    a, b = map(int, input().split()) 
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    degrees[a] += 1
    degrees[b] += 1
    edges[(a, b)] = i

max_degree = max(degrees)
print(max_degree)

edge_colors = [-1 for _ in range(N - 1)]
visited = [False for _ in range(N)]

def dfs(v, color):
    global max_degree
    if visited[v]:
        return
    visited[v] = True

    next_color = color + 1
    next_color %= max_degree
    for u in adj[v]:
        if visited[u]:
            continue
        if u < v:
            edge_colors[edges[(u, v)]] = next_color
        else:
            edge_colors[edges[(v, u)]] = next_color

        dfs(u, next_color)
        next_color += 1
        # if color == next_color:
        next_color %= max_degree

dfs(0, -1)
for i in range(N - 1):
    print(edge_colors[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
rg = [[] for _ in range(n)]
ret_dict = dict()
ls = []

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


deq = deque()
deq.append((0, 0))

visited = set()
visited.add(0)

ret = 0

while deq:
    head, color = deq.pop()
    n_color = 1
    for item in rg[head]:
        if item not in visited:
            visited.add(item)
            if n_color == color:
                n_color += 1
            ret = max(ret, n_color)
            deq.append((item, n_color))
            ret_dict[(min(head, item), max(head, item))] = n_color
            n_color += 1


print(ret)
for item in ls:
    print(ret_dict[item])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
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])

l = [len(i) for i in edge]
k = max(l)
root = l.index(k)

d = deque()
d.append([root, 0])
res = [0] * (n - 1)
while d:
    node, par_color = d.popleft()
    color = 0
    for e, idx in edge[node]:
        if res[idx] > 0:
            continue

        color += 1
        if color == par_color:
            color += 1
        d.append([e, color])
        res[idx] = color

print(k)
for c in res:
    print(c)

Submission status: Accepted

Solution code:
from queue import Queue
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

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

root = 0
maxdeg = 0
for i in range(1, n + 1):
    if len(adj[i]) > maxdeg:
        maxdeg = len(adj[i])
        root = i

print(str(maxdeg) + '\n')
colors = [i+1 for i in range(maxdeg)]

hashc = {}
q = Queue()
q.put((root, -1, -1))
while not q.empty():
    u, par, col = q.get()
    i = 0
    for child in adj[u]:
        if child == par: continue
        if colors[i] == col: i += 1
        hashc[(u, child)] = colors[i]
        hashc[(child, u)] = colors[i]
        q.put((child, u, colors[i]))
        i += 1

for e in edges:
    print(str(hashc[e]) + '\n')

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

int1 = lambda x: int(x) - 1
edges = [[] for _ in range(N)]
nodes = [None] * N
for i in range(1, N):
    a, b = map(int1, input().split())
    edges[a].append(i)
    edges[b].append(i)
    nodes[i] = (a, b)

# dfs
C = max(len(x) for x in edges)
colors = [None] * N
d = deque([(0, 0)])
while d:
    v, parent_color = d.pop()
    i = 1
    for x in edges[v]:
        if colors[x] is None:
            if i == parent_color:
                i += 1
            colors[x] = i
            a, b = nodes[x]
            d.append((b if a == v else a, i))
            i += 1


print(C)
for i in range(1, N):
    print(colors[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d

"""
import sys


from collections import OrderedDict, deque

def main(args):
    N = int(input())
    G = [[] for _ in range(N+1)]
    res = OrderedDict()
    for _ in range(N-1):
        a, b = map(int, input().split())
        res[(a, b)] = -1
        G[a].append(b)
        G[b].append(a)

    k = max(len(g) for g in G)
    colors = [0 for _ in range(N+1)]
    q = deque([1])
    visited = set([1])
    while q:
        cn = q.popleft()
        color = 1
        for nn in G[cn]:
            if nn not in visited:
                if color == colors[cn]:
                    color += 1
                visited.add(nn)
                q.append(nn)
                c = color
                colors[nn] = color
                color += 1
                if (cn, nn) in res:
                    res[(cn, nn)] = c
                if (nn, cn) in res:
                    res[(nn, cn)] = c
    print(k)
    for v in res.values():
        print(v)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
K = 0
Ans = [0] * (N-1)
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Edge[a].append((b, _))
    Edge[b].append((a, _))

Q = deque()
Q.append((0, 0))
P = [-1] * N
while Q:
    now, color = Q.popleft()
    cnt = 1
    for nex, num in Edge[now]:
        if cnt == color:
            cnt += 1
        if nex == P[now]:
            continue
        if Ans[num] != 0:
            continue
        Q.append((nex, cnt))
        Ans[num] = cnt
        K = max(cnt, K)
        cnt += 1

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
zyun = []
route = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    zyun.append([a,b])
    route[a].append(b)
iro = [0 for i in range(n+1)]
ans = {}
q = deque()
q.append(1)
while q:
    now = q.popleft()
    cou = 1
    for k in route[now]:
        if iro[now] == cou:
            cou += 1
        ans[str(now) + "+" + str(k)] = cou
        iro[k] = cou
        q.append(k)
        cou += 1
print(max(iro))
for i,j in zyun:
    print(ans[str(i)+"+"+str(j)])

Submission status: Accepted

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

def dfs(curr, pare, pare_c, k, color_dic):
    curr_c = pare_c
    for chi in g[curr]:
        if chi == pare: continue
        curr_c = curr_c%k + 1
        color_dic[(curr,chi)] = curr_c
        dfs(chi, curr, curr_c, k, color_dic)


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


k = 0
for node in g:
    k = max(len(node),k)


color_dic = {}
dfs(1, -1, 0, k, color_dic)

print(k)
for edge in gl:
    print(color_dic[edge])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append((b,i))
        adj[b].append((a,i))
    p = max([len(a) for a in adj])
    ans = [-1] * (N-1)
    visited = [-1] * N
    visited[0] = 0
    q = deque([0])
    
    while q:
        now = q.popleft()
        tmp = 0
        for v in adj[now]:
            if visited[v[0]] == 0:
                tmp = ans[v[1]]
                break
        
        for v in adj[now]:
            if visited[v[0]] < 0:
                q.append(v[0])
                ans[v[1]] = (tmp+1) % p
                tmp += 1
                visited[v[0]] = 0
                if ans[v[1]] == 0:
                    ans[v[1]] += p
    print(p)
    [print(a) for a in ans]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
n = int(input())
l = [[] for i in range(n + 1)]
ab = [list(map(int, input().split())) for i in range(n - 1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)
que = deque([1])
p = [-1] * (n + 1)
p[1] = -2
ma = max([len(i) for i in l])
d = defaultdict(int)
print(ma)
while que:
    u = que.popleft()
    x = d[(u, p[u])]
    c = 1
    for v in l[u]:
        if p[v] != -1:
            continue
        p[v] = u
        if c == x:
            c += 1
        d[(u, v)] = d[(v, u)] = c
        c += 1
        que.append(v)
for a, b in ab:
    print(d[(a, b)])

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for i in range(n+1)]
d = {}
l = [-1] * (n-1)
max_idx = 0
for i in range(n-1):
  u,v = map(int, input().split())
  d[(u,v)] = i
  d[(v,u)] = i
  g[u].append((u,v))
  g[v].append((v,u))
  if len(g[max_idx]) < len(g[u]):
    max_idx = u
  if len(g[max_idx]) < len(g[v]):
    max_idx = v
m = len(g[max_idx])
stack = []
count = m
while len(g[1]) > 0:
  u2, v2 = g[1].pop()
  l[d[(u2, v2)]] = count
  count -= 1
  stack.append((u2, v2))

while len(stack) > 0:
  u, v = stack.pop()
  #print(u,v)
  if len(g[v]) > 0:
    count = m
    while len(g[v]) > 0:
      u2, v2 = g[v].pop()
      if count == l[d[(u, v)]]:
        count -= 1
      if l[d[(u2, v2)]] == -1:
        l[d[(u2, v2)]] = count
        count -= 1
        stack.append((u2, v2))
print(m)
for i in range(n-1):
  print(l[i])

Submission status: Accepted

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

from collections import defaultdict
g = defaultdict(list)
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

k = 0
for key in g:
    k = max(k, len(g[key]))
print(k)

ans = dict()
q = [(0, -1)] # (pos, used_color)
visited = set([0])
while q:
    cur, col = q.pop()

    if col == 0:
        tmp = 1
    else:
        tmp = 0

    for target in g[cur]:
        if target not in visited:
            q.append((target, tmp))
            visited.add(target)
            ans[(cur, target)] = tmp

            if tmp + 1 == col:
                tmp += 2
            else:
                tmp += 1

for a, b in ab:
    key = (a-1, b-1)
    print(ans[key] + 1)

Submission status: Accepted

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

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

res = [None] * (N-1)
def dfs(n, c=-1, p=-1):
  if c==-1 or c>1: 
    nc = 1
  else:
    nc = c+1
  for nei,i in adj[n]:
    if nei == p: continue
    res[i] = nc
    dfs(nei, nc, n)
    nc += 1
    if nc==c: nc += 1

dfs(0)
print(max(res))
for r in res: print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

col_max = max([len(row) for row in adj])

cols = defaultdict(int)
s = 1
dq = deque([s])
p = [-1] * (n + 1)
p[s] = -2
while dq:
    u = dq.popleft()
    c_banned = cols[(u, p[u])]
    c = 1
    for v in adj[u]:
        if p[v] != -1:
            continue
        p[v] = u
        if c == c_banned:
            c += 1

        cols[(u, v)] = cols[(v, u)] = c
        c += 1

        dq.append(v)

print(col_max)
for a, b in ab:
    print(cols[(a, b)])