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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    ed = [[] for i in range(n)]
    edg = defaultdict(int)
    ans = [None] * (n - 1)
    for i in range(n - 1):
        a, b = LI_()
        ed[a].append((b, i))
        ed[b].append((a, i))
        edg[a] += 1
        edg[b] += 1
    ma = max(edg.values())
    print(ma)
    for num, a in enumerate(ed):
        if len(a) == ma:
            break
    q = deque([num])
    while q:
        a = q.pop()
        o = 1
        li = defaultdict(int)
        for b, i in ed[a]:
            if ans[i] != None:
                li[ans[i]] = 1
        for b, i in ed[a]:
            if ans[i] == None:
                q.appendleft(b)
                while li[o]:
                    o += 1
                ans[i] = o
                o += 1
    for i in ans:
        print(i)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

N = int(input())
adjL = [[] for _ in range(N)]
edges = []
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append(B)
    adjL[B].append(A)
    edges.append((A, B))

colors = dict()
def dfs(vNow, vPar, color):
    c = 1
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        if c == color:
            c += 1
        A, B = vNow, v2
        if A > B:
            A, B = B, A
        colors[(A, B)] = c
        dfs(v2, vNow, c)
        c += 1

dfs(0, -1, 0)
#print(colors)

anss = []
for A, B in edges:
    anss.append(colors[(A, B)])

print(max(colors.values()))
print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
N = int(input())
ABs = []
E = [set() for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  ABs.append((a, b))
  E[a].add(b)
  E[b].add(a)
K = max([len(s) for s in E])
print(K)
Is = sorted(range(N-1), key=lambda i: ABs[i])
#IIs = [-1]*(N-1)
#for i in Is:
#  IIs[Is[i]] = i
#print(Is)
#print(IIs)
cs = [-1]*(N-1)
V = [-1]*N
for i in range(N-1):
  j = Is[i]
  a, b = ABs[j]
  c = V[a]
  c = (c+1)%K
  V[a] = c
  V[b] = c
  cs[j] = c
#print(cs)
for c in cs:
  print(c+1)

Submission status: Accepted

Solution code:
from queue import  Queue
n = int(input())


class uf_tree():

  def __init__(self, n):
    self.n = n
    self.par = [i for i in range(n)]
    self.rank = [0 for i in range(n)]

  def indep(self):
    dep = 0
    for i in range(self.n):
      if i == self.par[i]:
        dep += 1

    return dep

  def unite(self, x, y):
    if self.root(x) == self.root(y):
      return
    else:
      rootx = self.root(x)
      rooty = self.root(y)
      if self.rank[rootx] < self.rank[rooty]:
        self.par[rootx] = rooty
      else:
        self.par[rooty] = rootx
        if self.rank[rootx] == self.rank[rooty]:
          self.rank[rootx] += 1

  def root(self, i):
    if self.par[i] == i:
      return i
    else:
      self.par[i] = self.root(self.par[i])
      return self.par[i]

  def same(self, x, y):
    return self.root(x) == self.root(y)

tree = uf_tree(n)

edges = {}
arr = [0 for i in range(n-1)]
dic = {}

for i in range(n-1):
  a,b = map(int,input().split())
  dic[str(a-1)+","+str(b-1)] = i
  dic[str(b - 1) + "," + str(a - 1)] = i
  if a-1 in edges:
    edges[a-1].append(b-1)
  else:
    edges[a-1] = [b-1]
  if b-1 in edges:
    edges[b - 1].append(a - 1)
  else:
    edges[b - 1] = [a - 1]
  tree.unite(a-1,b-1)

root = tree.root(0)
que = []
que.append([root,0])
visited = set()
visited.add(root)
# print(root)
# print(edges)
while not len(que)==0:
  top = que[-1]
  que.pop()
  v = top[0]
  col = top[1]
  color = 1
  if v in edges:
    nex = edges[v]
  else:
    continue
  nc = []
  # print(v)
  # print(nex)
  for i in range(len(nex)):
    if nex[i] in visited:
      continue
    else:
      visited.add(nex[i])
    if col != color:
      # nc.append(color)
      que.append([nex[i],color])
      arr[dic[str(v)+","+str(nex[i])]] = color
      color += 1
    else:
      # nc.append(color+1)
      arr[dic[str(v)+","+str(nex[i])]] = color+1
      que.append([nex[i],color+1])
      color += 2

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
input = sys.stdin.readline
INF = 10**9

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

colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))
    if len(line) == 1:
        start = i
print(colors)

dq = deque()
dq.append((i, -1, -1))

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

while dq:
    v, prev, prev_c = dq.popleft()
    c = 0
    for dest, index in edge[v]:
        if dest == prev:
            continue
        if c == prev_c:
            c += 1
        color[index] = c 
        dq.append((dest, v, c))
        c += 1
for item in color:
    print(item + 1)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = rils(n - 1)
temp = []
for a, b in ls:
    if a > b:
        a, b = b, a
    temp.append((a - 1, b - 1))
ls = temp

edges = collections.defaultdict(list)
for i, (a, b) in enumerate(ls):
    edges[a].append((b, i))

colors = [-1] * n
colors[0] = (0, 0)

q = collections.deque()
q.append((0, 0))
while q:
    node, i0 = q.popleft()
    c = 1
    for next_, i in edges[node]:
        if colors[next_] != -1:
            continue
        if colors[node][0] == c:
            c += 1
            colors[next_] = (c, i)
        else:
            colors[next_] = (c, i)
        c += 1
        q.append((next_, i))
colors = [c for c, i in sorted(colors, key=lambda x: x[1])]
print(max(colors))
for c in colors[1:]:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add((b-1, i))
    ans = [0] * (N-1)
    q = deque([])
    q.append((0, -1))
    while len(q):
        cur, used = q.popleft()
        idx = 0
        for nxt, edge in adj[cur]:
            idx += 1
            if idx == used:
                idx += 1
            if ans[edge] != 0:
                continue
            ans[edge] = idx
            q.append((nxt, idx))
    mx = max(ans)
    print(mx)
    for i in range(N-1):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

v_color = [0] * N
e_color = [0] * (N-1)
K = 1
for a, children in enumerate(G):
    c = 1
    for b, i in children:
        if c == v_color[a]:
            c += 1
        v_color[b] = c
        e_color[i] = c
        K = max(K, c)
        c += 1

print(K)
print('\n'.join(map(str, e_color)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N = I()
a,b = Line(N-1,2)
d = defaultdict(int)

pt = edges_to_pt(a,b,N)
for i in range(N-1):
    x = min(a[i],b[i])
    y = max(a[i],b[i])
    d[(x-1)*N+(y-1)] = i

ans = [0]*(N-1)
used = [False]*N
used[0] = True

color = [0]*N
q = [0]
c = 1
while q:
    q1 = []
    for i in q:
        c = 1
        for j in pt[i]:
            if used[j]==False:
                if c==color[i]:
                    c += 1
                color[j] = c
                used[j] = True
                ans[d[min(i,j)*N+max(i,j)]] = c
                c += 1
                q1.append(j)
    q = q1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n=int(input())
edgecolor=[0]*(n-1)
nodecolorset=[set() for i in range(n)]
G=[[]*n for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append((b,i))
    G[b].append((a,i))

def dfs(node,color):
    i=1
    for gi,edgenum in G[node]:
        if edgecolor[edgenum]:continue
        if i!=color:
            edgecolor[edgenum]=i
        else:
            i+=1
            edgecolor[edgenum]=i
        dfs(gi,i)
        i+=1
# print(G)
# edgecolor[0]=1
dfs(0,0)
print(max(edgecolor))
for ci in edgecolor:
    print(ci)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
P = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    P[a-1].append((b-1, i))
    P[b-1].append((a-1, i))
ans = [0] * N
q = deque()
q.append((0, 0))
colmax = 0
while q:
    u, pcol = q.popleft()
    icol = 1
    for v, i in P[u]:
        if ans[i] != 0:
            continue
        if icol == pcol:
            icol += 1
        ans[i] = icol
        q.append((v, icol))
        colmax = max(colmax, icol)
        icol += 1

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

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.color = defaultdict(int)
		self.precolor = [None] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			self.c = 0
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.c += 1
					if self.c == self.precolor[v]:
						self.c += 1
					x, y = sorted([i, v])
					self.color[100000 * x + y] = self.c
					self.precolor[i] = self.c
					self.Q.put(i)
					self.visit[i] = "Yes"


#処理内容
def main():
	N = int(input())
	G = Graph()
	S = []
	for i in range(N - 1):
		a, b = getlist()
		a, b = sorted([a, b])
		G.add_edge(a - 1, b - 1)
		G.add_edge(b - 1, a - 1)
		S.append([a - 1, b - 1])
	BF = BFS(G, 0, N)
	D = BF.color
	#print(D)
	ans = []
	d = defaultdict(int)
	for i in range(N - 1):
		a = S[i][0]
		b = S[i][1]
		ans.append(D[100000 * a + b])
		d[D[100000 * a + b]] += 1
	print(len(d))
	for i in range(N - 1):
		print(ans[i])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

G = {k: [] for k in range(N+1)}
for n in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append((b, n))
    G[b].append((a, n))

ans = 1
ans_l = [-1]*(N-1)
que = deque([(1, -1, -1)])

while que:
    ci, pi, ec = que.popleft()
    c = 0

    for ni, n in G[ci]:
        if ni != pi:
            c += 1
            if c == ec:
                c += 1
            ans = max(ans, c)
            que.append((ni, ci, c))
            ans_l[n] = c

print(ans)
print(*ans_l, sep='\n')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

g = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    d[(a-1,b-1)] = i
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 

def dfs(v,p,j): #p: parent of v
    """
    vでの操作をここに
    """
    num = -1
    for c in g[v]:
        if c == p: continue
        num += 1
        col = (j+num)%m+1
        if c > v: ans[d[(v,c)]] = col
        else: ans[d[(c,v)]] = col
        dfs(c,v,col)

m = max(len(i) for i in g)
ans = [0]*(n-1)

dfs(0,-1,0)

#print(g,m,ans)
print(m)
print(*ans,sep = "\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
from operator import itemgetter
from heapq import heappop, heappush
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N = int(input())
M = []
D = {}

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

for i in range(N-1):
    a, b = inpl()
    D[(a, b)] = i
    D[(b, a)] = i
    G[a].append(b)
    G[b].append(a)

K = max(map(len, G))

used = [set() for _ in range(N+1)]
ans = [0]*(N-1)
Q = deque([1])
searched = [0]*(N+1)
searched[1] = True

while Q:
    p = Q.popleft()
    i = 0
    for q in G[p]:
        if ans[D[(p, q)]]:
            continue
        while True:
            i += 1
            if (i in used[p]) or (i in used[q]):
                continue
            ans[D[(p, q)]] = i
            used[p].add(i)
            used[q].add(i)
            if not searched[q]:
                searched[q] = True
                Q.append(q)
            break

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.edges = []


class Edge(object):

  def __init__(self):
    self.color = -1


def main():
  nodes = [Node() for _ in range(int(input()))]
  edges = [Edge() for _ in range(len(nodes) - 1)]

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

  queue = collections.deque()
  node = nodes[0]

  for i in range(len(node.edges)):
    node.edges[i][0].color = i
    queue.append(node.edges[i][1])

  max_color = len(node.edges) - 1

  while len(queue) != 0:
    node = queue.popleft()
    exist = -1
    index = 0

    for i in range(len(node.edges)):
      if node.edges[i][0].color != -1:
        exist = node.edges[i][0].color
        break

    for i in range(len(node.edges)):
      if index == exist:
        index += 1

      if node.edges[i][0].color != -1:
        continue

      node.edges[i][0].color = index
      index += 1
      queue.append(node.edges[i][1])

    max_color = max(len(node.edges) - 1, max_color)

  print(max_color + 1)
  for e in edges:
    print(e.color + 1)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

K = max(len(S) for S in ad)
d = dict()

def dfs(v=0, pv=-1, memo=-1):
    color = 0
    for nv in ad[v]:
        if nv == pv:
            continue
        if color == memo:
            color += 1
        d[(v, nv)] = color
        d[(nv, v)] = color
        dfs(nv, v, color)
        color += 1

dfs()

print(K)
for e in edge:
    print(d[e]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    N = read_int()
    E = []
    G = [dict() for _ in range(N)]

    for _ in range(N - 1):
        a, b = read_ints()
        a -= 1
        b -= 1
        E.append((a, b))
        G[a][b] = -1
        G[b][a] = -a

    K, C = solve(N, E, G)
    print(K)
    for c in C:
        print(c + 1)


def solve(N, E, G):
    K = max([len(d) for d in G])

    q = [(-1, 0)]
    while q:
        p, i = q.pop()

        used = -1
        if p != -1:
            used = G[p][i]

        c = 0
        for j in G[i]:
            if j == p:
                continue
            if c == used:
                c += 1
            G[i][j] = c
            G[j][i] = c
            q.append((i, j))
            c += 1

    C = [-1] * len(E)
    for i, (a, b) in enumerate(E):
        C[i] = G[a][b]
    return K, C


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
l = []
edge = [[] for i in range(N)]
idx = {}
for i in range(N-1):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	edge[a].append([b,None])
	edge[b].append([a,None])
	l.append((a,b))
	idx[(a,b)] = len(edge[a]) - 1

search = [(0,0)]
searched = [False for i in range(N)]
col_max = 1
while len(search) > 0:
	s = search.pop()
	n = s[0]
	c = s[1]
	searched[n] = True
	color = 1
	for e in edge[n]:
		if not searched[e[0]]:
			if color == c:
				color += 1
			e[1] = color
			col_max = max(col_max, color)
			search.append((e[0], color))
			color += 1
print(col_max)
for e in l:
	a,b = e[0], e[1]
	print(edge[a][idx[(a,b)]][1])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(100000)

N = int(input())

adj = [list() for _ in range(N)]

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


res = [None]*(N-1)

C = max(len(l) for l in adj)

def rec(v, used):
    global res
    c = 0
    for u,i in adj[v]:
        if c == used:
            c += 1
        if res[i] is None:
            res[i] = c
            rec(u, c)
            c += 1
rec(0, -1)
print(C)
for c in res:
    print(c+1)

Submission status: Accepted

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

N = int(input())
graph = [[] for _ in range(N)]
Ed = {}
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Ed[(a-1)*N+b-1] = i
    Ed[(b-1)*N+a-1] = i

q = [0]
checked = [False]*N
checked[0] = True

V_color = [None]*N
V_color[0] = 0

ans = [None]*(N-1)
while q:
    qq = []
    for p in q:
        c = V_color[p]
        t = 1
        for np in graph[p]:
            if not checked[np]:
                checked[np] = True
                qq.append(np)
                ind = Ed[p*N+np]
                if t == c:
                    t += 1
                ans[ind] = t
                V_color[np] = t
                t += 1
    q = qq

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

Submission status: Accepted

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

#入力
N = int(input())
AB = [0] * (N + 1) #答えの色
G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    G[a].append((b, i))
    G[b].append((a, i))

check = [[0, 0] for _ in range(N + 1)] #[[チェック、親と繋いでいる色]]
check[1][0] = 1
ans = 0
stack = [1]
while len(stack) != 0:
    tmp = stack.pop()
    color = 1
    for g, i in G[tmp]:
        if check[g][0] == 1: #すでに確認済みの時
            continue
        if color == check[tmp][1]:
            color += 1
        AB[i] = color
        check[g][0] = 1
        check[g][1] = color
        color += 1
        stack.append(g)

K = max(AB)
print (K)
print (*AB[:N - 1], sep = '\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = LI()
    G[a - 1] += [(i, b - 1)]
    G[b - 1] += [(i, a - 1)]


k = 0
for i in G:
    k = max(k, len(i))


col_set = set(range(1, k + 1))
ans = [0] * (n - 1)
visited = [0] * n
visited[0] = 1
dq = deque([(0, 0)])
while dq:
    u, pre_col = dq.popleft()
    col = 1
    for i, v in G[u]:
        if not visited[v]:
            visited[v] = 1
            if pre_col == col:
                col += 1
            ans[i] = col
            dq += [(v, col)]
            col += 1


print(k)
for j in ans:
    print(j)

Submission status: Accepted

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

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

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

ret = [0] * (N - 1)

def dfs(pre, cur, color) :
    i = 1
    for nex, j in v[cur] :
        if nex != pre :
            if i == color :
                i += 1
            ret[j] = i
            dfs(cur, nex, i)
            i += 1

dfs(-1, 0, 0)

print(max(ret))
for r in ret :
    print(r)

Submission status: Accepted

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

R = {}
for a, b in ab:
  a -= 1
  b -= 1
  if a not in R:
    R[a] = [b]
  else:
    R[a].append(b)
  if b not in R:
    R[b] = [a]
  else:
    R[b].append(a)

D = [0] * N
S = [[0, 0]] 
D[0] = 1
C = {}
m = 0
while S != []:
  t, c = S.pop()
  n = 1
  if c == n:
    n += 1
  m = max(m, len(R[t]))
  for i in R[t]:
    if D[i] == 0:
      D[i] = D[t] + 1
      S.append([i, n])
      if t not in C:
        C[t] = {}
        C[t][i] = n
      else:
        C[t][i] = n
      if i not in C:
        C[i] = {}
        C[i][t] = n
      else:
        C[i][t] = n
      n += 1
      if c == n:
        n += 1

print(m)
for a, b in ab:
  a -= 1
  b -= 1
  print(C[a][b])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**5+1)
readline = sys.stdin.readline
N, = map(int, readline().split())
G = [[] for _ in range(N+1)]
ees = dict()
for v in range(N-1):
    a, b = map(int, readline().split())
    G[a].append(b)
    G[b].append(a)
    ees[v+1] = tuple([min(a,b), max(a,b)])
cd = dict()
cd[1] = 0
ed = dict()

def itree(v, p):
    cdd = 1
    for c in G[v]:
        if c == p:
            continue
        if cdd == cd[v]:
            cdd += 1
        cd[c] = cdd
        ed[tuple([min(c,v), max(c,v)])] = cdd
        cdd += 1
        itree(c, v)


def process():
    itree(1,0)
process()
xs = []
for i in range(N-1):
    xs.append(ed[ees[i+1]])
print(max(xs))
print("\n".join(map(str,xs)))

Submission status: Accepted

Solution code:
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
ei = {}
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
    ei[(a,b)] = ei[(b,a)] = i

max_e = root = 0
for i in range(N):
    if len(es[i]) > max_e:
        max_e = len(es[i])
        root = i

ans = [None]*(N-1)
visited = [0]*N
visited[root] = 1
stack = []
for i,to in enumerate(es[root]):
    ans[ei[(root,to)]] = i+1
    visited[to] = 1
    stack.append((to,i+1))

while stack:
    v,pc = stack.pop()
    c = 0
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        c += 1
        if c == pc:
            c += 1
        pi = ei[(v,to)]
        ans[pi] = c
        stack.append((to,c))

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

n = int(input())
edge = [[] for i in range(n)]
a = [0] * n
b = [0] * n

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):
    global k
    color = 1
    for to in edge[x]:
        if to == last:continue
        if color == ban_color:color += 1
        color_dict[(x, to)] = color
        dfs(to, x, color)
        color += 1
    k = max(k, color-1)

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


dfs(0)
print(k)

for i in range(n-1):
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

n = int(input())
g = [list() for _ in range(n)]
edge = list()
d = dict()
for _ in range(n-1):
    a,b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
    if a > b:
        a,b = b,a
    edge.append((a,b))
k = max(len(g[i]) for i in range(n))

q = [(0,-1,-1)]
while q:
    v,p,c = q.pop()
    cc = 1
    for x in g[v]:
        if x == p:
            continue
        if cc == c:
            cc += 1
        if v < x:
            d[(v,x)] = cc
        else:
            d[(x,v)] = cc
        q.append((x,v,cc))
        cc += 1
print(k)
for x in edge:
    print(d[x])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for i in range(N)]
    e_index = []
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
        e_index.append((a,b))
    queue = deque()
    queue.append((0,0))
    ans_col = {}
    visited = set()
    K=1
    while queue:
        from_,col = queue.popleft()
        if from_ in visited:
            continue
        visited.add(from_)
        now = 1
        for to in edge[from_]:
            if to in visited:
                continue
            if now == col:
                now += 1
            ans_col[from_,to] = now
            ans_col[to,from_] = now
            queue.append((to,now))
            K = max(now,K)
            now += 1
    print(K)
    for a,b in e_index:
        print(ans_col[a,b])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

dic = {}
color = 0

for i in range(N-1):

    a,b = map(int,input().split())

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

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

    color = max(color,len(dic[a]),len(dic[b]))

print (color)

q = deque([[1,float("inf")]])
clis = [0] * (N-1)

while len(q) > 0:

    #print (q)
    now = q.popleft()
    np = now[0]
    ducolor = now[1]
    

    ncolor = 1
    for i in range(len(dic[np])):

        j = i
        if ncolor == ducolor:
            ncolor += 1

        nexp = dic[np][j][0]
        hen = dic[np][j][1]
        if clis[hen] == 0:
            clis[hen] = ncolor
            q.append([nexp,ncolor])
            ncolor += 1

for i in range(N-1):
    print (clis[i])