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:
# -*- 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)]])
		for j in mi:
			for ii in range(ansInt+1):
				ans[inp[(i,j)]] = ii
				dame.append(ii)
				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()

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 = []
		for j in ko:
			#print("{} {} {}".format(i,j,ko))
			if i < j:
				for ii in range(ansInt+1):
					tmp = bisect_right(dame, ii)
					if ii in dame:
						pass
					else:
						ans[inp[(i,j)]] = ii
						dame.append(ii)
						break
			else:
				dame.append(ans[inp[(j,i)]])
		#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()

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(max(color[a-1]),max(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:
import sys
input = sys.stdin.readline
N = int(input())
color = [[0] for _ in range(N)]
ans = []
for i in range(N-1):
    flg = True
    a, b = map(int, input().split())
    target = max(max(color[a-1]),max(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.append(k)
            color[a-1].append(k)
            color[b-1].append(k)
            flg = False
            break
    if flg:
        ans.append(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())
color = [[0] for _ in range(N)]
ans = []
for i in range(N-1):
    flg = True
    a, b = map(int, input().split())
    target = max(max(color[a-1]),max(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.append(k)
            color[a-1].append(k)
            color[b-1].append(k)
            flg = False
            break
    if flg:
        ans.append(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())
color = [[0] for _ in range(N)]
ans = []
for i in range(N-1):
    flg = True
    a, b = map(int, input().split())
    target = max(max(color[a-1]),max(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.append(k)
            color[a-1].append(k)
            color[b-1].append(k)
            flg = False
            break
    if flg:
        ans.append(target)
        color[a-1].append(target)
        color[b-1].append(target)
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

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):
    color_num = 0
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            color_num+=1
        else:
            route_color[route[1]] = color_num
            color_num+=1
        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: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(readline())
graph = [[] for _ in range(N+1)]

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

parent = [0] * (N+1)
root = 1
stack = [root]
color = [0] * (N+1)
while stack:
    x = stack.pop()
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        parent[y] = x
        color[y] = c
        c += 1
        stack.append(y)

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

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
from copy import deepcopy
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)
    max_edges_per_node = 0
    edges_next = deque([1])
    edges_next_next = deque()
    edges_seen = set()
    while len(edges_seen) < n:
        while edges_next:
            e = edges_next.pop()
            if e in edges_seen:
                continue
            else:
                edges_seen.add(e)
                num_of_nodes = len(nodes_edges_data[e])
                max_edges_per_node = max(max_edges_per_node, num_of_nodes)
                edge_adj = nodes_edges_data[e]
                colors = [i for i in range(max_edges_per_node)]
                for ea in edge_adj:
                    if edges_color[edges_data_to_number[(e, ea)]] in colors:
                        colors.pop(colors.index(edges_color[edges_data_to_number[(e, ea)]]))
                    elif edges_color[edges_data_to_number[(ea, e)]] in colors:
                        colors.pop(colors.index(edges_color[edges_data_to_number[(ea, e)]]))
                    else:
                        edges_color[edges_data_to_number[(ea, e)]] = min(colors)
                        colors.pop(colors.index(min(colors)))
                edges_next_next += edge_adj

        edges_next_next_set = set(edges_next_next)
        edges_next += list(edges_next_next_set - edges_seen)
        edges_next_next = deque()

    # 出力
    print(max(edges_color) + 1)
    for ea in edges_color:
        print(ea + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

tree = [[] for _ in range(n)]
color = [i for i in range(1, n)]
ans = []
for a, b in ab:
    for i in color:
        if not i in tree[a-1] and not i in tree[b-1]:
            tree[a-1].append(i)
            tree[b-1].append(i)
            ans.append(i)
            break

length = 0
for i in tree:
    length = max(length, len(i))
print(length)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append((b - 1, i))
    graph[b - 1].append((a - 1, i))
ans = [0] * (n - 1)

from collections import deque

d = deque()
d.append([0, -1])
while d:
    point, color = d.popleft()
    color = 1 if color != 1 else 2
    for a, index in graph[point]:
        if ans[index] == 0:
            ans[index] = color
            d.append([a, color])
            color += 1
print(max(ans))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
point = [0] * n
ans = []
edge = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    point[a - 1] += 1
    point[b - 1] += 1
    edge.append([a - 1, b - 1])
m = max(point)
print(m)
prev = [1] * n
for a, b in edge:
    t = max(prev[a], prev[b])
    print(t)
    prev[a] = ((t) % m) + 1
    prev[b] = ((t) % m) + 1

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = [tuple(map(int, input().split())) for _ in range(n - 1)]
count = [0] * n
for a, b in graph:
    a, b = a - 1, b - 1
    count[a] += 1
    count[b] += 1
color_max = max(count)
print(color_max)

color = [[0] * color_max for _ in range(n)]
for a, b in graph:
    a, b = a - 1, b - 1
    for i in range(color_max):
        if color[a][i] == 0 and color[b][i] == 0:
            print(i + 1)
            color[a][i] = 1
            color[b][i] = 1
            break

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)]
	ans = [inf for i in range(N)]
	ans[0] = 0

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

	#print(ki)
	for i in range(N):
		#print(ans)
		ko = ki[i]
		dame = ans[i]
		for j in ko:
			if ans[j] == inf:
				for ii in range(N):
					if ii == dame:
						continue
					else:
						ans[j] = ii
						break

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

Submission status: Wrong Answer

Solution code:
#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
#from collections import deque
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[[i] for i in range(N-1)]
A_sort =sorted(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_sort[i].append((a,b))             #色を出力するため
A_sort.sort(key=lambda x:x[1])
#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
aa=[]
hq_none =heapq.heapify(aa)
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理,dequeで高速？
for i in range(1,N+1):
    heapq.heapify(color_node[i])
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A_sort[i][1] #i番目の辺とつながっている頂点
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(-1)*(color_node[n_a][0]) +1
    while True:
        #color +=1
        q,color =divmod(color,color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            #color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            A_sort[i].append(color+1)     #辺の色を出力用に決める。1～color_max,A_sortに入れて、再度ソート
            heapq.heappush(color_node[n_a],color*(-1))    #前の頂点に使った色を追加、
            heapq.heappush(color_node[n_b],color*(-1))    #heapqの最大値出したいので*(-1)

            break
        else:
            color +=1      
#出力
print(color_max)
A_sort.sort()
for i in A_sort:
    print(i[2])

Submission status: Wrong Answer

Solution code:
#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
#from collections import deque
import heapq
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) )

#各頂点に色を準備⇒辺の色決定
aa=[]
hq_none =heapq.heapify(aa)
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理,dequeで高速？
for i in range(1,N+1):
    heapq.heapify(color_node[i])
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A[i] #i番目の辺とつながっている頂点
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(-1)*(color_node[n_a][0]) +1
    while True:
        #color +=1
        q,color =divmod(color,color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            heapq.heappush(color_node[n_a],color*(-1))    #前の頂点に使った色を追加、heapqの最大値出したいので*(-1)
            heapq.heappush(color_node[n_b],color*(-1))    #前の頂点に使った色を追加

            break
        else:
            color +=1      
#出力
print(color_max)
print(*color_edge, sep="\n")

Submission status: Wrong Answer

Solution code:
'''catupper
ポイントA.再帰DFSを使う。
ポイントB.入力に注意。
辺は頂点を結ぶので(a[i], b[i])で表現され、対応する色を
color_dict[(a[i], b[i])]としている。
配列が二重配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):    if (a[i], b[i]) in color_dict:
'''

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

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

color_dict = {}#色を覚えておく
k = 0

def dfs(x, last = -1, ban_color = -1):
#lastは、どこから来たか、逆走を防ぐ。使っちゃいけない色も引数
    global k#グローバル変数
    color = 1
    for to in edge[x]:
    #配列edgeに格納されている次の頂点toを順番にチェック
        if to == last:continue
        #来た頂点に戻ろうとしたら、何もしない
        if color == ban_color:color += 1
        #使っちゃいけない色なら、新しい色にする
        color_dict[(x, to)] = color
        dfs(to, x, color)
        #次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1#色を新しくする
    k = max(k, color-1)#何色を使ったか、覚えておく

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

dfs(0)#最初の頂点をDFSに入れてスタート
#print(color_dict)

print(k)#まず、何色必要かを出力

for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    print(color_dict[(a[i], b[i])],1)
'''  
    if (a[i], b[i]) in color_dict:#辞書から答を出力
        print(color_dict[(a[i], b[i])],1)
    else:
        print(color_dict[(b[i], a[i])])
'''

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    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
    c = collections.Counter(g)
    mode = c.most_common()[0][1]
    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:
import sys

sys.setrecursionlimit(10 ** 9)
if __name__ == '__main__':
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        tree[a - 1].append([b - 1, i])

    ans = 0
    for i in tree:
        ans = max(ans, len(i))

    ans = [0] * (n - 1)


    def solve(cur_index, color):
        cnt = 1

        for to, j in tree[cur_index]:
            if cnt == color:
                cnt += 1
            ans[j] = cnt
            solve(to, cnt)
            cnt += 1


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

Submission status: Wrong Answer

Solution code:
'''ika tako  色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、
まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
 |           `-- 3 ---⑥
 |--- 2 ---③--- 1 ---⑦
 |           `-- 3 ---⑧
 `--- 3 ---④--- 1 ---⑨
             `-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず
未確定である（後でその頂点の処理時に何とでも調整できる）ので、
この方法が使える。
'''
import sys
 
n = int(input())#頂点数
links = [set() for _ in range(n)]#この入力はABC166Cでも使う
for i, line in enumerate(sys.stdin):
    a, b = map(int, line.split())
    a -= 1#0-indexへ、abc165Cも同様
    b -= 1
    links[a].add((i, b))
    #リストlinksの中身のa番目のセットにindexと共に連結先を追加add
    links[b].add((i, a))

ans = [-1] * (n - 1)#初期値は存在しえない数値、頂点-1個で足りる
k = max(map(len, links))#リストlinksの長さの最大(セットの要素数の最大)
q = [(0, -1)]
fixed = set()
 
while q:
    v, c = q.pop()#頂点vと色cをキューから取り出す
    color = 1
    if c == color:#取り出した色が使っている色なら、新しい色を使う
        color += 1
    for i, u in links[v]:#リストlinksからindexと連結先を取り出す
        if ans[i] != -1:#色が決まっていたら何もしない
            continue
        ans[i] = color#色を決めて、ansに入れる
        q.append((u, color))#キューに連結先と使った色を入れる
        color += 1#色を新しい色にしておく
        #if c == color:#これがないと入力例３の出力順が変わる
            #color += 1
print(k)
print('\n'.join(map(str, ans)))