Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Accepted

Solution code:
# -*- 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()
		mark = 0
		for j in mi:
			for ii in range(mark,ansInt+1):
				if ii in dame:
					pass
				else:
					ans[inp[(i,j)]] = ii
					dame.append(ii)
					break
				mark += 1
		#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: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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: Accepted

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,pre_color):
    color_num = -1
    for route in routes[num]:
        color_num += 1
        if color_num == pre_color:
            color_num+=1
        if route_color[route[1]] != -10e+10:
            color_num-=1
            pass
        else:
            route_color[route[1]] = color_num
            
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0],route_color[route[1]])
    return

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

Submission status: Accepted

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


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

for _ in range(N-1):
    a, b = map(int, readline().split())
    AB.append((a, b))
    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))

for a, b in AB:
    if parent[a] == b:
        print(color[a])
    else:
        print(color[b])

Submission status: Accepted

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, prev = d.popleft()
    color = 1 if prev != 1 else 2
    for a, index in graph[point]:
        if ans[index] == 0:
            ans[index] = color
            d.append([a, color])
            color += 1 if prev != color + 1 else 2
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

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 = [0]*(N-1)
q = deque([(0, -1)])
while q:
  v, pc = q.popleft()
  c = 1 if pc != 1 else 2
  for nv, i in G[v]:
    if ans[i] == 0:
      ans[i] = c
      q.append((nv, c))
      c += 1 if c+1 != pc else 2

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

max_color = 0
for i in range(N):
    max_color = max(max_color, len(g[i]))

res = [-1] * (N-1)
d = [-1] * N
que = deque([])
que.append((0, -1))
d[0] = 0
while que:
    v, c = que.popleft()
    color = 1
    if color == c:
        color += 1
    for f, s in g[v]:
        if d[f] == -1:
            d[f] = d[v] + 1
            que.append((f, color))
            res[s] = color
            color += 1
            if color == c:
                color += 1

print(max_color)
for v in res:
    print(v)

Submission status: Accepted

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

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())

d = {}
col_self = [0] * N

for i in range(N):
    d[i] = {}

cond = []
for i in range(N-1):
    cond.append(list(map(int, input().split())))
    a, b = cond[i][0]-1, cond[i][1]-1
    d[a][b] = {'cond':i, 'color':0}

# print(cond)
# print(d)

colors = []
result = [0] * N

for i in range(N):
    num = len(d[i])
    if col_self[i] > 0:
        num += 1

    if num > len(colors):
        colors = list(range(1, num+1))

    idx = 0
    for node in d[i]:
        if colors[idx] == col_self[i]:
            idx += 1
        d[i][node]['color'] = colors[idx]
        col_self[node] = colors[idx]
        result[d[i][node]['cond']] = colors[idx]
        idx += 1

print(len(colors))

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

Submission status: Accepted

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: Accepted

Solution code:
'''catupper
ポイントA.再帰DFSで全ての頂点というか、辺をチェック。
ポイントB.入力に注意。頂点の連結が辺になっている。
辺は頂点を結ぶので(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

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を順番にチェック。
    #全ての頂点をチェックすればオシマイ。
        if to == last:continue
        #来た頂点に戻ろうとしたら、何もしない(条件1)
        if color == ban_color:color += 1
        #いま見ている頂点へ来た辺に使っている色なら、
        #新しい色にする(条件2)
        color_dict[(x, to)] = color
        #使う色をタプルで配列に格納する(作業)
        dfs(to, x, color)
        #深さ優先探索なので深く探索できる限り次から次へと探索する。
        #イメージ的には一つ下の階層の頂点を探索する。
        #次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1#いま見ている頂点から繋がる他の頂点へ行く辺の色として
        #新しい色を用意しておく(注意)
    k = max(k, color-1)    #何色を使ったか、覚えておく。
    #用意した新しい色(上記の注意)は、まだ使っていないから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)　　DFSして始めて、color_dictが出来る

print(k)#まず、必要となる色数を出力
for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    print(color_dict[(a[i], b[i])])
'''  以下の場合分けは不要。
    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: Accepted

Solution code:
'''catupper
ポイントA.再帰DFSで全ての頂点というか、辺をチェック。
ポイントB.入力に注意。頂点の連結が辺になっている。
辺は頂点を結ぶので(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])])
'''

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)    #何色を使ったか、覚えておく。
    #新しくした色は次のDFS用なので、まだ使っていないから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)　　DFSして始めて、color_dictが出来る

print(k)#まず、何色必要かを出力
for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    print(color_dict[(a[i], b[i])])
'''  以下の場合分けは不要。
    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: Accepted

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])])
'''  
    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: Accepted

Solution code:
import sys

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

n = int(input())
edge = [[] for i in range(n)]
a = [0] * n  # 頂点を格納しておく配列
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]:
        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(k)  # まず、何色必要かを出力

for i in range(n - 1):  # 辺の色を1から頂点番号-1まで出力
    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: Accepted

Solution code:
'''catupper

'''

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

n = int(input())
edge = [[] for i in range(n)]
a = [0] * n#頂点を格納しておく配列
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]:
        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(k)#まず、何色必要かを出力

for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    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: Accepted

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, 0)
    print(max(ans))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    # BFS
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  # from_node, to_node, color
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored[n[1]] = 1
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if explored[next_to_node] == 1:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    # print answer
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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:
        #これがないとサンプルはOKだが、他はダメ。
        #複数の連結先がある場合がダメか？
        #使った色と同じだった場合、新しい色にするということか？
            color += 1
print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

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:
        #これがないとサンプルはOKだが、他はダメ。
        #複数の連結先がある場合がダメか？
            color += 1
print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [None for _ in range(N)]
colored = {}

def colors_except(x):
  for c in colors:
    if c == x:
      continue
    yield c

for v in range(N):
  unused_colors = colors_except(usedcolor[v])
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = next(unused_colors)
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print(colored[(a, b)])

Submission status: Accepted

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

G = {}

for i in range(1,N+1):
    G[i] = []

for i in range(N-1):
    G[data[i][0]].append((data[i][1],i+1))
    G[data[i][1]].append((data[i][0],i+1))

M = max(len(G[i]) for i in range(1,N+1))

print(M)

from collections import deque

E = [0]+[-1]*(N-1)  #辺
E[1] = 1
q = deque([[data[0][0],1],[data[0][1],1]])

while q:
    n,i = q.pop()
    c = 1
    for dn,di in G[n]:
        if E[di] != -1:
            continue
        else:
            if c == E[i]:
                E[di] = M
                c += 1
                q.append([dn,di])
            else:
                E[di] = c
                c += 1
                q.append([dn,di])
for i in range(1,N):
    print(E[i])

Submission status: Accepted

Solution code:
"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

connection = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    connection[a].add((b, idx))
    connection[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

color_edge = [-1] * n  # color_edge[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    color_now = 1 if prev_color != 1 else 2
    for u, u_idx in connection[v]:
        if used[u]:
            continue
        used[u] = True
        color_edge[u_idx] = color_now
        q.append((u, u_idx, color_now))
        color_now += 1
        if color_now == prev_color:
            color_now += 1

ret = color_edge[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')

Submission status: Accepted

Solution code:
"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

n=int(input())

#初期値が0の辞書
from collections import defaultdict
tree = defaultdict(lambda: set([])) 

color={}
key=[]

for _ in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
    color[(a-1,b-1)]=0
    key.append((a-1,b-1))

checked=[0]*n
cnt=0

def DEF(parent_color,node_no):
    global color,checked,tree,cnt
    checked[node_no]=1
    cnt=max(cnt,parent_color)
    i=1
    #print("node_no",node_no)
    for item in tree[node_no]:
        if checked[item]==0:
            if i==parent_color:
                i+=1
            
            color[(min(item,node_no),max(item,node_no))]=i
            DEF(i,item)
            i+=1
DEF(0,1)

print(cnt)
for item in key:
    print(color[item])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

data = [[] for i in range(N)]


for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append((i,b))###(edge no.,edgeの行き先)
    data[b].append((i,a))###(edge no.,edgeの行き先)

l = 0

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

print(l)

stack = deque([(0,-1)]) ###(頂点番号, 前の頂点からきた色)
visit = [0]*N
visit[0] = 1
color = [0]*(N-1)

while stack:
    x = stack.pop()
    c = 1
    for y in data[x[0]]:
        if visit[y[1]] == 1:
            continue
        else:
            visit[y[1]] = 1
            if c != x[1]:
                color[y[0]]=c
                stack.append((y[1],c))
                c += 1
            else:
                color[y[0]]=c+1
                stack.append((y[1],c+1))
                c += 2

#print(color)
for i in range(N-1):
    print(color[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=int(input())

def dfs(u,par):
  col=1
  for v in graph[u]:
    if col==par:
      col+=1
    color_dic[(u,v)]=col
    dfs(v,col)
    col+=1

elist=[]
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
  a,b=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b))
#print(graph)

color_dic={}
dfs(1,-1)
#print(color_dic)

K=len(set(color_dic.values()))
print(K)
for e in elist:
  print(color_dic[e])

Submission status: Accepted

Solution code:
import queue

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

#A[i]=辺iの色
A=[0]*N
q=queue.Queue()

#bfs
#(ノード、色、親)
q.put((1,0,0))
while not q.empty():
    now=q.get()
    i=1 #色
    for next in G[now[0]]:
        if next[0]==now[2]: #親
            continue
        else:
            if i==now[1]:
                i+=1
            A[next[1]]=i    #色を定める
            q.put((next[0],i,now[0]))
            i+=1

    #print(now,(next[0],i,now[0]))


print(max(A))
for j in range(N-1):
    print(A[j+1])