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 defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

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

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

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

Submission status: Accepted

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

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

print(max(color))
for i in G_order:
  print(color[i])

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
d = [0] * (N + 1)
G = [[] for _ in range(N + 1)]
for a, b in ab:
    d[a] += 1
    d[b] += 1
    G[a].append(b)
    G[b].append(a)
print(max(d))

color = defaultdict(int)
q = deque([[1, 0]])
seen = [0] * (N + 1)
while q:
    v, c = q.popleft()
    seen[v] = 1
    tem = 1
    for u in G[v]:
        if seen[u]:
            continue
        if tem == c:
            tem += 1
        q.append([u, tem])
        i, j = min(v, u), max(v, u)
        color[(i, j)] = tem
        tem += 1

for a, b in ab:
    i, j = min(a, b), max(a, b)
    print(color[(i, j)])

Submission status: Accepted

Solution code:
from queue import Queue

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = {}
        
    def add_edge(self, v1, v2):
        self.adjacency_dict[v1][v2] = -1
        self.adjacency_dict[v2][v1] = -1
    
    def paint(self, v1, v2, color):
        self.adjacency_dict[v1][v2] = color
        self.adjacency_dict[v2][v1] = color
        
    def get_color(self, v1, v2):
        return self.adjacency_dict[v1][v2]
    
    def next_vertices(self, v):
        return self.adjacency_dict[v]


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


tree = Graph()
for i in range(1, N+1):
    tree.add_vertex(i)
for a,b in edges:
    tree.add_edge(a, b)

most_edges_vertex = -1
max_colors = 0
for k,v in tree.adjacency_dict.items():
    if len(v) > max_colors:
        most_edges_vertex = k
        max_colors = len(v)


# BFS
q = Queue()
q.put([most_edges_vertex, -1])  # [vertex, prev_color]
while not q.empty():
    vertex, prev_color = q.get()
    nexts = tree.next_vertices(vertex)
    color = 1 if prev_color != 1 else 2

    for v,c in nexts.items():
        if c > 0:
            continue
        q.put([v, color])
        
        # 色ぬり
        tree.paint(vertex, v, color)
        
        # 次の色
        color += 1
        if color == prev_color:
            color += 1

print(max_colors)
for v1,v2 in edges:
    print(tree.get_color(v1, v2))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uvs = [None]*(n-1)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    uvs[i] = (u,v)

s = [(0, -1)]
cs = {(0,-1): -1}
seen = [False]*n
seen[0] = True
while s:
    u,prev = s.pop()
    val = 0
    cc = cs[u,prev]
    for v in ns[u]:
        if seen[v]:
            continue
        if val==cc:
            val += 1
        cs[v,u] = val
        val += 1
        seen[v] = True
        s.append((v,u))
ans = []
for u,v in uvs:
    if (u,v) in cs:
        ans.append(cs[u,v]+1)
    else:
        ans.append(cs[v,u]+1)
print(max(ans))
write("\n".join(map(str, ans)))

Submission status: Accepted

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


def main():
  N = int(input())
  G = [[] for _ in range(N)]
  dic = {}
  for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    dic[(a, b)] = i
    dic[(b, a)] = i

  color = [0]*(N-1)
  upcol = [0]*(N)
  upcol[0] = None
  visited = set()
  q = deque([0])
  max_col = 0

  while len(q):

    now = q.popleft()
    visited.add(now)
    c = 0

    for next_ in G[now]:
      if next_ in visited:
        continue
      c += 1
      if upcol[now] == c:
        c += 1

      color[dic[(now, next_)]] = c
      upcol[next_] = c

      q.append(next_)

    max_col = max(max_col, c)

  print(max_col)
  print(*color, sep='\n')


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

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  G = [[] for _ in range(N)]
  dic = {}
  for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    dic[(a, b)] = i
    dic[(b, a)] = i

  color = [0]*(N-1)
  upcol = [0]*(N)
  upcol[0] = None
  visited = set()
  q = deque([0])
  max_col = 0

  while len(q):

    now = q.popleft()
    visited.add(now)
    c = 0

    for next_ in G[now]:
      if next_ not in visited:
        c += 1
        if upcol[now] is None or not(upcol[now] == c):
          color[dic[(now, next_)]] = c
          upcol[next_] = c
        else:
          c += 1
          color[dic[(now, next_)]] = c
          upcol[next_] = c
        q.append(next_)

    max_col = max(max_col, c)

  print(max_col)
  print(*color, sep='\n')


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIR1(n): return [LI1() 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)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    AB = LIR1(N-1)

    g = [[] for _ in range(N)]
    visited = [False] * N
    ins = [-1] * N

    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    visited[0] = True
    q.append(0)

    while q:
        u = q.popleft()
        outs_num = 0
        visited[u] = True

        for v in g[u]:
            if not visited[v]:
                if outs_num == ins[u]:
                    outs_num += 1

                ins[v] = outs_num

                outs_num += 1
                q.append(v)

    print(max(ins) + 1)
    for a, b in AB:
        print(ins[b] + 1)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [0] * (N - 1)
q = deque([[1, 0, -1]])
while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node: continue
        if cnt == pcol: cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
I = defaultdict(lambda:0)
cs = [0]*n
used = [0]*n
q = deque([0])
used[0]=1
k = 0
while q:
    u = q.popleft()
    if k < len(data[u]):
        k = len(data[u])
    cur = 1
    for v in data[u]:
        if used[v]:continue
        if cur==cs[u]:cur+=1
        cs[v] = cur
        I[(u,v)] = cur
        I[(v,u)] = cur
        cur += 1
        used[v] = 1
        q.append(v)
print(k)
for i,j in sides:
    print(I[(i,j)])

Submission status: Accepted

Solution code:
from collections import deque

def nearlist(N, LIST):  # 隣接リスト
    NEAR = [[] for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].append(b - 1)
        NEAR[b - 1].append(a - 1)
    return NEAR


def bfs(NEAR, S, COLOR, ANS):  # 幅優先探索  # キュー
    # 隣点リスト,始点,数
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        c, cnt = COLOR[q], 0
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            cnt += 1 + (cnt == c - 1)
            COLOR[i] = cnt
            ANS[(q, i)], ANS[(i, q)] = cnt, cnt
            que.append(i), frag.add(i)
    return


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

color, ans = [-1] * n, {}
near = nearlist(n, ab)
bfs(near, 0, color, ans)
print(max(ans.values()))
for a, b in ab:
    print(ans[(a - 1, b - 1)])

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

stack = deque([0])
stack.append(0)
ans = [0 for _ in range(n)]
while stack:
    v = stack.popleft()
    c = 1
    for nv in g[v]:
        if ans[v] == c:
            c += 1
        ans[nv] = c
        c += 1
        stack.append(nv)

print(max(ans))
for i in e:
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    e.append(b-1)
 
q=deque([0])
 
color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1
 
        color[x]=c
        c+=1
        q.append(x)
 
print(max(color))
for i in e:
    print(color[i])

Submission status: Accepted

Solution code:
#BFSだとかえって考えにくい
#それぞれの頂点に対して塗られてない色で塗り分け
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)
#print(paths)
for i in range(n):
    cand1,cand2=set(),[]
    #print(paths[i])
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])

Submission status: Accepted

Solution code:
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)
#print(paths)
for i in range(n):
    cand1,cand2=set(),[]
    #print(paths[i])
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])

Submission status: Accepted

Solution code:
from collections import deque

def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for i in range(1,n):
    a,b = map(int, input().split())
    d1 = {"id":i,"to":b}
    d2 = {"id":i,"to":a}
    graph[a].append(d1)
    graph[b].append(d2)
  
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[[] for _ in range(n+1)]
  reached=[False]*(n+1)
  ans=[0]*(n)
  while q:
    current = q.popleft()
    reached[current] = True
    temp = 1
    for dic in graph[current]:
      id = dic["id"]
      next = dic["to"]
      if reached[next]:
        continue
      while temp in color[current]:
        temp += 1
      color[next].append(temp)
      ans[id] = temp
      temp += 1
      q.append(next)
  for i in ans[1:]:
    print(i)
      
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200_000)

def solve(N: int, a: "List[int]", b: "List[int]"):
    from itertools import count
    edges = [[] for _ in range(N)]
    for i, (aa, bb) in enumerate(zip(a, b)):
        edges[aa-1].append((bb-1, i))
        edges[bb-1].append((aa-1, i))
    ans = [None] * (N-1)
    visited = set()
    def dfs(n, c):
        if n in visited:
            return
        visited.add(n)
        for (nn, i), cc in zip(filter(lambda x: x[0] not in visited, edges[n]),
                          filter(lambda y: y != c, count(1))):
            ans[i] = cc
            dfs(nn, cc)
    dfs(0, None)
    return [max(ans)] + ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(*solve(N, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

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

Submission status: Accepted

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

def dfs(x, last=-1, ban_color=-1):
    """
    x: 今いる頂点
    last: 既に探索済の頂点(無限ループにならないように初期値-1)
    ban_color: 既に探索済の頂点(last)と今いる頂点(x)との辺に塗られている色(→使っちゃいけない色)
    """
    color = 1
    for to in vertex[x]:  #今いる頂点に隣接する頂点(つまり今いる頂点から出てる辺をすべて舐める),(rootから隣接する頂点に対してのroopとも捉えられる)
        if to == last: continue  # 既に探索済の辺はもう色が塗られているからスキップ
        if color == ban_color: color += 1
        color_dic[(x, to)] = color  # 辺の色をぬる
        dfs(to, x, color)
        color += 1
        
        

n = int(input())
vertex = {i: [] for i in range(n)} # 隣接頂点を保持
a = [0] * (n - 1)  #i番目の辺を保持
b = [0] * (n - 1)  #i番目の辺を保持
color_dic = {} # 辺の色を保持


for i in range(n-1): # 隣接頂点の辞書を作成
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    vertex[a[i]].append(b[i])
    vertex[b[i]].append(a[i])

max_v = 0

for _, v in vertex.items():
    if len(v) > max_v:
        max_v = len(v)
print(max_v)
    


dfs(0)

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

Submission status: Accepted

Solution code:
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
graph = [[] for _ in range(N+1)]
AB = []
for i in range(N-1):
    a,b = map(int,readline().split())
    AB.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * (N+1)
dist[1] = 0
COL = defaultdict()
q = deque([(1,0)])
max_col = 0

def bfs(max_col):
    while q:
        x,pre_col = q.popleft()
        c = 1
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            if c == pre_col:
                c += 1
            COL[(x,nx)] = c
            dist[nx] = 1
            q.append((nx,c))
            max_col = max(max_col,c)
            c += 1
    return max_col  

max_col = bfs(max_col)
print(max_col)
for a,b in AB:
    if (a,b) in COL:
        print(COL[(a,b)])
    else:
        print(COL[(b,a)])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
dist = [[] for i in range(N)]
edge = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
    # queryの何番目のエッジか
    edge[(a - 1, b - 1)] = i
    edge[(b - 1, a - 1)] = i

ignore = [-1] * N
ignore[0] = 0
ans = [0] * (N - 1)

pos = deque([0])
while len(pos) > 0:
    u = pos.popleft()
    j = 1
    for i in dist[u]:
        if ignore[i] < 0:
            if j == ignore[u]:
                j += 1
            ignore[i] = j
            ans[edge[(i, u)]] = j
            pos.append(i)
            j += 1
print(max(ans))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N = NI()
    edges = [NLI() for _ in range(N-1)]
    graph = [[] for _ in range(N+1)]
    edge_dict = {}
    for i, edge in enumerate(edges):
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        edge_dict[(edge[0], edge[1])] = i+1

    queue = deque()
    queue.append(1)
    seen = [0]*(N+1)
    colors = [-1] * N
    colors[1] = 1
    now_colors = deque()
    now_colors.append(-1)
    while queue:
        now = queue.popleft()
        now_color = now_colors.popleft()
        seen[now] = 1
        nexts = graph[now]
        color = 1
        for goto in nexts:
            if seen[goto] == 0:
                a, b = min(now, goto), max(now, goto)
                if color == now_color:
                    color += 1
                colors[edge_dict[(a, b)]] = color
                queue.append(goto)
                now_colors.append(color)
                color += 1
    print(max(colors))
    for i in range(1, N):
        print(colors[i])



if __name__ == "__main__":
    main()

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))

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
    
answer = []
for a, b in AB:
  if parent[a] == b:
    answer.append(color[a])
  else:
    answer.append(color[b])
K =max(answer)

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())
    ab_s = [list(map(int, input().split())) for i in range(n - 1)]

    ref_s = [[] for i in range(n + 1)]

    for ab in ab_s:
        ref_s[min(ab)].append(max(ab))

    # deq作成
    que = deque()
    que.appendleft((1, 0))  # 始める場所はどこでもいい。

    ans = {}
    # BFS開始
    while len(que) is not 0:

        pop = que.pop()
        parent = pop[0]
        parent_col = pop[1]

        child_col = 0

        # 繋がる点に移動
        for child in ref_s[parent]:

            child_col += 1
            if child_col == parent_col:
                child_col += 1

            key1 = min(parent, child)
            key2 = max(parent, child)

            # 処理対象のチェック
            # 処理済みなら何もしない
            if ans.get((key1, key2), 0) != 0:
                continue

            # 処理済み状態にする
            ans[(key1, key2)] = child_col

            # 処理対象に対する処理
            # キューに追加(先頭に追加するのでappendleft())
            que.appendleft((child, child_col))

    # 色数を出力
    print(max(ans.values()))

    # 辺の色を出力
    for ab in ab_s:
        key1 = min(ab[0], ab[1])
        key2 = max(ab[0], ab[1])
        print(ans.get((key1, key2)))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2
2 3"""
        output = """2
1
2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """8
1 2
2 3
2 4
2 5
4 7
5 6
6 8"""
        output = """4
1
2
3
4
1
1
2"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """6
1 2
1 3
1 4
1 5
1 6"""
        output = """5
1
2
3
4
5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.pop()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

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