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

#+++++
		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	for i in range(n-1):
		a, b = map(int, input().split())
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
	
	bb=max([len(t) for t in ttt])	
	print(bb)
	
	ret_ll=[0]*(n-1)
	ss_stack=[(0,-1, bb+100)]
	#state, parent, parent_path_color
	
	while len(ss_stack) > 0:
		st, parent, pp_color = ss_stack.pop()
		
		current_color=1
		if current_color==pp_color:
			current_color+=1
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to == parent:
				continue
			
			c_color = current_color
			current_color+=1
			if current_color==pp_color:
				current_color+=1
			
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
def coloring2(color,p):
    global K
    dcolor = 1
    for c in Data[p]:
        if dcolor == color:
            dcolor += 1
        s = str(p)+'_'+str(c)
        Edge[s] = dcolor 
        coloring2(dcolor,c)
        dcolor += 1
    K = max(K,dcolor-1)

sys.setrecursionlimit(10 ** 9)
N = int(input())
Data = [ [] for _ in range(N+1) ]
Edge = {} 
Edge2 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    Data[a].append(b)
    s = str(a)+'_'+str(b)
    Edge[s] = 0
    Edge2.append([a,b])

K = 0
coloring2(0,1)
print(K)
for [a,b] in Edge2:
    s = str(a)+'_'+str(b)
    print(Edge[s])

Submission status: Accepted

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

n = int(input())
edges = [tuple([int(i) for i in input().split()]) for _ in range(n - 1)]
graph = [0] + [[] for _ in range(n)]

for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

max_color_index = 1
def bfs(graph, dist, queue, parent_colors, color_map):
    global max_color_index
    while queue:
        parent = queue.pop(0)
        children = graph[parent]

        color_index = 1
        for child in children:
            if dist[child] != -1:
                continue

            # 親との辺の色と重なった場合、一個進める
            # それ以外は1から順に埋めていく
            if parent_colors[parent] == color_index:
                color_index += 1

            e = (min(child, parent), max(child, parent))
            if e not in color_map:
                color_map[e] = color_index

            parent_colors[child] = color_index
            color_index += 1

            dist[child] = dist[parent] + 1
            queue.append(child)

        # 実際に使ったindexより1つ進んでいる
        max_color_index = max(max_color_index, color_index - 1)

dist = [0] + [-1] * n
dist[1] = 0
queue = [1]
parent_color = [0] * (n + 1)
color_map = {}
bfs(graph, dist, queue, parent_color, color_map)

print(max_color_index)
for e in edges:
    print(color_map[e])

Submission status: Accepted

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

n = int(input())
edges = [tuple([int(i) for i in input().split()]) for _ in range(n - 1)]
graph = [0] + [[] for _ in range(n)]

for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

max_color_index = 1
def bfs(graph, dist, queue, parent_colors, color_map):
    global max_color_index
    while queue:
        parent = queue.pop(0)
        children = graph[parent]

        color_index = 1
        for child in children:
            if dist[child] != -1:
                continue

            # 親との辺の色と重なった場合、一個進める
            # それ以外は1から順に埋めていく
            if parent_colors[parent] == color_index:
                color_index += 1

            e = (min(child, parent), max(child, parent))
            if e not in color_map:
                color_map[e] = color_index

            parent_colors[child] = color_index
            color_index += 1

            dist[child] = dist[parent] + 1
            queue.append(child)

        # 実際に使ったindexより1つ進んでいる
        max_color_index = max(max_color_index, color_index - 1)

dist = [0] + [-1] * n
dist[1] = 0
queue = [1]
parent_color = [0] * (n + 1)
color_map = {}
bfs(graph, dist, queue, parent_color, color_map)

print(max_color_index)
for e in edges:
    print(color_map[e])

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

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))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)

Submission status: Accepted

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

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [[] for _ in range(N+1)]    

    for i in range(N-1):
        h[a[i]].append(b[i])
        h[b[i]].append(a[i])

    queue = deque([1])

    ## 頂点iの親を格納
    parents = [0]*(N+1)
    order = []

    while queue:
        q = queue.pop()
        order.append(q)

        for child in h[q]:
            if child == parents[q]:
                continue

            parents[child] = q
            queue.append(child)

    ## 頂点i と親nodeの間のcolor
    color = [0]*(N+1)

    for o in order:
        ng_color = color[o]
        cur_color = 1

        for node in h[o]:
            if node == parents[o]:
                continue

            if cur_color == ng_color:
                cur_color += 1
            
            color[node] = cur_color
            cur_color += 1


    answer = []
    append = answer.append
    for i in range(N-1):
        if parents[a[i]] == b[i]:
            append(color[a[i]])
        else:
            append(color[b[i]])

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

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def dfs(v, c=-1, p=-1):
    k = 1
    for nv, ei in edges[v]:
        if nv == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(nv, ans[ei], v)

ans = [None]*(n-1)
dfs(0)

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

Submission status: Accepted

Solution code:
# 2019-11-24 20:59:47(JST)
import sys

def main():
    n = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())
    ab = list(zip(m, m)) # 2回以上使えるようにlist化

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

    root = 1
    parent = [None] * (n + 1)
    # treeなのでループがないため、parentが定義できる
    checked = []
    to_check = [root]
    # dfs: depth first search では stack
    # bfs: breadth first search では queueを使う
    # 今回は stack

    while to_check:
        x = to_check.pop()
        # stackから要素を取り除き、xにset
        for y in graph[x]: # xから直接つながっているverticesについて
            if y == parent[x]: 
                continue
            # yがxの親でなければ
            parent[y] = x # xを親にして
            to_check.append(y) # 子であるyをto_checkにstackしていく
        checked.append(x) # 探索が終わったらvertexを記録

    color = [None] * (n + 1) # 初期状態ではなにも塗らないのがNG
    # vertexに色を、色1から始めて一つ塗ったら色2, 色3,...と変えて塗っていく
    # その際、色iがngだったらその色iを跳ばして色i+1,色i+2,...と塗っていく(ngは親の色)
    for x in checked: # checkされた順になっている
        ng = color[x]
        c = 1
        for y in graph[x]:
            if y == parent[x]:
                continue
            if c == ng:
                c += 1
            color[y] = c 
            c += 1

    res = []
    for a, b in ab:
        if a == parent[b]:
            res.append(color[b])
        else: # 木なので parent[a] == b
            res.append(color[a])

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 2019-11-24 20:59:47(JST)
import sys

def main():
    n = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())
    ab = list(zip(m, m)) # 2回以上使えるようにlist化

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

    root = 1
    parent = [None] * (n + 1)
    # treeなのでループがないため、parentが定義できる
    checked = []
    to_check = [root]
    # dfs: depth first search では stack
    # bfs: breadth first search では queueを使う
    # 今回は stack

    while to_check:
        x = to_check.pop()
        # stackから要素を取り除き、xにset
        for y in graph[x]: # xから直接つながっているverticesについて
            if y == parent[x]: 
                continue
            # yがxの親でなければ
            parent[y] = x # xを親にして
            to_check.append(y) # 子であるyをto_checkにstackしていく
        checked.append(x) # 探索が終わったらvertexを記録

    color = [-1] * (n + 1) # 初期は0でもいいが、あえてngであることがわかりやすいように-1にしている
    for x in checked: # checkされた順になっている
        ng = color[x] # 最初は-1, colorは1からなので最初はngにはならない
        c = 1
        for y in graph[x]:
            if y == parent[x]:
                continue
            if c == ng:
                c += 1
            color[y] = c
            c += 1

    res = []
    for a, b in ab:
        if a == parent[b]:
            res.append(color[b])
        else: # 木なので parent[a] == b
            res.append(color[a])

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 2019-11-24 20:59:47(JST)
import sys

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

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

    root = 1
    parent = [0] * (n + 1)
    order = []
    stack = [root]

    while stack:
        x = stack.pop()
        order.append(x)
        for y in graph[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)

    color = [-1] * (n + 1)
    for x in order:
        ng = color[x]
        c = 1
        for y in graph[x]:
            if y == parent[x]:
                continue
            if c == ng:
                c += 1
            color[y] = c
            c += 1

    res = []
    for a, b in ab:
        if parent[a] == b:
            res.append(color[a])
        else:
            res.append(color[b])

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

while len(q) > 0:
    (c, n), ac = q.popleft(), 1
    for l, i in P[n]:
        if ac == c:
            ac += 1
        q.append((ac, l))
        ans[i] = ac
        ac += 1

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())

graph = [[] for _ in range(N + 1)]
 
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
 
color = [0] * (N + 1)
queue = deque([1])
 
while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1
 
print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])

while stack:
    a=stack.popleft()
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        P[b].remove(a)
    P[a].clear()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=[[] for i in range(n)]
d=[]
for i in range(n-1):
  c[l[i][0]-1].append(l[i][1]-1)
  c[l[i][1]-1].append(l[i][0]-1)
for i in range(n):
  d.append(len(c[i]))
print(max(d))
dmax=d.index(max(d))

def bfs(v):
  child=[[] for i in range(n)]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  colorL=[set() for i in range(n)]
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        color=0
        for j in range(len(c[next[i]])):
          if visited[c[next[i]][j]]==-1:
            color+=1
            while color in colorL[next[i]]:
              color+=1
            child[next[i]].append((c[next[i]][j],color))
            next2.add(c[next[i]][j])
            colorL[c[next[i]][j]].add(color)
    next=list(next2)
    next2=set()
  return child

bfs=bfs(dmax)
ans={}
for i in range(n):
  for j in range(len(bfs[i])):
    ans[min(bfs[i][j][0],i)+1,max(bfs[i][j][0],i)+1]=bfs[i][j][1]

for i in range(n-1):
  print(ans[l[i][0],l[i][1]])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    a=stack.popleft()
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        P[b].remove(a)
    P[a].clear()


print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)


def f(a, b):
    return (a, b) if a < b else (b, a)


def dfs(s, p):
    used = {}
    for t in g[s]:
        idx = rev[f(s, t)]
        if ans[idx] > 0:
            used[ans[idx]] = True 
    c = 1
    for t in g[s]:
        idx = rev[f(s, t)]
        if t == p or ans[idx] > 0:
            continue
        while c in used:
            c += 1
        ans[idx] = c
        c += 1
        dfs(t, s)
        

n = int(input())
g = [[] for _ in range(n)]
rev = {}
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    g[a].append(b)
    g[b].append(a)
    rev[(a, b)] = i
ans = [0] * (n - 1)
dfs(0, -1)
print(max(ans), *ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    #print(C)
    #print(Cpath,"Cpath")
    a=stack[0]
    count=1
    for b in P[a]:
        #b=P[a][-1]
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        #P[a].remove(b)
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Submission status: Accepted

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)
    init = -1
    display_order = []

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

    q = deque()
    q.append((1, 0))
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx, color = q.popleft()
        nxt = graph[idx]
        cnt = 1
        # print('visiting', nxt)
        for e in nxt:
            if colors[e] == -1 and not visited[e]:
                if cnt == color:
                    cnt += 1
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1
                else:
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1

    print(max(colors))
    # print(*colors)
    # print(*display_order)
    for i in display_order:
        # print(i)
        print(colors[i+1])
    # for i in range(2, len(colors)):
    #     print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i)-1 for i in input().split()])

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0]].append(row[1])
    link_list[row[1]].append(row[0])
edge_color = dict()
marker = [0] * N


def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1, node2])

Submission status: Accepted

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

n=int(input())
# n=100000
tree=[set() for i in range(n)]
edges=[tuple(map(int,input().split())) for i in range(n-1)]
edge_color={}
for a,b in edges:
    a-=1
    b-=1
    tree[a].add(b)
    tree[b].add(a)
k = 0
for i in range(n):
    k = max(k,len(tree[i]))

for a,b in edges:
    edge_color[(a-1,b-1)] = 0

def colorize(u,v,c,init=False):
    if not init:
        edge_color[(min(u,v),max(u,v))] = c
    cc = c+1
    if cc > k:
        cc = 1
    for x in tree[u]:
        if edge_color[(min(x,u),max(x,u))] == 0:
            colorize(x,u,cc)
            cc += 1
            if cc > k:
                cc = 1

colorize(0,1,1,True)
print(k)
for a,b in edges:
    print(edge_color[(a-1,b-1)])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read


n, *ab = map(int, read().split())
ans = [0]*(n-1)
edges = [[]for _ in range(n)]
used = [0]*n

for i, a, b in zip(range(n-1), *[iter(ab)] * 2):
    edges[a-1].append([b-1, i])

for node in range(n):
    unable = used[node]
    color = 1

    for to, id in edges[node]:
        if color == unable:
            color += 1
        ans[id] = str(color)
        used[to] = color
        color += 1

print(max(used))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
n=int(input())
edges=[]
relations={}
nodes=[0,0]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    relations.setdefault(a,[]).append(b)
    nodes.append(0)

max_color=0
for start in range(1,n+1):
    targets=relations.get(start,[])
    color=1
    for target in targets:
        if color == nodes[start]:
            color+=1
        else:
            pass
        nodes[target]=color
        if color>=max_color:
            max_color=color
        color+=1

print(max_color)
for edge in edges:
    print(nodes[edge[1]])

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
from sys import getrecursionlimit,setrecursionlimit
setrecursionlimit(100*getrecursionlimit())
G = defaultdict(list)
C = Counter()
N = int(input())
ans = {}
o = []
for i in range(N-1):
    a, b = map(int, input().split())
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

a = C.most_common(1)[0][0]
b = C.most_common(1)[0][1]

visited = [False] * (N+1)
def dfs(v, p):
    visited[v] = True
    counter = 1
    for c in G[v]:
        if not visited[c]:
            if p != 0 and counter == ans[(v, p)]:
                counter += 1
            ans[(v, c)] = ans[(c, v)] = counter
            counter += 1
            dfs(c, v)

dfs(a, 0)

print(b)
for a,b in o:
    print(ans[(a,b)])

Submission status: Accepted

Solution code:
import copy

n=int(input())
org_set=set([i for i in range(1,10**5)])
edges=[]
relations={}
nodes=[]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    relations.setdefault(a,[]).append(b)
    nodes.append([])
nodes.append([])
nodes.append([])

max_color=0
for start in range(1,n+1):
    targets=relations.get(start,[])
    color=1
    for target in targets:
        if color in nodes[start]:
            color+=1
        else:
            pass
        nodes[target].append(color)
        if color>=max_color:
            max_color=color
        color+=1

print(max_color)
for edge in edges:
    print(nodes[edge[1]][0])

Submission status: Accepted

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


n = int(input())
ans = [0]*(n-1)
edges = [[]for _ in range(n)]
used = [0]*n

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

for node in range(n):
    unable = used[node]
    color = 1

    for to, id in edges[node]:
        if color == unable:
            color += 1
        ans[id] = color
        used[to] = color
        color += 1

print(max(used))
for color in ans:
    print(color)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    color=[-1]*n
    color[0]=0
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    d=[-1]*n
    d[0]=0
    q=[0]
    cnt=0
    while q:
        qq=[]
        cnt+=1
        while q:
            i=q.pop()
            for j in g[i]:
                if d[j]==-1:
                    d[j]=cnt
                    qq.append(j)
        q=qq
    print(max(color[1:]))
    for i,j in ab:
        if d[i-1]>d[j-1]:
            k=i
        else:
            k=j
        print(color[k-1])
main()

Submission status: Accepted

Solution code:
N = int(input())
edge = {}
tree = [[] for i in range(N)]
colors = [1]*(N-1)
c_p = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    tree[a].append(b)
    edge[(a,b)] = i

for i in range(N):
    c = 1
    for v_c in tree[i]:
      while c in c_p[i]: c+=1
      colors[edge[(i,v_c)]] = c
      c_p[v_c].append(c)
      c+=1

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

Submission status: Accepted

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

N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

# make graph
# graph(x): xと繋がっている頂点（番号）のリスト
graph = [[] for _ in range(N+1)]
for a,b in AB:
  graph[a].append(b)
  graph[b].append(a)

# 深さ優先探索で、頂点の探索順序を作成
root = 1
parent = [0] * (N+1) # parent[x]: xの親の番号
order = [] # 深さ優先探索の順序リスト
stack = [root]
while stack:
  x = stack.pop()
  order.append(x)
  for y in graph[x]:
    if y == parent[x]:
      continue
    parent[y] = x
    stack.append(y)

# color[i]: 頂点iとその親の間の辺の色
color = [-1] * (N+1)

# 頂点の探索順ごとに、頂点とその子の間の辺の色を決定
for x in order:
  ng = color[x] # 頂点xとxの親との間の辺の色
  c = 1
  # 頂点xとつながっている頂点のリストを取得し、辺の色を1から順に割り当てる
  for y in graph[x]:
    if y == parent[x]: # xの親の頂点の場合は何もしない
      continue
    if c == ng: # xとその親との間の辺の色は割り当てないようにする
      c += 1
    color[y] = c
    c += 1

# 回答作成
answer = []
for a,b in AB:
  # aがbの子ならcolor[a]を、逆の場合はcolor[b]を出力する
  if parent[a] == b:
    answer.append(color[a])
  else:
    # 今回の場合、a_i < b_iで、番号の小さい方が親になるように木を作っているので、
    # こちらの条件のほうにしか引っかからないはず
    answer.append(color[b])

K = max(answer) # 色の番号の中で最も大きいものがK
print(K)
print('\n'.join(map(str,answer)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC146 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    graph[a].append((b,i))
    graph[b].append((a,i))
    edge.append((a,b,i))

m = 0
for i in range(n):
    m = max(m,len(graph[i]))

print(m)
ans = [None]*(n-1)
que = deque()
que.append((0,0))
while que:
    v,color = que.popleft()
    cnt = 1
    for u,i in graph[v]:
        if ans[i] == None:
            if cnt != color:
                ans[i] = cnt
                que.append((u,cnt))
                cnt += 1
            else:
                ans[i] = cnt+1
                que.append((u,cnt+1))
                cnt += 2
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

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

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Accepted

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

N = int(input())

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

# print(E)
# print(T)



R = [None for i in range(N)]
def dfs(using, cur):
    R[cur] = using
    i=0
    for t in T[cur]:
        if i==using:
            i+=1
        dfs(i,t)
        i+=1


dfs(-1, 0)

print(max(R)+1)
# print(K)
for e in E:
    print(R[e[1]]+1)

# print(K)

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

q = collections.deque([(id, 0)])
print(max_e)
d = dict()
for a, b in ab:
    d[(a-1, b-1)] = 0
    d[(b-1, a-1)] = 0
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        d[(x, y)] = i
        d[(y, x)] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

for a, b in ab:
    print(d[(a-1, b-1)])