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
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 bfs(s):
    check = [False] * (n + 1)
    q = deque([s])
    while q:
        now = q.popleft()
        check[now] = True
        cnt = 0
        for nxt in graph[now]:
            if check[nxt]:
                continue
            q.append(nxt)
            cnt += 1
            if cnt == color[now]:
                cnt += 1
            color[nxt] = cnt


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

Submission status: Wrong Answer

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_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            #color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Wrong Answer

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)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Wrong Answer

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
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Wrong Answer

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
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)

Submission status: Wrong Answer

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
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        q,color =divmod(color,color_max) #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]: #使った色リストに入っているか？
            color_side[i] =color+1  #辺の色を決める（2行上の＋１）
            color_vertex[v_b].add(color) #つながっている頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Wrong Answer

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
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    while True:
        color +=1
        q,color =divmod(color,color_max) #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a]: #使った色リストに入っているか？
            color_side[i] =color+1  #辺の色を決める（2行上の＋１）
            color_vertex[v_b].add(color) #つながっている頂点に使った色として追加
            break
    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

Submission status: Wrong Answer

Solution code:
#初期入力
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_num =[]
for i in connection.values():
    color_num.append(len(i))
color_min = max(color_num)

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set(range(1,color_min +1))for i in range(1,N+1)}
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color_side[i] =color_vertex[v_a].pop()  #辺の色を決める
    color_vertex[v_b].discard(color_side[i])#つながり先の頂点から、今決めた色を抜く
    
#出力
print(color_min)
for i in color_side:
    print(i)

Submission status: Wrong Answer

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

#色の数(各頂点)
color_num =[]
for i in connection.values():
    color_num.append(len(i))
color_min = max(color_num)

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set(range(1,color_min +1))for i in range(1,N+1)}
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color_side[i] =color_vertex[v_a].pop()  #辺の色を決める
    color_vertex[v_b].discard(color_side[i])#つながっている頂点から、今決めた色を抜く
    
#出力
print(color_min)
for i in color_side:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [[] for i in range(N)]
edge1 = []
edge2 = []

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

ans = 0

for i in range(N):
    ans = max(ans,len(data[i]))

print(ans)

color = [1]*N
ret = [[] for _ in range(N-1)]
p = [0]*N

for i in range(N):
    if len(data[i]) == ans:
        p[i] = 1

for i in range(N-1):
    if p[edge1[i]] == 1:
        ret[i].append(color[edge1[i]])
        color[edge1[i]] += 1
        color[edge2[i]] += 1
    elif p[edge2[i]] == 1:
        ret[i].append(color[edge2[i]])
        color[edge1[i]] += 1
        color[edge2[i]] += 1

for i in range(N-1):
    if p[edge1[i]] == 0 and p[edge2[i]] == 0:
        ret[i].append(max(color[edge1[i]],color[edge2[i]]))
        color[edge1[i]] += 1
        color[edge2[i]] += 1

for i in range(N-1):
    print(" ".join(map(str,ret[i])))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque

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

stack = deque([1])
C = [0] * (N + 1)
while stack:
    v = stack.popleft()
    c = 0
    for w in graph[v]:
        c += 1 + (c + 1 == C[v])
        C[w] = c
        stack.append(w)
        
print(max(C))
print("\n".join(str(C[b]) for b in range(2,N+1)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from copy import deepcopy

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

stack = deque([1])
C = [0] * (N + 1)
while stack:
    v = stack.popleft()
    c = 0
    for w in graph[v]:
        c += 1 + (c + 1 == C[v])
        C[w] = c
        stack.append(w)
        
print(max(C))
for c in C[2::]:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from copy import deepcopy

N = int(input())
graph = defaultdict(deque)
colored = dict()
for _ in range(N-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    colored[(a,b)] = None

MAX = 0
for k,v in graph.items():
    if MAX < len(v):
        MAX = len(v)
        s = k

stack = deque([s])
graph2 = deepcopy(graph)
color_deque_dict = dict()
arrive = [False] * (N+1)
color_dict = dict()
for i in range(1,N+1):
    color_dict[i] = list(range(1,MAX+1))

while stack:
    v = stack[-1]
    arrive[v] = True
    if graph2[v]:
        w = graph2[v].pop()
        stack.append(w)
        if arrive[w] == False:
            # print(v,color_dict[v],v,w)
            c = color_dict[v][0]
            color_dict[v].remove(c)
            color_dict[w].remove(c)
            if v > w:
                w , v = v, w
            colored[(v,w)] = c
        
    else:
        stack.pop()

print(MAX)
for i in colored.values():
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque

N = int(input())
graph = defaultdict(list)
colored = dict()
for _ in range(N-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    colored[(a,b)] = None

MAX = 0
for v in graph.values():
    MAX = max(MAX, len(v))

color_list = list(range(1,MAX+1))
color_node = dict()
for i in range(1,N+1):
    color_node[i] = []

for (a,b) in colored.keys():
    for c in color_list:
        if not c in color_node[a] and not c in color_node[b]:
            colored[(a,b)] = c
            color_node[a].append(c)
            color_node[b].append(c)
            break

print(MAX)
for v in colored.values():
    print(v)

Submission status: Wrong Answer

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

N = int(input())
G = [dict() for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1][b-1] = i
    G[b-1][a-1] = i
ans = [0]*(N-1)
def dfs(i,visited_i,color):
    visited = copy.deepcopy(visited_i)
    visited[i] += 1
    c = 1
    for j in G[i]:
        if visited[j]:
            continue
        if c==color:
            c += 1
        ans[G[i][j]] = c
        dfs(j,visited,c)
        c += 1
dfs(0,[0]*N,1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

N = int(input())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
def dfs(i,visited_i,color):
    ans[i] = color
    visited = copy.deepcopy(visited_i)
    visited[i] += 1
    c = 1
    for j in G[i]:
        if visited[j]:
            continue
        if c==color:
            c += 1
        dfs(j,visited,c)
        c += 1
dfs(0,[0]*N,1)
print(max(ans))
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

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

import copy
ans = [0]*N
def dfs(i,visited_i,color):
    ans[i] = color
    visited = copy.deepcopy(visited_i)
    visited[i] += 1
    c = 1
    for j in G[i]:
        if visited[j]:
            continue
        if c==color:
            c += 1
        dfs(j,visited,c)
        c += 1
dfs(0,[0]*N,1)
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque

N = int(input())
graph = defaultdict(list)
colored = dict()
for _ in range(N-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    colored[(a,b)] = None

MAX = 0
for v in graph.values():
    MAX = max(MAX, len(v))

color_list = list(range(1,MAX+1))
color_node = dict()
for i in range(1,N+1):
    color_node[i] = []

for (a,b) in colored.keys():
    for c in color_list:
        if not c in color_node[a] and not c in color_node[b]:
            colored[(a,b)] = c
            color_node[a].append(c)
            color_node[b].append(c)
            break
        
for v in colored.values():
    print(v)

Submission status: Wrong Answer

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections
N = ri()
edges = collections.defaultdict(list)
for i in range(N-1):
	a, b = rl()
	edges[a-1].append((b-1,i))
	edges[b-1].append((a-1,i))

colors = [-1]*N
ecolors = [-1]*(N-1)
stack = []
stack.append((0, -1))
max_color = 0
while stack:
	node, prev = stack.pop()
	color = 0
	for n, e in edges[node]:
		color += 1
		if n == prev: continue
		stack.append((n, node))
		if colors[node] == color:
			color += 1
		colors[n] = color
		ecolors[e] = color
	max_color = max(max_color, color)

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

Submission status: Wrong Answer

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections
N = ri()
edges = collections.defaultdict(list)
for i in range(N-1):
	a, b = rl()
	edges[a-1].append(b-1)
	edges[b-1].append(a-1)

colors = [-1]*N
stack = []
stack.append((0, -1))
max_color = 0
while stack:
	node, prev = stack.pop()
	color = 0
	for n in edges[node]:
		color += 1
		if n == prev: continue
		stack.append((n, node))
		if colors[node] == color:
			color += 1
		colors[n] = color
	max_color = max(max_color, color)

print(max_color)
for i in range(1,N):
	print(colors[i])

Submission status: Wrong Answer

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    cnt = [0 for _ in range(N)]
    for a, b in edge:
        cnt[a] += 1
        cnt[b] += 1

    C = max(cnt)
    print(C)
    used = [[] for _ in range(N)]
    for a, b in edge:
        for i in range(1, C + 1):
            if (i not in used[a]) and (i not in used[b]):
                res = i
                break
        used[a].append(res)
        used[b].append(res)
        print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def search(x,col_befedge):
    #print("top", x, count)
    global col

    k=1
    for n in adj[x]:
        
        e=tuple(sorted((n,x)))
        #print(e,k,col_befedge)
        if col[e]>0:
            continue
        if k==col_befedge:
            k+=1
        #if k==col_pa:
        #    k+=1
        
        col[e]=k
        search(n,k)
        k+=1
    
            
        

N=int(input())

adj=[[] for i in range(N+1)]

edges=[]
col={}
for i in range(N-1):
    tmp=acinput()
    adj[tmp[0]].append(tmp[1])
    
    adj[tmp[1]].append(tmp[0])
    col[tuple(sorted(tmp))]=0
    edges.append(tuple(sorted(tmp)))

    
#col=[-1]*(N+1)

#col[1]=1
#print(adj)

search(1,0)
#print(reduce(lambda a,b:max(a,b),col.keys))
print(col[max(col)])
for se in edges:
    print(col[se])

Submission status: Wrong Answer

Solution code:
N = int(input()) 
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
for vertex in connected:
    used = [0] * colors
    for side in vertex:
        if ans[side[1]]:
            used[ans[side[1]]-1] = 1
        else:
            ans[side[1]] = used.index(0)+1
            used[ans[side[1]]-1] = 1
for i in range(N-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input()) 
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
for vertex in connected:
    used = [0] * colors
    for side in vertex:
        if ans[side[1]]:
            used[ans[side[1]]-1] = 1
        else:
            ans[side[1]] = used.index(0)+1
            used[ans[side[1]]-1] = 1
for color in ans:
    print(color)

Submission status: Wrong Answer

Solution code:
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
for vertex in connected:
    used = [0] * colors
    for side in vertex:
        if ans[side[1]]:
            used[ans[side[1]]-1] = 1
        else:
            ans[side[1]] = used.index(0)+1
            used[ans[side[1]]-1] = 1
for color in ans:
    print(color)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import deque
INF = 1145141919810364364334
n = int(input())
c = []
b = [0] * (n-1)
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b[i] = map(int,input().split())
    edge[a-1].append(b[i]-1)
    edge[b[i]-1].append(a-1)
    c.append(a)
    c.append(b[i])

d = Counter(c)
hen = d.most_common()[0][1]

col = [INF] * n
col[0] = hen+1

q = deque()
q.append(0)

while q:
    x = q.popleft()
    no = 0
    for i in edge[x]:
        if col[i] == INF:
            q.append(i)
            no += 1
            if no == col[x]:
                no += 1
            col[i] = no
            
ans = [0]*(n-1)
for i in range(n-1):
    ans[b[i]-2] = col[i+1]
print(hen)
for i in range(n-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
dev = {}
for n in range(1,N+1):
  dev[n] = 0
for _ in range(N-1):
    a,b  = map(int,input().split())
    ab.append(tuple((a,b)))
    dev[a] += 1
    dev[b] += 1
dev = list(dev.items())
max_dev = max(list(zip(*dev))[1])
print(max_dev)
color = 1
print(color)
pre_a,pre_b = ab[0]
for i in range(1,N-1):
  a,b = ab[i]
  if a in (pre_a,pre_b) or b in (pre_a,pre_b):
    color += 1
  else:
    color =1
  print(color)
  pre_a,pre_b = a,b

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque
 
N = int(stdin.readline().rstrip())
adj = defaultdict(set)
 
for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
visited = [False]*(N+1)
color_edges = [0]*(N+1)
visit_p = deque()
visit_p.append((1,0))
edges_num = 1
 
while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        edges_num += 1
        color_edges[edges_num] = cnt
        visit_p.append((i,cnt))
print(max(color_edges))
for i in color_edges[2:]:
    print(i)

Submission status: Wrong Answer

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

for i in range(N-1):
  a=ab[i][0]
  b=ab[i][1]
  cnt[a-1]+=1
  cnt[b-1]+=1
  link[a-1].append(b)
  link[b-1].append(a)
K=max(cnt)
print(K)

colors=[[] for _ in range(N)]
for i in range(N-1):
  a=ab[i][0]
  b=ab[i][1]
  if len(colors[a-1])==0:
    print(1)
    colors[a-1].append(1)
    colors[b-1].append(1)
    continue
  for j in range(1,K+1):
    if not j in colors[a-1]:
      colors[a-1].append(j)
      colors[b-1].append(j)
      print(j)
      break

Submission status: Wrong Answer

Solution code:
N = int(input())
H = sorted([list(map(int,input().split())) for k in range(N-1)])
C = [0]*N
for e in H:
    a, b = e[0]-1, e[1]-1
    C[a] += 1
    C[b] += 1
M = max(C)
print(M)
U = [set([]) for k in range(N)]
ans = []
for e in H:
    for k in range(1,M+1):
        if (k not in U[e[0]-1]) and (k not in U[e[1]-1]):
            ans.append(k)
            U[e[0]-1].add(k)
            U[e[1]-1].add(k)
            break
for e in ans:
    print(e)

Submission status: Wrong Answer

Solution code:
N = int(input())
H = [list(map(int,input().split())) for k in range(N-1)]
C = [0]*N
T = [[] for k in range(N)]
for e in H:
    a, b = e[0]-1, e[1]-1
    C[a] += 1
    C[b] += 1
    T[a].append(b)
    T[b].append(a)

M = max(C)
print(M)
U = [set([]) for k in range(N)]
ans = []
for e in H:
    for k in range(1,M+1):
        if (k not in U[e[0]-1]) and (k not in U[e[1]-1]):
            ans.append(k)
            U[e[0]-1].add(k)
            U[e[1]-1].add(k)
            break
for e in ans:
    print(e)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque
 
N = int(stdin.readline().rstrip())
adj = defaultdict(set)
 
for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
visited = [False]*(N+1)
color_edges = [0]*(N+1)
visit_p = deque()
visit_p.append((1,1))
edges_num = 1
 
while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    color_edges[edges_num] = color
    edges_num += 1
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        visit_p.append((i,cnt))
print(max(color_edges[:-1]))
for i in color_edges[1:-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
visited = [False]*(N+1)
color_edges = [0]*(N+1)
visit_p = deque()
visit_p.append((1,0))

while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    color_edges[node] = color
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        visit_p.append((i,cnt))
print(max(color_edges))
for i in color_edges[2:]:
    print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
visited = [False]*(N+1)
color_edges = [0]*(N+1)
visit_p = deque()
visit_p.append((1,1))

while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    color_edges[node] = color
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        visit_p.append((i,cnt))
print(max(color_edges))
for i in color_edges[2:]:
    print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
visited = [False]*(N+1)
color_edges = [0]*(N+1)
visit_p = deque()
visit_p.append((1,1))

while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    color_edges[node] = color
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        visit_p.append((i,cnt))
for i in color_edges[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = [0 for _ in range(N)]
    C = []

    for _ in range(N - 1):
        a, b = map(int, input().split())
        A[a - 1] += 1
        A[b - 1] += 1
        C.append([a, b])
    S = max(A)
    print(S)
    B = [0 for _ in range(N - 1)]
    check = [[0] for _ in range(N)]
    for i in range(N - 1):
        c = C[i]
        a = c[0]
        b = c[1]
        if len(check[a - 1]) > 1 or len(check[b - 1]) > 1:
            if (1 in check[a - 1]) or (1 in check[b - 1]):
                x = max(check[a - 1])
                y = max(check[b - 1])
                B[i] = max(x, y) + 1
            else:
                B[i] = 1
            check[a - 1].append(B[i])
            check[b - 1].append(B[i])
        else:
            B[i] = 1
            check[a - 1].append(1)
            check[b - 1].append(1)

    print(*B, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    points = []
    edges = {i: [] for i in range(N)}
    color = {}
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)
        points.append((a, b))
        color[(a, b)] = None

    edges = sorted(edges.items(), reverse=True, key=lambda x: len(x[1]))
    K = len(edges[0][1])

    for a, edge in edges:
        used = [0] * K
        for b in edge:
            if a > b:
                i = b
                j = a
            else:
                i = a
                j = b
            if color[(i, j)] is not None:
                used[color[(i, j)]] = 1

        for b in edge:
            if a > b:
                i = b
                j = a
            else:
                i = a
                j = b
            if 0 not in used:
                break
            if color[(i, j)] is None:
                k = used.index(0)
                color[(i, j)] = k
                used[k] = 1

    print(K)
    for p in points:
        c = color[p]
        print(c + 1)


if __name__ == "__main__":
    main()