Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

Solution code:
from collections import deque

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

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

parents = [-1] * (n+1)
order = []
q = deque()
q.append(1)
while q:
    c = q.pop()
    order.append(c)
    for i in l[c]:
        if i == parents[c]:
            continue
        parents[i] = c
        q.append(i)

color = [-1] * (n+1)
for i in order:
    ng = color[i]
    c = 1
    for j in l[i]:
        if j == parents[i]:
            continue
        if c == ng:
            c += 1
        color[j] = c
        c += 1

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
edge = []
relation = defaultdict(set)
for i in range(N - 1):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    edge.append((a,b))
    relation[a].add(b)
    relation[b].add(a)

print(max(map(lambda x: len(relation[x]), relation)))
answer = {}
queue = []
queue.append((0, 0)) # (node_id, color_id)
already = set()
counter = 0
already.add(0)
while counter < len(queue):
    node, color = queue[counter]
    c = 1 if color != 1 else 2
    for n in relation[node]:
        if n not in already:
            queue.append((n, c))
            already.add(n)
            answer[(node, n)] = c
            c += 1
            if c == color:
                c += 1
    counter += 1
for e in edge:
    print(answer[e])

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

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

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

    parents = [-1] * (n+1)
    order = []
    q = deque()
    q.append(1)
    while q:
        c = q.pop()
        order.append(c)
        for i in l[c]:
            if i == parents[c]:
                continue
            parents[i] = c
            q.append(i)
    
    color = [-1] * (n+1)
    for i in order:
        ng = color[i]
        c = 1
        for j in l[i]:
            if j == parents[i]:
                continue
            if c == ng:
                c += 1
            color[j] = c
            c += 1
    
    ans = []
    for a, b in ab:
        if a == parents[b]:
            ans.append(color[b])
        else:
            ans.append(color[a])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, edge):
        self.graph[start].append((end, edge))
        self.graph[end].append((start, edge))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        a,b=INTM()
        a-=1
        b-=1
        g.addEdge(a,b,i)

    
    que=deque()
    check=[True]*n
    clrs=[0]*(n-1)
    que.append([0,0])
    check[0]=False
    while que:
        clr=1
        now,clr_f=que.popleft()
        if clr_f==1:
            clr=2
        for next,i in g.graph[now]:
            if check[next]:
                check[next]=False
                que.append([next,clr])
                clrs[i]=clr
                clr+=1
                if clr==clr_f:
                    clr+=1
    
    print(max(clrs))
    for i in range(n-1):
        print(clrs[i])








if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n = int(input())
d = defaultdict(list)
l = []
for i in range(n-1):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    l.append((a,b))

# print(d)

que = deque([a])
visited = [-1] + [False]*n
visited[a] = True

preans = defaultdict(list)
ans = defaultdict(int)
maxi = 1

while que:
    v = que.popleft()
    cnt = 1
    for x in d[v]:
        if not visited[x]:
            while cnt in preans[v]:
                cnt += 1
            maxi = max(maxi,cnt)
            preans[x].append(cnt)
            ans[(v,x)] = cnt
            ans[(x,v)] = cnt
            que.append(x)
            visited[x] = True
            cnt += 1
    # print(preans)
    # print(ans)
print(maxi)

for i in l:
    print(ans[i])

Submission status: Accepted

Solution code:
N=int(input())
ans=[-1]*(N-1)
rootLine=[0]*N
numLine=[0]*N
l=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l.append([a,b,i])
l.sort()

for a,b,i in l:
  numLine[a]+=1
  if numLine[a]==rootLine[a]:
    numLine[a]+=1
  ans[i]=numLine[a]
  rootLine[b]=numLine[a]

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

Submission status: Accepted

Solution code:
N=int(input())
l=[[] for i in range(N)]
color=[0]*N
mem=[]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   mem.append(b)
from collections import deque
que=deque([0])
while que:
   node=que.popleft()
   c=1
   for i in l[node]:
      if color[node]==c:
         c+=1
      color[i]=c
      c+=1
      que.append(i)
print(max(color))
for i in mem:
   print(color[i])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    P=[-1]*N#親から来た辺の色だけ持っておく
    C=[0]*(N-1)
    adj=[[]for _ in range(N)]
    
    from collections import defaultdict
    dd = defaultdict(lambda : -1)
    dd2 = defaultdict(lambda : -1)
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
        dd[(a,b)] = i
        dd2[i]=(a,b)
        
    
    import queue
    q=queue.Queue()
    q.put((0,-1))
    
    while not q.empty():
        v,p=q.get()
        
        col=0
        for i in range(len(adj[v])):
            nv=adj[v][i]
            
            if nv==p:
                continue
            
            if col==P[v]:
                col+=1
            
            a=min(v,nv)
            b=max(v,nv)
            ii=dd[(a,b)]
            C[ii]=col
            P[nv]=col
            col+=1
            
            q.put((nv,v))
            
    K=0
    for i in range(N):
        K=max(K,len(adj[i]))
    
    print(K)
    for i in range(N-1):
        print(C[i]+1)

            
    
    
    

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(lambda x:int(x)-1,input().split())
  t[a].append(b)
  t[b].append(a)
  ab.append((min(a,b),max(a,b)))
k = max(map(len,t))
d = {}
def dfs(pre,cur,col):
  cn = 1 if col != 1 else 2
  for i in t[cur]:
    if i == pre:
      continue
    d[(min(i,cur),max(i,cur))] = cn
    dfs(cur,i,cn)
    cn += 1
    if col == cn:
      cn += 1
dfs(0,0,0)
print(k)
for i in ab:
  print(d[i])

Submission status: Accepted

Solution code:
N = int(input())

ans = [0] * (N-1)
to = [[] for i in range(N-1)]
used = [0] * N

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

for i in range(N-1):
    unable = used[i]
    c = 1
    for j, id in to[i]:
        if c == unable:
            c += 1
        ans[id] = c
        used[j] = c
        c += 1

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

Submission status: Accepted

Solution code:
N = int(input())
from collections import deque
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
inp = deque(inp)
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

from bisect import insort
ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
while inp:
  item = inp.popleft()
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Submission status: Accepted

Solution code:
N = int(input())
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

from bisect import insort


ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Submission status: Accepted

Solution code:
N = int(input())
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while cnt in mark[item[0]] or cnt in mark[item[1]]:
    cnt += 1
  mark[item[1]].append(cnt)
  mark[item[0]].append(cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Submission status: Accepted

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

class vertex:
  def __init__(self,i):
    self.__i = i
    self.__e = []
    self.__d = 0
    self.__nei = []
  def add_e(self, e):
    self.__e.append(e)
    self.__d += 1
    self.__nei.append(e.get_pair_v(self.__i))
  def get_e(self):
    return self.__e
  def get_d(self):
    return self.__d
  def get_i(self):
    return self.__i
  def get_n(self):
    return self.__nei
  
class edge:
  def __init__(self, i, a, b):
    self.__i = i
    self.__c = -1
    self.__v = dict()
    self.__v[a] = b
    self.__v[b] = a
  def get_pair_v(self, a):
    return self.__v[a]
  def get_c(self):
    return self.__c
  def set_c(self, a):
    if self.__c == -1:
      self.__c = a
      return True
    else:
      return False
  def get_i(self):
    return self.__i
    
class tree:
  def __init__(self,N):
    self.__v = [vertex(i) for i in range(N+1)]
    self.__e = []
    self.__max_d = 0
    self.__max_v_idx = 0
    
  def add_e(self,i, a, b):
    ed = edge(i, a, b)
    self.__e.append(ed) 
    self.__v[a].add_e(ed)
    self.__v[b].add_e(ed)
  
  def reload_max_d(self):
    for i in self.__v:
      if i.get_d() > self.__max_d:
        self.__max_d = i.get_d()
        self.__max_v_idx = i.get_i()
        
  def painting(self):
    v = self.__max_v_idx
    edges = self.__v[v].get_e()
    for i, ver in enumerate(edges):
      ver.set_c(i+1)
      self.change_c(ver.get_pair_v(v),ver)   
    
  def change_c(self, idx, prev_e):
    edges = self.__v[idx].get_e()
    edges.remove(prev_e)
    offset = 0
    prev_e_c = prev_e.get_c()
    if not edges:
      return
    for ver in edges:
      offset += 1
      if offset == prev_e_c:
        offset += 1
      if ver.set_c(offset):
        self.change_c(ver.get_pair_v(idx),ver)   
  
  def show_max_d(self):
    print(self.__max_d)
    
  def show_colors(self):
    for i in self.__e:
      print(i.get_c()) 

t = tree(N)
for i in range(N-1):
  temp = list(map(int, input().split()))
  t.add_e(i, temp[0], temp[1])
t.reload_max_d()
t.painting()
t.show_max_d()
t.show_colors()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
edge_colors = [0]*(N-1)
g = [[] for _ in range(N)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))

q = deque([(0, 0)])
visited = [False] * N
visited[0] = True
while len(q) > 0:
    node, color = q.popleft()
    i = 1
    for v, edgeid in g[node]:
        if visited[v]:
            continue
        if i == color:
            i += 1
        visited[v] = True
        q.append((v, i))
        edge_colors[edgeid] = i
        i += 1


print(max(edge_colors))
for c in edge_colors:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
edge = []

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

color = max([len(x) for x in graph])
print(color)

check = [False] * n
check[0] = True
DQ = deque()
DQ.append(0)

tree = [set() for i in range(n)]

while DQ:
    now = DQ.popleft()
    for node in graph[now]:
        if check[node] == False:
            check[node] = True
            tree[now].add(node)
            DQ.append(node)

memo = [False] * n
memo[0] = -1
DQ = deque()
DQ.append(0)

while DQ:
    now = DQ.popleft()
    if now == 0:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            memo[node] = c
            c += 1
    else:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            if c == memo[now]:
                c += 1
                memo[node] = c
                c += 1
            else:
                memo[node] = c
                c += 1

for a, b in edge:
    if a in tree[b]:
        print(memo[a])
    else:
        print(memo[b])

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, itr):
        self.graph[start].append((end, itr))
        self.graph[end].append((start, itr))
    
    def BFS(self, start):
        from collections import deque
        dist = [-1] * self.v
        ret = [0] * (self.v-1)
        que = deque()
        que.append((start, -1))
        dist[start] = 0
        while que:
            now, _color = que.popleft()
            color = 1
            if _color == color: color += 1
            for to, itr in self.graph[now]:
                if dist[to] == -1:
                    que.append((to, color))
                    dist[to] = dist[now] + 1
                    ret[itr] = color
                    color += 1
                    if color == _color: color += 1
        return ret
    
    def color_types(self):
        ret = len(self.graph[0])
        for x in self.graph[1:]:
            ret = max(ret, len(x))
        return ret

def Main():
    n = read_int()
    g = Graph(n)
    for i in range(n - 1):
        a, b = read_ints()
        g.addEdge(~-a, ~-b, i)
    print(g.color_types())
    print(*g.BFS(0), sep='\n')

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
n = int(input())
A = []
g  =[[] for _ in range(n+1)]
ans = {}
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    A.append([a,b])
 
 
from collections import deque
 
q = deque()
q.append(1)
 
color = [-1]*(n+1)
color[1] = 0
cnt = 0
 
while q:
    v = q.popleft()
    p = 1
    for u in g[v]:
        if p==color[v]:
            p += 1
        color[u] = p
        ans[v,u] = p
        q.append(u)
        cnt = max(cnt,p)
        p += 1
print(cnt)
 
for i in range(n-1):
    tmp = (A[i][0],A[i][1])
    print(ans[tmp])

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        edges[a].append((b,i))
        edges[b].append((a,i))

    color = [None]*(N-1)
    SIZE = 1
    q = deque([(0,None)])
    while q:
        v, prev_color = q.popleft()
        c = 1
        for w, i in edges[v]:
            if not color[i]:
                if c == prev_color:
                    c += 1
                color[i] = c
                c += 1
                q.append((w,color[i]))
        SIZE = max(SIZE, c-1)
    print(SIZE)
    for n in range(N-1):
        print(color[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([b,i])
        edge[b].append([a,i])
    color = [0] * (N-1)
    def dfs(s,p,c):
        tmp_c = 1
        for v, num in edge[s]:
            if v == p:
                continue
            if tmp_c == c:
                tmp_c += 1
            color[num] = tmp_c
            dfs(v,s,tmp_c)
            tmp_c += 1
    dfs(0,-1,0)
    print(max(color))
    for c in color:
        print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    edge = [-1] * (N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append(b*N + i)
        G[b].append(a*N + i)

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        que.append(s)
        while que:
            pos = que.popleft()
            c = -1
            k = 1
            for vi in G[pos]:
                v, i = divmod(vi, N)
                if par[pos] == v:
                    c = edge[i]
            for vi in G[pos]:
                v, i = divmod(vi, N)
                if par[pos] == v:
                    continue
                if k == c:
                    k += 1
                par[v] = pos
                edge[i] = k
                k += 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        que.append(s)
        while que:
            pos = que.popleft()
            c = -1
            k = 1
            for (v, i) in G[pos]:
                if par[pos] == v:
                    c = edge[i]
            for (v, i) in G[pos]:
                if par[pos] == v:
                    continue
                if k == c:
                    k += 1
                par[v] = pos
                edge[i] = k
                k += 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        color = [-1]*N
        que.append(s)
        c = 1
        while que:
            pos = que.popleft()
            for (v, i) in G[pos]:
                if par[pos] == v:
                    continue
                if color[pos] == c:
                    c += 1
                    if max_deg < c:
                        c = 1
                par[v] = pos
                edge[i] = c
                color[v] = c
                c += 1
                if max_deg < c:
                    c = 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    G = [[] for _ in range(N)]
    edge = [-1] * (N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append((b, i))
        G[b].append((a, i))

    max_deg = max(len(G[i]) for i in range(N))

    def dfs(s, c=-1, p=-1):
        # 行きがけ順処理
        cur_color = 1
        for (v, i) in G[s]:
            if v == p:
                continue
            if c == cur_color:
                cur_color += 1
            edge[i] = cur_color
            dfs(v, edge[i], s)
            cur_color += 1
        # 帰りがけ順処理

    dfs(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bfs():
    q = deque([(0, -1)])
    visited = [False]*N
    visited[0] = True
    ans = [-1]*(N-1)

    while q:
        v, prev = q.popleft()
        now = 0

        for nv in G[v]:
            if not visited[nv]:
                if now==prev:
                    now += 1

                visited[nv] = True
                ans[idx[(min(v, nv), max(v, nv))]] = now
                q.append((nv, now))
                now += 1

    return ans

N = int(input())
G = [[] for _ in range(N)]
idx = defaultdict(int)

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

ans = bfs()
print(max(ans)+1)

for ans_i in ans:
    print(ans_i+1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = [[] for i in range(N)]
B = []
for i in range(N-1):
  a = list(map(int, input().split()))
  A[a[0]-1].append([a[1]-1, 0])
  A[a[1]-1].append([a[0]-1, 1])
  B.append(a)
K = 0
D = {}
C = [0 for i in range(N)]
de = deque([[0, -1]])
while len(de):
  n = de.pop()
  C[n[0]] = 1
  color = 1
  for a in A[n[0]]:
    if C[a[0]] == 1:
      continue
    if color == n[1]:
      color += 1
    if a[1] == 0:
      D[str(n[0])+","+str(a[0])] = color
    else:
      D[str(a[0])+","+str(n[0])] = color
    de.append([a[0], color])
    K = max(K, color)
    color += 1
print(K)
for b in B:
  print(D[str(b[0]-1)+","+str(b[1]-1)])

Submission status: Accepted

Solution code:
# 木なので親から繋がっている1辺のみ色が塗られている状態(根に限っては何も塗られていない)

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

g = dict()
for i, (a, b) in enumerate(AB):
    a, b = a-1, b-1
    if a not in g:
        g[a] = set()
    if b not in g:
        g[b] = set()
    g[a].add((b, i))
    g[b].add((a, i))

col = [-1]*N
col[0] = -2
e_col = [-1]*(N-1)

q = [0]
while q:
    par = q.pop()
    par_col = col[par]

    c = 0
    for child, e_i in g[par]:
        # print(child, c)
        if col[child] != -1:
            continue
        while c == par_col:
            c += 1
        e_col[e_i] = c
        col[child] = c
        c += 1
        q.append(child)

# print(col)
# print(e_col)

print(max(e_col)+1)
for e_col_i in e_col:
    print(e_col_i+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    edge_order = [0]*(N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append(b)
        G[b].append(a)
        edge[a*N + b] = -1  # 辺(a,b)の色
        edge_order[i] = a*N + b
    # 辺彩色
    # 最大次数だけ色があればよさそう？
    # BFSで塗っていく
    # ある辺を塗るときに必要なのは，親の辺の色と，同じ親の頂点を持つ
    # 辺のうち彩色済みの色（陽に持たなくてよい）
    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        par_color = [-1]*N
        c = 0
        que.append(s)
        while que:
            pos = que.popleft()
            for v in G[pos]:
                if par[pos] == v:
                    continue
                if par_color[pos] == c:
                    c += 1
                    if c == max_deg:
                        c = 0
                if pos < v:
                    edge[pos * N + v] = c
                else:
                    edge[v * N + pos] = c
                par[v] = pos
                par_color[v] = c
                que.append(v)
                c += 1
                if c == max_deg:
                    c = 0

    bfs(0)

    print(max_deg)
    for i in range(N-1):
        print(edge[edge_order[i]] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree = [[] for i in range(N)]
edges = []

for i in range(N - 1):
    edges.append(tuple(map(int, input().split())))
    tree[edges[-1][0] - 1].append(edges[-1][1] - 1)
    tree[edges[-1][1] - 1].append(edges[-1][0] - 1)

coloring = {}
c_max = 1

color_used = [0]*N
v_dist = [-1]*N

queue = deque([0])
v_dist[0] = 0

while queue:
    v = queue.popleft()
    
    c = 1
    for n_v in tree[v]:
        if v_dist[n_v] < 0:
            v_dist[n_v] = v_dist[v] + 1

            if color_used[v] == c:
                c += 1
            
            coloring[(v, n_v)] = c
            coloring[(n_v, v)] = c
            color_used[n_v] = c
            queue.append(n_v)

            c += 1
    
    c_max = max(c_max, c)

print(c_max - 1)

for edge in edges:
    print(coloring[(edge[0]-1, edge[1]-1)])

Submission status: Accepted

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

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)

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

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)

Submission status: Accepted

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

from collections import deque

q = deque()
color = [0]*n
q.append(0)
while q:
    cur = q.popleft()
    c = 1
    for nx in G[cur]:
        if color[cur] == c:
            c += 1
        color[nx] = c
        c += 1
        q.append(nx)

print(max(color))
for e in edge:
    print(color[e])