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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = i

# DFSで木の走査(開始位置はどこでもいい)
# (自分, 親, 親との辺の色)
stack = [(0, -1, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev, used = stack.pop()
    color = 0
    # 自分の子ノードを順番に塗り進めていく
    for v in nodes[u]:
        if v == prev:
            continue
        color += 1
        # 親-自分間で使用済の色だったら1つ進める
        if color == used:
            color += 1
        a, b = min(u, v), max(u, v)
        i = edges[(a, b)]
        ans[i] = str(color)
        stack.append((v, u, color))
    # 各ノードから使った色数の最大を取る
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(min(a,b),max(a,b))]=i
    ans=[None]*(n-1)

    def dfs(v=0,p=-1,c=0):
        col=1
        for nv in E[v]:
            col+=col==c
            if(nv==p): continue
            ans[idx[(min(v,nv),max(v,nv))]]=col
            dfs(nv,v,col)
            col+=1
    dfs()
    print(max(ans))
    print(*ans,sep='\n')
resolve()

Submission status: Accepted

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

Q = [(0, -1)]
ANS = [-1] * (N-1)
while Q:
    x, c0 = Q.pop()
    
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n-1)] 
graph = [[] for _ in range(n+1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)


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

color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1


ans = [] 
for a, b in ab:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

k = max(ans)
print(k)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        idx[(a,b)]=i
    ans=[None]*(n-1)

    # coloring
    Q=[(0,0)]
    while(Q):
        v,c=Q.pop()
        cnt=1
        for nv in E[v]:
            cnt+=cnt==c # 親との辺の色と被るときは1増やす
            ans[idx[(v,nv)]]=cnt
            Q.append((nv,cnt))
            cnt+=1

    print(max(ans))
    print(*ans,sep='\n')
resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


def main():
    N = int(input().strip())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().strip().split())
        edges[a-1].append([b-1, i])
        edges[b-1].append([a-1, i])
    color = [-1 for i in range(N-1)]
    trgt = deque([[0, -1], ])
    while len(trgt) > 0:
        now, parent_color = trgt.pop()
        cand_color = 0
        for node, edge_num in edges[now]:
            if color[edge_num] == -1:
                cand_color += 1
                if cand_color == parent_color:
                    cand_color += 1
                color[edge_num] = cand_color
                trgt.append([node, cand_color])
    print(max(color))
    print("\n".join(map(str, color)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N-1)]
Path=[[] for i in range(N)]
for p in P:
  Path[p[0]-1].append(p[1]-1)
  Path[p[1]-1].append(p[0]-1)
colornum=1
dic={}
def bfs(nodes,p,pcolor,selfnum):
  global colornum
  if len(nodes)-1==0 and p!=-1:
    return
  c=1
  for n in nodes:
    if n == p:
      continue
    if c==pcolor:
      c+=1
    dic[(selfnum+1,n+1)]=c
    dic[(n+1,selfnum+1)]=c
    bfs(Path[n],selfnum,c,n)
    c+=1
  if c>colornum:
    colornum=c
bfs(Path[0],-1,0,0)
print(colornum-1)
for p in P:
  print(dic[p])

Submission status: Accepted

Solution code:
from collections import  deque
import time
N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]

ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1], 1))
dicans = {}

while len(q) > 0:
    i, l, c= q.popleft()
    num = c
    for k in l:
        if k < i:
            continue
        num += 1
        if num > ans1:
            num = 1
        dicans[(i, k)] = num
        q.append((k, dic[k], num))

print(ans1)

for a, b in A:
    print(dicans[(a, b)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def main():
    n = int(input())
    color = [None]*(n-1)
    color[0] = -1

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

    def dfs(now=0, prev=-1, mycolor=-1):
        in_use = {mycolor}
        i = 0

        for tup in con[now]:
            if tup[0] != prev:
                while True:
                    if i not in in_use:
                        color[tup[1]] = i
                        in_use.add(i)
                        break
                    i += 1
                dfs(tup[0], now, i)

    dfs()

    print(max(color)+1)
    for i in color:
        print(i+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs():
    q = deque()
    q.append((0, 0))

    while len(q):
        v, pc = q.popleft()
        color = 1

        for e in edge[v]:
            if color == pc:
                color += 1

            if ec[e[1]] == 0:
                ec[e[1]] = color
                q.append((e[0], color))
                color += 1


bfs()
print(max(ec))
for c in ec:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N=int(input())
Graph = [ [] for ii in range(N) ]

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

ans = [None]*(N-1)
def rec(cur, color):
    cnt = 1
    for (to, jj) in Graph[cur]:
        if cnt==color:
            cnt+=1
        ans[jj] = cnt
        rec(to, cnt)
        cnt += 1

rec(0, 0)
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for i 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])

ans = [None]*(n-1)
def rec(cur,color):

    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n=int(input())
l=[[]for i in range(n)]
ans=set()
ll=[set() for i in range(n)]
c=1
ab=[]
from collections import Counter
ans2=Counter()
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    ab.append((a,b))
    l[a].append(b)
    #l[b].append(a)

for i in range(n):
    c=1
    for j in l[i]:
        while True:
            if (c not in ll[j]) and (c not in ll[i]):
                ll[j].add(c)
                ll[i].add(c)
                ans.add(c)
                ans2[(i,j)]=c
                break
            else:
                c+=1
print(len(ans))
#print(ans)
#print(ans2)
for i,j in ab:
    print(ans2[(i,j)])

Submission status: Accepted

Solution code:
N = int(input())

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])

max_color = -1

# print(adj_dict)

# Create a queue for BFS
queue = [1]

# Mark the source node as
# visited and enqueue it

painted = {}


while queue:

    # Dequeue a vertex from
    # queue and print it
    s = queue.pop(0)

    # Get all adjacent vertices of the
    # dequeued vertex s. If a adjacent
    # has not been visited, then mark it
    # visited and enqueue it
    if s not in adj_dict:
        continue

    for i in range(len(adj_dict[s])):
        color = 1 + i
        if painted.get(s) is not None:
            if 0 < painted[s] <= color:
                color += 1
        # print(s, i)
        painted[adj_dict[s][i]] = color
        max_color = max(max_color, color)
        queue.append(adj_dict[s][i])

print(max_color)

for edg in edge_list:
    print(painted[edg[1]])


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

5
1
2
3
1
4
1
3
5
'''

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

N = ni()
AB = [na() for _ in range(N-1)]
graph = [[] for _ in range(N+1)]

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
for o in order:
    ng = color[o]
    c = 1
    for y in graph[o]:
        if y == parent[o]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1
answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(answer))
print('\n'.join(map(str,answer)))

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

N = int(input())

# ある辺の両端のノードの番号の和(必ず片方のノード番号はわかっているのでこれで通じる)
branch_add = np.zeros(N, dtype="int")

ans = np.zeros(N - 1)

# 頂点から見た辺の個数の計算
appeard = np.zeros(N, dtype="int")

# 2次元配列ではメモリが不足しそうなので多重配列で接続先の辺の情報を記録する
branch_list = [[] for _ in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    branch_add[i] = a + b
    appeard[a] += 1
    appeard[b] += 1
    # 頂点の接続先の情報
    branch_list[a].append(i)
    branch_list[b].append(i)

# あるノードから一番多く伸びている枝の数が色の数
color_num = np.max(appeard)

start_node = (np.where(appeard == color_num)[0])[0]

# 幅優先探索で色塗りを行う。変数は順番に「色を塗る辺がある頂点、色を塗った辺の番号、その色」
color_queue = deque()

# 最初のノードの色を塗る
for c, i in enumerate(branch_list[start_node]):
    color_queue.append([branch_add[i] - start_node, i, c])
    ans[i] = c

while len(color_queue) > 0:
    next_queue = color_queue.popleft()
    node = next_queue[0]
    colored_branch = next_queue[1]
    color = next_queue[2]
    color_index = 0
    for i in branch_list[node]:
        # 色を塗ったノードは無視
        if i == colored_branch:
            continue
        # 同じ色では塗らない
        if color_index == color:
            color_index += 1
        color_queue.append([branch_add[i] - node, i, color_index])
        ans[i] = color_index
        color_index += 1

print(color_num)

for i in range(N - 1):
    # 色の情報は1から始まることに注意
    print(int(ans[i] + 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N=int(input())
val=[list(map(int, input().split())) for i in range(N-1)]

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[0]*(N-1)
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=1
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp
    coltemp+=1
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            coltemp=1
            que[i+1] |= arrtemp
            for f in arrtemp:
                while(1):
                    if coltemp not in col[t]:
                        break
                    coltemp+=1
                p=coltemp
                coltemp+=1
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])

Submission status: Accepted

Solution code:
def func(iro,tree,num,max_color):
  if num not in tree:
    return
  
  my_color = iro[num]
  arr = tree[num]
  
  for i in arr:
    my_color += 1
    iro[i] = my_color % max_color
    func(iro,tree,i,max_color)
    

n = int(input())
tree = {}

b_arr = []
for i in range(n-1):
  a,b = map(int,input().split())
  
  b_arr.append(b)
  if a not in tree:
    tree[a] = []
    
  tree[a].append(b)
  
color = len(tree[1])
for key,arr in sorted(tree.items()):
  if key == 1:
    continue
    
  color = max(len(arr)+1, color)

print(color)

iro = [-1] * (n+1)

for key,arr in sorted(tree.items()):
  my_color = iro[key]
  for i in arr:
    my_color += 1
    iro[i] = my_color % color

for i in b_arr:
  print(iro[i]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []

class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id

ans = []

def dfs(v, fr, c):
    k = 1
    for g in G[v]:
        to = g.to
        id = g.id
        if to != fr:
            if k == c:
                k += 1
            ans[id] = k
            k += 1
            dfs(to, v, ans[id])
    

def main():
    global G, ans
    n = int(input().strip())
    ans = [0] * (n-1)
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int, input().strip().split()))
        G[a-1].append(Edge(b-1, i))
        G[b-1].append(Edge(a-1, i))
    dfs(0, -1, -1)

    print(len(set(ans)))
    for v in ans:
        print(v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        
    q = collections.deque([(0,1,0)])#親、子、色
    ans=dict()
    while q:
        parent,togo,old_color = q.popleft()
    #    print(parent,togo,old_color)
        col=1
        for togotogo in tree[togo-1]:
    #        print(togotogo)
            if togotogo == parent:
                continue
            if col == old_color:
                col+=1
            q.append((togo,togotogo,col))
            ans["_".join(map(str,(togo,togotogo)))]=col
            col+=1
        
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = int(readline())
    ab = map(int, read().split())
    ab = list(zip(ab, ab))
    g = [[] for _ in range(n+1)]
    for a, b in ab:
        g[a].append(b)
        g[b].append(a)

    parent = [0]*(n+1)
    color, maxc = [0]*(n+1), 0
    stack = [1]
    while stack:
        p = stack.pop()
        children = g[p]
        c, notc = 1, color[p]
        for child in children:
            if child==parent[p]:
                continue
            parent[child] = p
            stack.append(child)

            c = c+1 if c==notc else c
            color[child] = c
            maxc = c if maxc<c else maxc
            c+=1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
e=[[] for _ in range(n)]
a=[0]*n
b=[0]*n
d={}
def dfs(x,last=-1,ban=-1):
    c=1
    for to in e[x]:
        if to==last:
            continue
        if c==ban:
            c+=1
        d[(x,to)]=c
        dfs(to,x,c)
        c+=1

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

dfs(0)
print(max(d.values()))
for i in range(n-1):
    if (a[i],b[i]) in d:
        print(d[(a[i],b[i])])
    else:
        print(d[(b[i],a[i])])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[-1]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]<0:
            if visited[v]==j:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.append(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans = {}
tmp = []
flag = [False] * N  # そのノードに到達済みか判定する
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    tmp.append((a, b))  # 最後に出力する時に使う
    ans[(a, b)] = -1
q = deque([0])  # 開始のノード
colors = [-1]*N
now_color = 0
while len(q):
    v = q.pop()
    flag[v] = True
    color = 1
    # vからeへの辺の色を塗る
    for e in graph[v]:

        if flag[e]:
            continue
        q.append(e)
        if color == colors[v]:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[-1]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]<0:
            if j==visited[v]:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.appendleft(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())

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

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

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

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

print(max(colors))
for c in colors:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())

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

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

ans = [0] * (N - 1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1


dfs(-1, 1, -1)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
tree = [[] for i in range(N)]  # 入力で与えられる木: [[to, 辺のindex],]
degrees = defaultdict(int)  # 各頂点の次数を記録

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


# 最大次数色使えば必ず塗り分けられる
ans_K = max(degrees.values())
ans_c = [-1] * (N - 1)


# [現在見ている頂点, 直前を何色で塗ったか]
stack = [[0, -1]]
visited = [False] * N
while stack:
    fr, pre_color = stack.pop()
    visited[fr] = True
    painting = 1  # これから何色で塗ろうとするか

    for to, index in tree[fr]:
        if visited[to]:
            continue

        if painting == pre_color:
            painting += 1

        ans_c[index] = painting
        stack.append([to, painting])

        # 塗ったら違う色に変える
        painting += 1


print(ans_K)
print(*ans_c, sep='\n')

Submission status: Accepted

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

tree = [[] for i in range(n+1)]
for a,b in AB:
	tree[a].append(b)
	tree[b].append(a)

parent = [0]*(n+1)
stack = [1]
while stack:
	v = stack.pop()
	for c in tree[v]:
		if c == parent[v]:
			continue
		parent[c] = v
		stack.append(c)

color = [0]*(n+1)
for i in range(1,n+1):
	cur_col = 1
	par_col = color[i]
	for c in tree[i]:
		if c == parent[i]:
			continue
		if cur_col == par_col:
			cur_col += 1
		color[c] = cur_col
		cur_col += 1
	# print(color)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) # パス先, パスの色でキューに追加
while q:
    v, pc = q.popleft()
    nc = 1 # 使用する色
    for nv, edge in tree[v]: # nv=パス先 edge=abでの順番
        if nc == pc: # 渡ってきたパスの色と同じなら+1した色にする
            nc += 1
        color[edge] = nc # 使用する色を答えのリストに格納
        q.append((nv, nc))
        nc += 1

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) # パス先, パスの色でキューに追加
while q:
    v, pc = q.popleft()
    nc = 0 # 使用する色
    for nv, edge in tree[v]: # nv=パス先 edge=abでの順番
        nc += 1
        if nc == pc: # 渡ってきたパスの色と同じなら+1した色にする
            nc += 1
        color[edge] = nc # 使用する色を答えのリストに格納
        q.append((nv, nc))

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

Submission status: Accepted

Solution code:
def examD():
    N = I()
    AB = [LI() for _ in range(N-1)]
    V = [[] for _ in range(N)]
    for a,b in AB:
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    ans = []
    root = 0
    #親とdfsの順序記録
    parent = [0] * (N)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in V[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
#    print(parent); print(order)
    #辺の色...子の色
    color = [-1]*(N)

    for i in order:
        NG = color[i]
        cur = 1
        for j in V[i]:
            if j == parent[i]:
                continue
            if cur==NG:
                cur +=1
            color[j] = cur
            cur +=1
#    print(color)
    append = ans.append
    for a,b in AB:
        if parent[a-1]==b-1:
            #子の色を塗る
            append(color[a-1])
        else:
            append(color[b-1])
    print(max(ans))
    for v in ans:
        print(v)

def examE():
    N, K = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

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


def main():
    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))

    V = [[-1, -1] for _ in range(N)]  # 頂点の[親, 親への辺の色]
    ans = [-1]*(N-1)
    stack = [0]  # dfsになるはず（キューだとbfs）
    while stack:
        i = stack.pop()
        color = 0
        for c, ei in G[i]:
            if c == V[i][0]:
                continue
            V[c][0] = i
            color += 1
            if color == V[i][1]:
                color += 1
            V[c][1] = ans[ei] = color
            stack.append(c)
    print(max(ans))
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    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))

    V = [[-1, -1] for _ in range(N)]  # 頂点の[親, 親への辺の色]
    ans = [-1]*(N-1)
    import collections
    Q = collections.deque()
    Q.append(0)
    while Q:
        i = Q.popleft()
        color = 0
        for c, ei in G[i]:
            if c == V[i][0]:
                continue
            V[c][0] = i
            color += 1
            if color == V[i][1]:
                color += 1
            V[c][1] = ans[ei] = color
            Q.append(c)
    print(max(ans))
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
edge = [set() for _ in range(N)]
ab = []
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    ab.append((a,b))
    edge[a].add(i)
    edge[b].add(i)

K = 0
ans = [0]*(N-1)
pool = deque([(0,0)])
while pool:
    node, prev = pool.popleft()
    c = 0
    for i in edge[node]:
        c += 1
        if c == prev:
            c += 1
        a, b = ab[i]
        if node == a:
            x = b
        else:
            x = a
        edge[x].remove(i)
        ans[i] = c
        pool.append((x,c))
    if c >= K:
        K = c

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
edge = [set() for _ in range(N)]
ab = []
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    ab.append((a,b))
    edge[a].add(i)
    edge[b].add(i)

K = 0
ans = [0]*(N-1)
pool = [(0,0)]
while pool:
    node, prev = pool.pop()
    c = 0
    for i in edge[node]:
        c += 1
        if c == prev:
            c += 1
        a, b = ab[i]
        if node == a:
            x = b
        else:
            x = a
        edge[x].remove(i)
        ans[i] = c
        pool.append((x,c))
    if c >= K:
        K = c

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

Submission status: Accepted

Solution code:
"""
DFS
"""
# 再帰回数の上限を解除
import sys
sys.setrecursionlimit(10**7)


class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


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

dfs(0)

# 最大次数が色数となる
mx = max([len(g) for g in graph])
print(mx)

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