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: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def bfs(v):
        color = [f_inf for _ in range(n)]
        color[v] = 0
        q = deque()
        q.append([v, 0])
        while q:
            u, pc = q.popleft()
            cnt = 1
            for nv in tree[u]:
                if color[nv] == f_inf:
                    if cnt == pc:
                        cnt += 1
                    color[nv] = cnt
                    q.append([nv, color[nv]])
                    cnt += 1

        return color

    res = bfs(0)

    k = max(res)
    print(k)
    for i in range(1, n):
        print(res[i])



if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())

colors =  [0]*N
E = []
for n in range(N-1):
    a, b = map(int, input().split())
    E.append((a-1, b-1))
    colors[a-1] += 1
    colors[b-1] += 1

m = max(colors)
print(m)
C = [[i+1 for i in range(m)] for _ in range(N)]
for n in range(N-1):
    a, b = E[n]
    for ca in C[a]:
        if ca in C[b]:
            C[a].remove(ca)
            C[b].remove(ca)
            print(ca)
            break

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dfs(v, p, pc):
        if len(tree[v]) > 2:
            nc = 1
            for u in tree[v]:
                if u == p:
                    continue
                if pc == nc:
                    nc += 1
                color[u] = nc
                nc += 1

        for u in tree[v]:
            if u == p:
                continue
            else:
                nc = 1
                if color[u] == -1:
                    if nc == pc:
                        color[u] = nc + 1
                    else:
                        color[u] = nc
                else:
                    nc = color[u]
                dfs(u, v, nc)

    color = [-1 for _ in range(n)]
    color[0] = 0
    dfs(0, -1, -1)

    print(max(color))
    for i in range(1, n):
        print(color[i])


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    AB=[tuple(map(int,input().split())) for i in range(n-1)]
    V=[0]*n
    VC=[[] for _ in range(n)]
    for a,b in AB:
        V[a-1]+=1
        V[b-1]+=1
    max_V=max(V)
    print(max_V)
    for i in range(n-1):
        a,b=AB[i]
        for j in range(1,max_V+1):
            if (not j in VC[a-1]) and (not j in VC[b-1]):
                print(j)
                VC[a-1].append(j)
                VC[b-1].append(j)
                break


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

colors =  [0]*N
E = []
for n in range(N-1):
    a, b = map(int, input().split())
    E.append((a-1, b-1))
    colors[a-1] += 1
    colors[b-1] += 1

m = max(colors)
print(m)
C = [{i+1 for i in range(m)} for _ in range(N)]
for n in range(N-1):
    a, b = E[n]
    for ca in C[a]:
        if ca in C[b]:
            C[a].discard(ca)
            C[b].discard(ca)
            print(ca)
            break

Submission status: Wrong Answer

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
now_list = [(0, 0)]
next_list = []
while len(now_list) > 0:
    for i in range(len(now_list)):
        v, c = now_list.pop()
        color[v] = c
        now_color = 0
        for nv in edge[v]:
            now_color += 1 if now_color + 1 != c else 2
            next_list.append((nv,now_color))
    now_list = next_list
    next_list = []

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

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

ans = [-1] * (N - 1)
A = [set() for _ in range(N)]

st = [0]
while st:
    now = st.pop()
    s = 1
    for c, (i, to) in enumerate(edges[now]):
        if ans[i] != -1:
            continue
        while c + s in A[now]:
            s += 1
        ans[i] = s + c
        A[to].add(s + c)
        st.append(to)

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

Submission status: Wrong Answer

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

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)


color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n

color_max = 1

d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))

    # color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])

    for i in index_list:
        if check_list[i] == 1:
            continue
        else:
            check_list[i] == 0
            check_list[i] = 1
            d.append(i)

        if color_list[index][i] == -1:
            # num = color_list_rest.pop()
            num = 0
            color_list[index][i] = num
            color_list[i][index] = num


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

Submission status: Wrong Answer

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

# この点で既に使った色 
pc_sets = [set() for _ in range(N)]
colors = []
for _ in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())

    c = 1
    while c in pc_sets[a] or c in pc_sets[b]:
        c += 1
    pc_sets[a].add(c)
    pc_sets[b].add(c)
    colors.append(c)

print(len(set(colors)))
for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
# この点で既に使った色 
pc_sets = [set() for _ in range(N)]

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

    c = 1
    while c in pc_sets[a] or c in pc_sets[b]:
        c += 1
    pc_sets[a].add(c)
    pc_sets[b].add(c)

    colors.append(c)

maxlen = 0    
for s in pc_sets:
    maxlen = max(maxlen, len(s))
print(maxlen)

for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peers = [[] for _ in range(N)]
colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peers[a].append(b)
    colors[a][b] = 0


def draw(node, parent_edge_color):
    _peers = peers[node]
    if len(_peers) == 0:
        return 0
    color = 1
    max_nrof_color = 1
    for peer in _peers:
        print(node,peer,color)
        if color == parent_edge_color:
            color +=1
        colors[node][peer] = color
        max_nrof_color = max(max_nrof_color, color, draw(peer, color))
        color += 1

    return max_nrof_color


print(draw(0,0))
for a,b in pairs:
    print(colors[a][b])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                used_colors.remove(color)
                color += 1
            if edge_colors[i][j] == 0:
                edge_colors[i][j] = color
    max_colors = max([color] + used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans = 0
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
color = [0] * N
color[0] = 1
q = deque([0])
while q:
  x = q.popleft()
  num = 1
  for nextx in graph[x]:
    if(color[nextx] > 0):
      continue
    if(num == color[x]):
      num += 1
    color[nextx] = num
    q.append(nextx)
    num += 1
print(max(color))
for i in range(N):
  print(color[i])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
color = [0] * (n + 1)


def dfs(s):
    stack = deque([s])
    color[s] = -1
    while stack:
        num = 1
        now = stack.pop()
        for next in graph[now]:
            if color[next] != 0:
                continue
            if color[now] == num:
                num += 1
            color[next] = num
            num += 1
            stack.appendleft(next)


dfs(1)
color[1] = max(color)
print('\n'.join(map(str, color[1:])))

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import log2
colors = [set() for _ in range(N)]
ans = []
for _ in range(N - 1):
    a, b = map(lambda n: int(n) - 1, input().split())
    colorset = colors[a] | colors[b]
    color = 1
    while color in colorset:
        color += 1
    colors[a] |= {color}
    colors[b] |= {color}
    ans.append(color)
print(max(ans), *ans, sep="\n")

Submission status: Wrong Answer

Solution code:

#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(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
root =0
for i,v in connection.items():
    if color_max < len(v) :
        color_max =len(v)
        root =i         #枝が一番多い所を根 ⇒スタート

#各頂点に色を準備⇒辺の色決定
aa=[]
color =0                                 #辺に塗る色の候補
node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
edge ={}
for a,b in A:
    edge[(a,b)] =-1                   #辺の色 -1で初期化
now_set =set() #=start
now_set.add(root) #=start
next =set()
next_next =set()
passed ={i:False for i in range(1,N+1)}
count =0
while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
    for now in now_set: #幅優先探索
        next =connection[now]
        for nex_2 in next:
            count =0
            if node[now] !=[]:
                color =node[now][-1] +1
            while count < color_max:
                q,color =divmod(color,color_max)
                #if color not in node[now] and color not in node[nex_2]:
                if color not in node[now] :
                    n1,n2=0,0
                    if now > nex_2:
                        n1,n2 =nex_2,now
                    else:
                        n1,n2 =now,nex_2
                    edge[(n1,n2)] =color +1  #辺の色決定
                    node[now]   .append(color)
                    node[nex_2] .append(color)
                    passed[now] =True
                    #colored     =connection[nex_2] - passed
                    if passed[nex_2] ==False:
                        next_next.add(nex_2)  #つながっている頂点（次に探索する）
                    passed[nex_2] =nex_2
                    color   +=1
                    count   +=1
                    break
                else:
                    color +=1
                    count +=1
    now_set     .clear()
    now_set     |=next_next
    next_next   .clear()
    
#出力
print(color_max)
for i in A:
    print(edge[i])

Submission status: Wrong Answer

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

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

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)

while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        
# 根以外の頂点は、唯一の親を持つことから、
# vの親がpであるとき → color[v] に辺 pvの色を持たせると定めて色を管理
color = [-1] * (N+1)
for x in seen:
    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

print(max(color))
for i in range(2,N+1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    # 入力
    n = int(input())
    nodes_edges_data = {e: [] for e in range(1, n + 1)}
    edges_data_to_number = {}
    for i1 in range(n - 1):
        a, b = tuple(map(int, input().split()))
        nodes_edges_data[a].append(b)
        nodes_edges_data[b].append(a)
        edges_data_to_number[(a, b)] = i1
        edges_data_to_number[(b, a)] = i1
    # 処理
    edges_color = [-1] * (n - 1)
    nodes_num = [0] * (n + 1)
    nodes_num[1] = -1
    max_edges_per_node = 0
    nodes_next = deque([1])
    nodes_next_next = deque()
    nodes_seen = set()
    while len(nodes_seen) < n:
        while nodes_next:
            e = nodes_next.pop()
            nodes_seen.add(e)
            adj_nodes = nodes_edges_data[e]
            print(e,":",adj_nodes)
            nodes_next_next += adj_nodes
            num_of_nodes = len(adj_nodes)
            max_edges_per_node = max(max_edges_per_node, num_of_nodes)
            num = nodes_num[e]
            print("nodes_seen:", nodes_seen)
            print("color:", edges_color)
            for adj_node in adj_nodes:
                if not adj_node in nodes_seen:
                    print("go", adj_node)
                    num = (num + 1) % max_edges_per_node
                    edges_color[edges_data_to_number[(e, adj_node)]] = num
                    #nodes_num[adj_node] = (num + 1) % max_edges_per_node
                    nodes_num[adj_node] = num
        nodes_next_next_set = set(nodes_next_next)
        nodes_next += deque(nodes_next_next_set - nodes_seen)
        nodes_next_next = deque()

    # 出力
    print(max(edges_color) + 1)
    for i in range(n - 1):
        print(edges_color[i] + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    q = [[]for i in range(n)]
    print(mode)
    for i in range(n-1):
        for j in range(1,mode+1):
            if j in q[p[i][0]-1] or j in q[p[i][1]-1]:
                print(j)
            else:
                print(j)
                q[p[i][0]-1].append(j)
                q[p[i][1]-1].append(j)
                break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    q = [[]for i in range(n)]
    print(mode)
    for i in range(n-1):
        for j in range(1,mode+1):
            if j in q[p[i][0]-1] or j in q[p[i][1]-1]:
                continue
            else:
                print(j)
                q[p[i][0]-1].append(j)
                q[p[i][1]-1].append(j)
                break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    s = [[i+1 for i in range(mode)]for j in range(n)]
    print(mode)
    for i in range(n-1):
        for j in range(len(s[p[i][0]-1])):
            ans = s[p[i][0]-1][j]
            if ans in s[p[i][1]-1]:
                print(ans)
                s[p[i][0]-1].remove(ans)
                s[p[i][1]-1].remove(ans)
                break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    p.sort()
    s = [1 for i in range(n)]
    print(mode)
    for i in range(n-1):
        ans = max(s[p[i][0]-1],s[p[i][1]-1])
        print(ans)
        if (ans + 1)%mode == 0:
            s[p[i][0]-1] = mode
            s[p[i][1]-1] = mode
        else:
            s[p[i][0]-1] = (ans + 1)%mode
            s[p[i][1]-1] = (ans + 1)%mode
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    s = [1 for i in range(n)]
    print(mode)
    for i in range(n-1):
        ans = max(s[p[i][0]-1],s[p[i][1]-1])
        print(ans)
        if (ans + 1)%mode == 0:
            s[p[i][0]-1] = mode
            s[p[i][1]-1] = mode
        else:
            s[p[i][0]-1] = (ans + 1)%mode
            s[p[i][1]-1] = (ans + 1)%mode
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    s = [[i+1 for i in range(mode)]for j in range(n)]
    print(mode)
    for i in range(n-1):
        for j in range(1,mode+1):
            if j in s[p[i][0]-1] and j in s[p[i][1]-1]:
                print(j)
                s[p[i][0]-1].remove(j)
                s[p[i][1]-1].remove(j)
                break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    g = [0 for i in range(n)]
    p = []
    for i in range(n-1):
        a,b = map(int,input().split())
        p.append([a,b])
        g[a-1] += 1
        g[b-1] += 1
    mode = max(g)
    s = [[i+1 for i in range(mode)]for j in range(n)]
    for i in range(n-1):
        for j in range(1,mode+1):
            if j in s[p[i][0]-1] and j in s[p[i][1]-1]:
                print(j)
                s[p[i][0]-1].remove(j)
                s[p[i][1]-1].remove(j)
                break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
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)
print(iro)
for i in ans:
  for j in i:
    print(j)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
color = [[0] for _ in range(N)]
ans = [0]*(N-1)
for i in range(N-1):
    flg = True
    a, b = map(int, input().split())
    target = max(len(color[a-1]),len(color[b-1])) + 1
    for k in range(1,target):
        if k not in color[a-1] and k not in color[b-1]:
            ans[i] = k
            color[a-1].append(k)
            color[b-1].append(k)
            flg = False
            break
    if flg:
        ans[i] = target
        color[a-1].append(target)
        color[b-1].append(target)
print(len(set(ans)))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int( input() )

K = 0
D = [0] * N
L = [0] * ( N - 1 )
for i in range( N - 1 ):
  a, b = map( int, input().split() )
  if a <= N - 1:
    D[ a - 1 ] += 1
    K = max( K, D[ a - 1 ] )
  if b <= N - 1:
    D[ b - 1 ] += 1
    K = max( K, D[ b - 1 ] )
  L[ i ] = max( D[ a - 1], D[ b - 1] )
print( K )
for i in L:
  print( i )

Submission status: Wrong Answer

Solution code:
N = int( input() )

K = 0
L = [0] * ( N - 1 )
for _ in range( N - 1 ):
  a, b = map( int, input().split() )
  if a <= N - 1:
    L[ a - 1 ] += 1
    K = max( L[ a - 1 ], K )
  if b <= N - 1:
    L[ b - 1 ] += 1
    K = max( L[ b - 1 ], K )
  
print( K )
for i in L:
  print( i )

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	ki = [[] for i in range(N)]
	inp = {}
	ans = [inf for i in range(N-1)]
	ansInt = 0

	for i in range(N-1):
		a,b = inputMap()
		a -= 1
		b -= 1
		ki[a].append(b)
		ki[b].append(a)
		inp[(a,b)] = i

	for i in ki:
		if len(i) > ansInt:
			ansInt = len(i)

	for i in range(N):
		ko = ki[i]
		dame = []
		mi = []
		for j in ko:
			#print("{} {} {}".format(i,j,ko))
			if i < j:
				mi.append(j)
			else:
				dame.append(ans[inp[(j,i)]])
		dame.sort()
		for j in mi:
			for ii in range(ansInt+1):
				tmp = bisect_left(dame,ii)
				if tmp < len(dame):
					pass
				else:
					ans[inp[(i,j)]] = ii
					dame.append(ii)
					dame.sort()
					break
		#print(ans)

	#print(ki)
	#print(inp)
	#print(ans)

	print(ansInt)
	for i in ans:
		print(i+1)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()