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:
#problem1
from collections import deque
d=deque()
e=deque()

N=int(input())
graph=[[] for i in range(N+1)]
D=[]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    D.append((a,b))
    
#頂点1からスタート
K=0
d.append(1)
visited=[False for i in range(N+1)]
color=[-1 for i in range(N+1)]
visited[1]=True
color[1]=-1
dic={}
while d:
    while d:
        x=d.popleft()
        par_color=color[x]
        c=1
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                e.append(node)                
                if c!=par_color:
                    color[node]=c
                    dic[(x,node)]=c
                elif c==par_color:
                    c+=1
                    color[node]=c
                    dic[(x,node)]=c
                c+=1
    if e:
        d=e
        e=deque()

A=max(color)
print(A)
for que in D:
    a,b=que
    if (a,b) in dic.keys():
        print(dic[que])
    else:
        print(dic[(b,a)])

Submission status: Accepted

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

ans=[0 for i in range(N-1)]

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline
n = int(input())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append((b, i + 1))
    graph[b].append((a, i + 1))
par = [-1] * (n + 1)
que = deque([(1, -1, -1, -1)])  # edge, color, par, hen_num
color = [-1] * (n)
num = 0  # 使った色の数
while que:
    v, c, p, hen = que.popleft()
    par[v] = p
    color[hen] = c
    cnt = 0
    for i in range(len(graph[v])):
        u, hen_num = graph[v][i]
        if u == par[v]:
            continue
        cnt += 1
        if cnt == c:
            cnt += 1
        color[hen_num] = cnt
        num = max(num, cnt)
        que.append((u, cnt, v, hen_num))
print(num)
print(*color[1:], sep="\n")

Submission status: Accepted

Solution code:
import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
start = 0
color = [[] for _ in range(N+1)]
node[1] = 0
while(True):
    if que.empty():
        break
    before = start
    start = que.get()
    col =1
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
        if edge[i[1]] == -1:
            if col == node[start]:
                col += 1
            edge[i[1]] = col
            node[i[0]] = col
            if col > maxi:
                maxi = col
            col +=1
            
print(maxi)
for i in edge[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([0])

chk = [False] * n
chk[0] = True

res = [0] * n
par = [0] * n
while q:
    x = q.popleft()
    cnt = 1
    for y in g[x]:
        if chk[y]:
            continue
        if res[x] == cnt:
            cnt += 1
        res[y], par[y], chk[y] = cnt, x, True
        cnt += 1
        q.append(y)

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

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
adj = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    adj[a-1].append((b, i))
    adj[b-1].append((a, i))
# print(adj)
color = [0]*N
visited = [False]*N
visited[0] = True
queue = deque([1])
ans = [0]*(N-1)
while queue:
    now = queue.popleft()
    cnt = 1
    for n, e in adj[now-1]:
        if visited[n-1]:
            continue
        if color[now-1] == cnt:
            cnt += 1
        color[n-1] = cnt
        visited[n-1] = True
        ans[e] = cnt
        cnt += 1
        queue.append(n)
print(max(color))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Accepted

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)#Maxの数

col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k #k以下のものを順番に割り当てていく

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

Submission status: Accepted

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

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0]*n
    dq.append(0)
    done[0] = 1
    edgecolor = [0]*(n-1)

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

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
from collections import deque 

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0 for _ in range(n)]
    dq.append(0)
    done[0] = 1
    edgecolor = [0 for _ in range(n-1)]

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

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
from collections import deque 

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0 for _ in range(n)]
    dq.append(0)
    done[0] = 1
    edgecolor = [0 for _ in range(n-1)]

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for i in range(len(g[v])):
            nx = g[v][i].to
            edge_id = g[v][i].id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for i in range(len(g[v])):
            nx = g[v][i].to
            edge_id = g[v][i].id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。辺の本数だけ空を用意する。
ans = [0 for _ in range(N-1)]

Q = deque([])
Q.append(0)
used = [0 for _ in range(N)] #訪れた頂点をここに記録
used[0] = 1
#pre = [-1 for _ in range(N)]

while Q:
  v = Q.popleft()
  #p = pre[v] #vの親
  c = -1
  for i in range(len(g[v])): #vとvの親が繋がっている色を探す。
    TO = g[v][i][0]
    ID = g[v][i][1]
    if used[TO] == 1:
      c = ans[ID]
  k = 1
  for i in range(len(g[v])): #vとつながっている親以外の色を塗っていく。
    TO = g[v][i][0]
    ID = g[v][i][1]
    if used[TO] == 1:
      continue
    if k == c:
      k += 1
    ans[ID] = k
    k += 1
    Q.append(TO)
    used[TO] = 1
    


#bfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b = ab[i]
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    index = -1
    MAX = 0
for i in range(N):
    li = tree[i]
    n = len(li)
    if n > MAX:
        MAX = n
        index = i
d = defaultdict(int)

def dfs(cur,parent,prevcolor):
    li = tree[cur]
    n = len(li)
    if n == 0:
        return
    flag = 0
    for i in range(n):
        chi = li[i]
        if chi == parent:
            flag = 1
            continue
        a = (prevcolor+1+i)%MAX
        if flag == 1:
            a -= 1
        d[(cur,chi)] = a
        d[(chi,cur)] = a
        dfs(chi,cur,a)
dfs(index,-1,0)
print(MAX)
for i in range(N-1):
    a,b = ab[i]
    ans = d[(a-1,b-1)]
    if ans == 0:
        ans += MAX
    print(1+ans%MAX)

Submission status: Accepted

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)
col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

Submission status: Accepted

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)
col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k
        #print(col[c]+1)

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

Submission status: Accepted

Solution code:
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*(n-1)

for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b); eid[a].append(i) # to:nodeの繋がり、eid:edgeの色
    to[b].append(a); eid[b].append(i)

import queue

q = queue.Queue()
used = [0]*n
q.put(0)
used[0] = 1
while not q.empty():
    v = q.get()
    c = -1
    for i in range(len(to[v])):
        u = to[v][i]; ei = eid[v][i]
        if used[u]: c = ans[ei]
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]; ei = eid[v][i]
        if used[u]: continue
        if k == c: k += 1
        ans[ei] = k
        k += 1
        q.put(u)
        used[u] = 1

mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
"""dfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*(n-1)

def dfs(v, c=-1, p=-1): # v:これから見るnode、c:pとvを繋ぐedgeの色、p:親node
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]
        ei = eid[v][i]
        if u == p: continue # 親nodeは確認済みなので見ない
        if k == c: k += 1 # 親nodeとの間のedgeの色と同じではいけないのでインクリメントする
        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
    to[a].append(b); eid[a].append(i) # to:nodeの繋がり、eid:edgeの色
    to[b].append(a); eid[b].append(i)

dfs(0)

mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
"""dfs"""

n = int(input())
import sys
sys.setrecursionlimit(10**6)

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]
        ei = eid[v][i]
        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
    to[a].append(b); eid[a].append(i)
    to[b].append(a); eid[b].append(i)

dfs(0)
mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

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


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

    def dfs(v, p, p_col):
        col = 1
        for u, idx in tree[v - 1]:
            if u == p:
                continue
            if col == p_col:
                col += 1
            res[idx] = col
            col += 1
            dfs(u, v, res[idx])

    res = [0 for _ in range(n - 1)]
    dfs(1, -1, -1)
    print(max(res))
    print("\n".join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
def color_available(unavailable, K):
    idx = 0
    L = len(unavailable)
    unavailable = sorted(unavailable)
    for color in range(K):
        if idx < L and color == unavailable[idx]:
            idx += 1
        else:
            yield color

def bfs(graph, N, K, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        gen = color_available(colors[node].values(), K)
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                colors[node][n] = colors[n][node] = next(gen)
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
K = max(counts)
colors = bfs(graph, N, K, 0)
print(K)
for i, j in inputs:
    print(colors[i][j] + 1)

Submission status: Accepted

Solution code:
from collections import deque
def color_available(unavailable, K):
    idx = 0
    L = len(unavailable)
    unavailable = sorted(unavailable)
    for color in range(K):
        if idx < L and color == unavailable[idx]:
            idx += 1
        else:
            yield color

def bfs(graph, N, K, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        gen = color_available(colors[node].values(), K)
        color = 1
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                color = next(gen)
                colors[node][n] = color
                colors[n][node] = color
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
K = max(counts)
colors = bfs(graph, N, K, 0)
print(K)
for i, j in inputs:
    print(colors[i][j] + 1)

Submission status: Accepted

Solution code:
from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

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

K = Counter(edge_list).most_common()[0][1]

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

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()

    is_visited[cur_node] = True
    col_use = 0

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            if col_use == pre_col:
                col_use += 1

            color[(cur_node,next_node)] = col_use
            q.append([next_node, col_use])
            col_use += 1

print(K)

for i in range(N-1):
    print(color[tuple(edge[i])] + 1)

Submission status: Accepted

Solution code:
N = int(input())
query = [[] for _ in range(N)]
color = []
m = [0]*N
for n in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1) 
    query[b-1].append(a-1)
    color.append((min(a, b), max(a, b)))
    m[a-1] += 1
    m[b-1] += 1

print(max(m))
from collections import deque
queue = deque()
queue.appendleft(0)
checked = [-1]*N
checked[0] = 0
dic = {}
while queue:
    v = queue.pop()
    oya = checked[v]
    lis = query[v]
    cnt = 1
    for i in lis:
        if checked[i]!=-1:
            continue
        if cnt==oya:
            cnt += 1
        queue.appendleft(i)
        dic[(min(v+1, i+1), max(v+1, i+1))] = cnt
        checked[i] = cnt
        cnt += 1

for n in range(N-1):
    a, b = color[n]
    print(dic[(min(a, b), max(a, b))])

Submission status: Accepted

Solution code:
#グラフ構造DFSを使う
import sys
sys.setrecursionlimit(500000)
N = int(input())
ans = [-1] * (N-1)
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))

def bfs(v, c, p):
    n_c = 1
    for i in range(len(g[v])):
        to = g[v][i][0]
        ID = g[v][i][1]
        if to == p:
            continue
        if n_c == c:
            n_c += 1
        ans[ID] = n_c
        bfs(to, n_c, v)
        n_c += 1

bfs(0, 0, -1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N = int(input())

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

    dq = deque()
    dq.append([0, -1])
    color = [-1] * (N - 1)
    while dq:
        v, skip = dq.popleft()
        color_to_use = 1
        for u, i in g[v]:
            if ~color[i]: continue
            if color_to_use == skip:
                color_to_use += 1
            color[i] = color_to_use
            dq.append((u, color_to_use))
            color_to_use += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    counter = defaultdict(int)
    edges = []
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        edges.append(b)
        counter[a] += 1
        counter[b] += 1
    
    ans = [0] * N
    
    def bfs(parent, p_color):
        c_color = 1
        for child in graph[parent]:
            if c_color == p_color:
                c_color += 1
            ans[child] = c_color
            bfs(child, c_color)
            c_color += 1
    
    bfs(0, 0)
    print(max(counter.values()))
    for edge in edges:
        print(ans[edge])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())

#道を双方向に記録する。
g = [[] for _ in range(N)]

for i in range(N-1): #木の辺の数はN-1
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1 #ここで引いて頂点を0スタートにしないとオーバーフロー
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import collections
N = int(input())
G = [set() for i in range(N)]
ab = [tuple(map(int, input().split())) for i in range(N-1)]

d = dict()
i = 0
for a, b in ab:
    a -= 1
    b -= 1
    d[(a, b)] = i
    d[(b, a)] = i
    i += 1
    G[a].add(b)
    G[b].add(a)


q = collections.deque()
r = set()
r.add(0)
q.append((0, 0))
ans = [0]*(N-1)

while(q):
    x, s = q.popleft()
    i = 1
    for y in G[x]:
        if y in r:
            continue
        else:
            r.add(y)
            if i == s:
                i += 1
            ans[d[(x, y)]] = i
            q.append((y, i))
            i += 1
print(max(ans))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    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))
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    colors=[0]*n
    ans=[0]*(n-1)
    while queue:
        node=queue.popleft()
        c=1
        for xnode,edge in graph[node]:
            if visited[xnode]:continue
            if colors[node]==c:c+=1
            ans[edge]=c
            colors[xnode]=c
            visited[xnode]=True
            queue.append(xnode)
            c+=1
    print(max(ans))
    for a in ans:
        print(a)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        par = [-1]*N
        while todo:
            u = todo.pop()
            k = 0
            c = edge[(par[u], u)] if u != 0 else 0
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                par[v] = u
                k += 1
                if k == c:
                    k += 1
                    if max_g < k:
                        k = 1
                if u < v:
                    edge[(u, v)] = k
                else:
                    edge[(v, u)] = k

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n = II()
    e = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = MI1()
        e[a].append((b, i))
        e[b].append((a, i))
    # print(e)

    ans = [0] * (n-1)
    def dfs(v, v_pre=-1, c_pre=-1):
        c = 1
        for (nv, id) in e[v]:
            if nv == v_pre: continue
            if c_pre == c: c += 1
            # v to nv color = c
            ans[id] = c
            dfs(nv, v, c)
            c += 1

    dfs(0)
    print(max(ans))
    printlist(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append((b, 1+i))

color = [0] * N

def dfs(v, c, idx):
    color[idx] = c
    now = 0
    for nv, i in edge[v]:
        now += 1
        if now == c:
            now += 1
        dfs(nv, now, i)

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

Submission status: Accepted

Solution code:
from collections import deque
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))

queue = deque([0])
seen = [False]*n
seen[0] = True
colors = [None]*n
ans = [None]*(n-1)
while len(queue)>0:
    node = queue.popleft()
    c = 1
    for c_node, edge in graph[node]:
        if seen[c_node]:
            continue
        if colors[node]==c:
            c += 1
        ans[edge] = c
        colors[c_node] = c
        seen[c_node] = True
        queue.append(c_node)
        c += 1
print(max(ans))
for i in ans:
    print(i)