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: Runtime Error

Solution code:
from collections import deque

def dfs(node,par,color,k):
  for i in range(len(graph[node])):
    if graph[node][i][0] == par:
      graph[node][i][1] = color
      color = graph[node][i][1]       
      continue
    graph[node][i][1] = (i+2)%k +((i+2)%k == 0) if (i+1) == color else (i+1)%k +((i+1)%k == 0)
    dfs(graph[node][i][0],node,graph[node][i][1],k)

N = int(input())
graph = {}
for i in range(N+1):
  graph[i] = []
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append([a,b])
  graph[a].append([b,-1])
  graph[b].append([a,-1])
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

dfs(1,0,0,k+1)
print(k)
for i in range(N-1):
  a,b = ab[i]
  for j in range(len(graph[a])):
    if graph[a][j][0] == b:
      print(graph[a][j][1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import heapq
def main():
    N = int(input())
    graph = {}
    for i in range(1, N+1):
        graph[i] = set()
    ans_order = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
        ans_order.append((a, b))
    K = 0
    for i in range(1, N+1):
        K = max(K, len(graph[i]))
    available_colors = deque([i for i in range(1, K+1)])
    not_available_colors = deque([])
    seen = [0 for _ in range(N)]
    seen[0] = 1
    ans = {i: {} for i in range(1, N+1)}
    que = deque([])
    que.append(1)
    pre_edges = deque([])
    while len(que) != 0:
        v = que.popleft()
        pre_edges.append(len(graph[v]))
        for node in graph[v]:
            if seen[node-1] == 1:continue
            seen[node-1] = 1
            col = available_colors.popleft()
            ans[v][node] = col
            not_available_colors.append(col)
            que.append(node)
        if len(pre_edges) > 1:
            restore_count = pre_edges.popleft()
            for _ in range(restore_count):
                if len(not_available_colors) > 0:
                    available_colors.append(not_available_colors.popleft())
    print(K)
    for pair in ans_order:
        a, b = pair
        print(ans[a][b])
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*(n-1)

for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); eid[a].append(i) # to:nodeの繋がり、eid:edgeの色
    to[b].append(a); eid[b].append(i)

import queue

q = queue.Queue()
used = [0]*n
q.put(0)
used[0] = 1
while not q.empty():
    v = q.get()
    p = pre[v]
    c = -1
    for i in range(len(to[v])):
        u = to[v]; ei = eid[v]
        if used[u]: c = ans[ei]
    k = 1
    for i in range(len(to[v])):
        u = to[v]; ei = eid[v]
        if used[u]: continue
        if k == c: k += 1
        ans[ei] = k
        k += 1
        q.put(u)
        used[u] = 1

mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
"""dfs"""

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]
        ei = eid[v][i]
        if u == p: continue
        if k == c: k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)

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

dfs(0)
mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque
 
N = int(input())
G = [deque([]) for _ in range(N)]
arrive = [0] *N
key = []
for _ in range(N-1):
    a,b = map(int,input().split())
    key.append((a,b))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
 
MAX = 0
for i,g in enumerate(G):
    if MAX < len(g):
        MAX = len(g)
        t = i
 
c_l = list(range(MAX))
C = dict()
 
def bfs(v,c):
    arrive[v] = 1
    cnt = 0
    for w in G[v]:
        if arrive[w] == 0:
            if c == cnt:
                cnt += 1
            bfs(w,cnt)
            if v > w:
                v,w = w,v
            C[(v+1,w+1)] = cnt+1
            cnt += 1
 
bfs(1,-1)
 
print(MAX)
# print(C)
for k in sorted(key):
    print(C[k])

Submission status: Runtime Error

Solution code:
#グラフ構造DFSを使う
N = int(input())
ans = [-1] * (N-1)
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    g[a-1].append((b-1, i))
    g[b-1].append((a-1, i))

def bfs(v, c, p):
    n_c = 1
    for i in range(len(g[v])):
        to = g[v][i][0]
        ID = g[v][i][1]
        if to == p:
            continue
        if n_c == c:
            n_c += 1
        ans[ID] = n_c
        bfs(to, n_c, v)
        n_c += 1

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

Submission status: Runtime Error

Solution code:
#標準入力からKを求めるまで
N = int(input())
node = [0] * N
AB = []
for i in range(N-1):
    ab = list(map(int, input().split()))
    node[ab[0] - 1] += 1
    node[ab[1] - 1] += 1
    AB.append(ab)
K = max(node)
print(K)

#各辺の色を求めていく
color = [[ i for i in range(1, K + 1)] for i in range(N)]
for i in range(N-1):
    now = list(set(color[AB[i][0]-1]) & set(color[AB[i][1] - 1]))
    tmp = now[0]
    color[AB[i][0]-1].remove(tmp)
    color[AB[i][1]-1].remove(tmp)
    print(tmp)

Submission status: Runtime Error

Solution code:
#標準入力からKを求めるまで
N = int(input())
node = [0] * N
AB = []
for i in range(N-1):
    ab = list(map(int, input().split()))
    node[ab[0] - 1] += 1
    node[ab[1] - 1] += 1
    AB.append(ab)
K = max(node)
print(K)

#各辺の色を求めていく
color = [[ i for i in range(1, K + 1)] for i in range(N)]
for i in range(N-1):
    now = list(set(color[AB[i][0]-1]) & set(color[AB[i][1] - 1]))
    tmp = now[0]
    color[AB[i][0]-1].remove(tmp)
    color[AB[i][1]-1].remove(tmp)
    print(tmp)

Submission status: Runtime Error

Solution code:
N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
G = dict([(i,[]) for i in range(1,N+1)])
ansl = []
for i in range(N-1):
  a,b = map(int,input().split())
  ansl.append([a,b])
  G[a].append(b)
  G[b].append(a)

K = -1
hen = [0]*(N+1)
seen = [False for i in range(N+1)]
seen[1] = True 
#[頂点、来たときの辺の色]
l = deque([[1,0]])
while len(l)!=0:
  [v,oyac] = l.popleft()
  nuri = 1
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      while True:
        if nuri != oyac:
          hen[min(v,i)][max(v,i)] = nuri
          l.append([i,nuri])
          K = max(K,nuri)
          nuri += 1
          break
        else:
          nuri += 1  
###
print(K)
for i in range(N-1):
  a,b = ansl[i]
  print(hen[a][b])

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
G = [deque([]) for _ in range(N)]
arrive = [0] *N

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

MAX = 0
for i,g in enumerate(G):
    if MAX < len(g):
        MAX = len(g)
        t = i

c_l = list(range(MAX))
C = dict()

def bfs(v,c):
    arrive[v] = 1
    # print(v)
    cnt = 0
    for w in G[v]:
        if arrive[w] == 0:
            if c == cnt:
                cnt += 1
            bfs(w,cnt)
            if v > w:
                v,w = w,v
            C[(v+1,w+1)] = cnt+1
            cnt += 1

bfs(t,-1)

print(MAX)
for k in sorted(C.keys()):
    print(C[k])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        par = [-1]*N
        while todo:
            u = todo.pop()
            if par[u] != -1:
                color[u] -= color[par[u]]
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                c = color[u].pop()
                par[v] = u
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


color = [0] * N

def dfs(v, c):
    color[v] = c
    now = 0
    for nv in edge[v]:
        now += 1
        if now == c:
            now += 1
        dfs(nv, now)

dfs(0, 0)
color[0] = max(color)
print(*color, sep="\n")

Submission status: Runtime Error

Solution code:
N = int(input())
nood = [[]for i in range(0,N+1,1)]
h_color = [1]*(N+1)
for i in range(1,N,1):
    a,b=map(int,input().split())
    nood[a].append([b,i])
    nood[b].append([a,i])

max_color_count = -1

def bfs(nowNood,preNood,preColor):
    global max_color_count
    colorCount=1
    for i in range(0,len(nood[nowNood]),1):
        if nood[nowNood][i][0]!=preNood:
            if colorCount == preColor:
                colorCount+=1
            h_color[nood[nowNood][i][1]]=colorCount
            bfs(nood[nowNood][i][0],nowNood,colorCount)
            max_color_count = max(max_color_count,colorCount)
            colorCount+=1

bfs(1,-1,-1)
print(max_color_count)
for i in range(1,N,1):
    print(h_color[i])

Submission status: Runtime Error

Solution code:
N = int(input())
nood = [[]for i in range(0,N+1,1)]
h_color = [1]*(N+1)
for i in range(1,N,1):
    a,b=map(int,input().split())
    nood[a].append([b,i])
    nood[b].append([a,i])

max_color_count = -1
def bfs(nowNood,preNood,preColor):
    global max_color_count
    colorCount=1
    for i in range(0,len(nood[nowNood]),1):
        if nood[nowNood][i][0]!=preNood:
            if colorCount == preColor:
                colorCount+=1
            h_color[nood[nowNood][i][1]]=colorCount
            bfs(nood[nowNood][i][0],nowNood,colorCount)
        max_color_count = max(max_color_count,colorCount)
        colorCount+=1

bfs(1,-1,-1)
print(max_color_count)
for i in range(1,N,1):
    print(h_color[i])

Submission status: Runtime Error

Solution code:
# D - Coloring Edges on Tree

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

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

def dfs(key, color=-1, parent=-1):
    k = 1
    for i in range(len(G[key])):
        if G[key][i][0] == parent:
            continue
        if color == k:
            k += 1
        ans[G[key][i][1]] = k
        dfs(G[key][i][0], k, key)
        k += 1

dfs(0)

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
b = []
# graph作成
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    a.append(u)
    b.append(v)

def dfs(x, depth,col):
    tf[x] = True
    if depth % 2 == 1:
        col = 0
    for next in graph[x]:
        if tf[next]:
            continue
        col += 1
        dfs(next, depth + 1, col)
        color[x, next] = col
        color[next, x] = col
    return

maxcolor = 0
tf = [False] * (n + 1)
color = {}
dfs(1, 1, 0)

print(max(color.values()))
for i in range(n - 1):
    print(color[a[i],b[i]])

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
b = []
# graph作成
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    a.append(u)
    b.append(v)

def dfs(x, depth,col):
    tf[x] = True
    if depth % 2 == 1:
        col = 0
    for next in graph[x]:
        if tf[next]:
            continue
        col += 1
        dfs(next, depth + 1, col)
        color[x, next] = col
    return

sn = (10 ** 5) + 10
for i in range(1, n + 1):
    maxcolor = 0
    tf = [False] * (n + 1)
    color = {}
    dfs(i, 1, 0)
    if sn > maxcolor:
        ans = color
        sn = maxcolor

print(max(ans.values()))
for i in range(n - 1):
    print(ans[a[i],b[i]])

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
b = []
# graph作成
graph = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    a.append(u)
    b.append(v)

def dfs(x, depth,col):
    tf[x] = True
    if depth % 2 == 1:
        col = 0
    for next in graph[x]:
        if tf[next]:
            continue
        col += 1
        dfs(next, depth + 1, col)
        color[x, next] = col
    return

maxcolor = 0
tf = [False] * (n + 1)
color = {}
dfs(1, 1, 0)

print(max(color.values()))
for i in range(n - 1):
    print(color[a[i],b[i]])

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
edge=[[] for i in range(n+1)]
iro=0
for i in ab:
  edge[i[0]].append(i[1])
for i in edge:
  if (len(i)+1)>iro:
    iro=len(i)+1
color_list=list(range(1,iro+1))
ans=[[] for i in range(n+1)]
def DFS(x,pre,color,color_list,ans):
  count=-1
  color_list=list(range(1,iro+1))
  if len(edge[x])==0:
    #print(str(pre) + "→"+ str(x) +":" + str(color))
    ans[pre].append(color)
    return
  elif 1!=x:
    #print(str(pre) + "→"+ str(x) +":" + str(color))
    ans[pre].append(color)
  for i in edge[x]:
    a=color_list.pop(-1)
    if a==color:
      a=color_list.pop(-1)
    DFS(i,x,a,color_list,ans)
    
DFS(1,-1,iro,color_list,ans)
for i in ans:
  for j in i:
    print(j)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

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

N = inputI()

graph = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = inputIL()
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
  
M = 0
root = 0
for i in range(N):
  l = graph[i]
  n = len(l)
  if n > M:
    root = i
    M = n

color = [None for _ in range(N)]
q = deque([root])

while  q:
  u = q.popleft()
  c = set(range(M))
  for v in graph[u]:
    if color[v] == None:
      q.append(v)
    else:
      c.remove(color[v])
  color[u] = c.pop()
  
print(M)
for i in color:
  print(i+1)

Submission status: Runtime Error

Solution code:
n=int(input())

g =[[] for _ in range(n)]
ans=[0] * (n-1)

def dfs(v,c=-1,p=-1):
    k=1

    for u,ei in g[v]:
        if u == p: continue
        if k == c: k+=1

        ans[ei] = k
        k+=1
        dfs(u,ans[ei],v)

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

dfs(0)
mx=0

for i in range(n):
    mx = max(mx,int(len(g[i])))

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

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000000)

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

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0])
    return

function(0)
print(max_route)
for color in route_color:
    print(color+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
routes = [[] for _ in range(N-1)]

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    seen[num] = True
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            function(route[0])
    return

function(0)
print(max_route)
for color in route_color:
    print(color+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000000)

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

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    seen[num] = True
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            function(route[0])
    return
        
function(0)
print(max_route)
for color in route_color:
    print(color+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000000)
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")


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

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    seen[num] = True
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            function(route[0])

function(0)
print(max_route)
for color in route_color:
    print(color+1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    seen[num] = True
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            function(route[0])

function(0)
print(max_route)
for color in route_color:
    print(color+1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
struct Edge
{
    int to_;
    int id;
};
vector<ll> ans; //答えを格納する配列。
vector<Edge> to[200005];

void dfs(int v, int c = -1, int p = -1)
{
    int g = 1;
    for (Edge x : to[v]) //
    {
        int u = x.to_;
        int ei = x.id; //これはxが何番目に出てくるものであるかをカウントしている。
        if (u == p)
        {
            continue;
        }
        if (c == g)
        {
            g++;
        }
        ans[ei] = g;
        dfs(u, g, v);
        g++; //これで一つのノードの子ノードまでを補えた。
    }
}
ll dp2(int v)
{
    int res = 0;
    for (Edge x : to[v]) //
    {
        res++;
    }
    return res;
}

int main()
{
    ll n;
    cin >> n;
    ans.resize(n - 1);
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        to[a].push_back((Edge){b, i});
        to[b].push_back((Edge){a, i});
    }
    ll max1 = 0;
    rep(i, n)
    {
        max1 = max(max1, dp2(i));
    }
    cout << max1 << endl;
    dfs(0);
    for (int x : ans)
    {
        cout << x << endl;
    }
}

Submission status: Runtime Error

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


def main():
    N = int(input())
    ans = []
    AB = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)
    
    M = max([len(i) for i in AB])
    _c = set(range(1, M+1))
    C = [_c for _ in range(N+1)]

    root = 1
    checked = set()
    q = [root]

    while q:
        i = q.pop(0)
        if i in checked:
            continue
        checked.add(i)
        for j in AB[i]:
            if j in checked:
                continue
            k = C[i].pop()
            ans.append(k)
            C[j] = C[j] - set([k])
            q.append(j)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)]
e=[ set() for _ in range(N)] #存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
for j in d:
    maxi=max(maxi,len(j))
for i in range(N-1):
    pos=set([i+1 for i in range(maxi)])
    pos= pos- e[a[i]-1] -e[b[i]-1]
    col=min(pos)
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)]
e=[ set() for _ in range(N)] #存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
for j in d:
    maxi=max(maxi,len(j))
for i in range(N-1):
    pos=set([i+1 for in range(maxi)])
    pos= pos- e[a[i]-1] -e[b[i]-1]
    col=min(pos)
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)]
e=[ set() for _ in range(N)] #存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
for j in d:
    maxi=max(maxi,len(j))
for i in range(N-1):
    pos={1,2,3,4}
    pos= pos- e[a[i]-1] -e[b[i]-1]
    col=min(pos)
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
'''catupper
ポイントA.再帰DFSで全ての頂点をチェックし、辺の色を求める。上限に注意。
ポイントB.入力に注意。
頂点が連結しているということは、そこに辺があるということ。
辺は頂点を結ぶので、辺が連結している二つの頂点(a[i], b[i])で表現され、
まず、辺をedgeに格納する。
辺の色は辞書color_dictに格納している。
辺である(a[i], b[i])をキーとして使って、color_dict[(a[i], b[i])]で
その辺に対応する色の番号が分かるようにしている。
辞書のキーが配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):  
    print(color_dict[(a[i], b[i])])
疑問点：色が新しくなるのは分かるけど、
色が1から再び使えるようになる仕組みは下の通りで良いのか？
'''

import sys
sys.setrecursionlimit(1000000)#DFSは再帰の上限回数に注意

n = int(input())
edge = [[] for i in range(n)]
#どの頂点とどの頂点が繋がっているかを格納しておく配列
a = [0] * n#頂点aに繋がっている頂点bの番号を格納しておく配列
b = [0] * n

for i in range(n-1):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1#0-indexにする
    b[i] -= 1
    edge[a[i]].append(b[i])#無向グラフとして入力する
    edge[b[i]].append(a[i])#二重配列に注意

color_dict = {}#色を格納しておく辞書
k = 0#求める色の数

def dfs(x, last = -1, ban_color = -1):
#lastは、どこから来たか、逆走を防ぐ。使っちゃいけない色も引数
#最初は、どこからも来ないし、どの色もOK
    global k#グローバル変数、宣言を忘れない
    color = 1#次の頂点については、再び1からチェックする
    #但し、繋がっている前の頂点と結ばれている辺の色は使えない
    for to in edge[x]:
    #このfor文はある頂点から繋がる次の頂点への辺の色を次々と決めている
    #同じ頂点に繋がる辺は同じ色に出来ないので、次々、色を新しくする
    #配列edgeに格納されている次の頂点toを順番にチェック。
    #edgeに格納されている、いま見ている頂点から繋がっている
    #全ての頂点をチェックすれば、dfs1回分のfor文はオシマイ。
    #次の頂点についても、同様にfor文でチェックし、
    #次の頂点から繋がる全ての頂点をチェックすることになるが、
    #それは次の話。    
        if to == last:continue
        #来た頂点に戻ろうとしたら、何もしない(条件1)
        if color == ban_color:color += 1
        #いま見ている頂点へ来た辺に使っている色なら、
        #新しい色にする(条件2)
        color_dict[(x, to)] = color#DFSして、color_dictに値が入る
        #使う色をタプルで辞書color_dictに格納する(作業)
        #辺(x, to)をキーとして、値colorをバリューに入れる。
        dfs(to, x, color)
        #深さ優先探索なので深く探索できる限り次から次へと探索する。
        #イメージ的には一つ下の階層の頂点を探索する。
        #いま見ている頂点ではないので、混乱しないこと。
        #次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1#いま見ている頂点から繋がる他の頂点へ行く辺の色として
        #新しい色を用意しておく(注意)
    k = max(k, color-1)    #何色を使ったか、その最大値を記録しておく。
    #用意した新しい色(上記の注意)は、まだ使っていないのでcolor-1。

dfs(0)#最初の頂点を示す0をDFSに入れてスタート。
#辞書color_dictに辺キーと色バリューが格納される。

print(k)#必要となる色数を出力
for i in range(n-1):
#辺の色を1から、辺の総数である頂点番号-1まで出力
    print(color_dict[(a[i], b[i])])
  　#辺と色を格納した辞書に対してキーである辺を指定すると、
    #辺に対応する色が出力される
'''  以下の場合分けは不要。制約で1≤ai<bi≤Nだからか？
無向グラフで、aiで一通り、全ての辺が出力されるから？
    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: Runtime Error

Solution code:
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #辺につながっている頂点に使った色
color_side =[0]*(N-1)
color =0
color_all =set(j for j in range(1,color_max +1) )
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    #while True:
    color =(color_all - color_vertex[v_a] -color_vertex[v_b]).pop() #全ての色-使った色[a]-使った色[b]

    color_side[i] =color          #辺の色を出力用に決める
    color_vertex[v_a].add(color)    #前の頂点に使った色として追加
    color_vertex[v_b].add(color)    #先の頂点に使った色として追加
              
#出力
print(color_max)
print(*color_side, sep="\n")