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:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

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

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

ma = 0
ma_e = 0
for i, arr in enumerate(mp):
    if len(arr) > ma:
        ma = len(arr)
        ma_e = i

CLS = [0]*(N-1)
VISITED = [0]*(N+1)
Q=deque([(ma_e, 0)])
VISITED[ma_e] = 1

while Q:
    v, c = Q.popleft()
    cnt = 0
    for next_e, i in mp[v]:
        if VISITED[next_e]: continue
        color = ((c + cnt) % ma) + 1
        CLS[i] = color
        # print("{} color{}".format(i, color))

        Q.append((next_e, color))
        VISITED[next_e] = 1
        cnt += 1

print(ma)
for i in CLS: print(i)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    col = 1 
    for i in g[prvi]:
      if i in used:continue
      if col == prvcol: col += 1
      cols[eds[str(min(prvi,i))+'-'+str(max(prvi,i))]] = col
      q.append([i,col])
      used.add(i)
      col += 1

N = int(input())
g = {i:[] for i in range(N)}
eds = {}
for i in range(N-1):
  a,b = map(int,input().split())
  eds[str(a-1)+'-'+str(b-1)] = i
  g[a-1].append(b-1)
  g[b-1].append(a-1)

used = set([])
cols = [-1 for _ in range(N-1)]  
bfs(0)
print(max(cols))
[print(col) for col in cols]

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a].append((b,i))
  edges[b].append((a,i))
ans=[0]*(n-1)
q=deque()
next_v=edges[0]
for c,(u,i) in enumerate(next_v):
  q.append((u,i,c+1))
  ans[i]=c+1
while q:
  up,_,cp=q.popleft()
  next_v=edges[up]
  cnt=1
  for u,i in next_v:
    if ans[i]>0:
      continue
    if cnt==cp:
      cnt+=1
    ans[i]=cnt
    q.append((u,i,cnt))
    cnt+=1
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[min(v,P[v]),max(v,P[v])]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[min(u,v),max(u,v)]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)

Submission status: Accepted

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

N=int(input())
ab=[list(map(int, input().split())) for i in range(N-1)]
link=[[] for i in range(N+1)]
for i in range(0, N-1):
  link[ab[i][0]].append([ab[i][1], i])
  link[ab[i][1]].append([ab[i][0], i])
  
out=[0]*(N-1)
def f(num, prenum=0, prec=0):
  postc=1
  for postnum, linknum in link[num]:
    if postnum==prenum:
      continue
    if postc==prec:
      postc+=1
      
    out[linknum]=postc
    f(postnum, num, postc)
    postc+=1
    
f(1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
def colorize(current_node, adjacents, colors, from_color, k):
    
    # そのノードから繋がるエッジを辿っていく
    count = 0
    for edge, node in adjacents[current_node]:
 
        # 既に塗られていたら無視
        if colors[edge]!=None:
            continue
        
        count += 1
        colors[edge] = (from_color+count)%k
        colorize(node, adjacents, colors, colors[edge], k)
     
N = int(input())
adjacents = {i+1:[] for i in range(N)}
 
for i in range(N-1):
    a,b = [int(e) for e in input().split(" ")]
    
    adjacents[a].append( [i+1,b] )
    adjacents[b].append( [i+1,a] )
 
# 一番隣接エッジ数が多いノード
most_edge =sorted(adjacents, key=lambda d:len(adjacents[d]))[-1]
k = len(adjacents[most_edge])
 
colors = {i+1:None for i in range(N-1)}
colorize(1, adjacents, colors, -1, k)
 
print(k)
for color in colors.values():
    print(color+1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    ab = [LI() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)
    t = sorted([(-len(e[i]), i) for i in range(1,n+1)])
    d = collections.defaultdict(set)
    r = {}
    for _, a in t:
        i = 1
        for b in e[a]:
            if (a,b) in r:
                continue
            while i in d[a] or i in d[b]:
                i += 1
            d[a].add(i)
            d[b].add(i)
            r[(a,b)] = r[(b,a)] = i
            i += 1
    rr = []
    for a,b in ab:
        rr.append(r[(a,b)])

    return JA([max(rr)] + rr, "\n")


print(main())

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**5+10)

n = int(input())
visited = set()
g = {}
idx = {}
color = {}
for i in range(n-1):
    a,b = map(int, input().split())
    idx[i] = (a,b)
    if a not in g:
        g[a] = []
    g[a].append(b)
    if b not in g:
        g[b] = []
    g[b].append(a)

def dfs(v,c):
    cc = 0
    for u in g[v]:
        if u in visited:
            continue
        visited.add(u)

        cc += 1
        while cc==c:
            cc += 1
        a,b = min(u,v),max(u,v)
        color[(a,b)] = cc
        
        dfs(u,cc)
visited.add(1)
dfs(1,0)

mc = 0
for c in color.values():
    mc = max(mc, c)
print(mc)
for i in range(n-1):
    print(color[idx[i]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())

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

ans = [None for _ in range(n-1)]
used = [False for _ in range(n)]
k = 0


def dfs(node, col=-1, parent=-1):
    global k
    if k < len(tree[node]):
        k = len(tree[node])

    c = 1
    for neighbor, i in tree[node]:
        if neighbor == parent:
            continue
        if c == col:
            c += 1
        ans[i] = c
        c += 1
        dfs(neighbor, ans[i], node)


dfs(0)

print(k)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    # G = [[0] * (n-1) for i in range(2)]
    cnt = [0] * n
    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))
        cnt[a-1] += 1
        cnt[b-1] += 1


    # for i in range(n-1):
    #     a,b = map(int, input().split())
    #     G[0][i] = a-1
    #     G[1][i] = b-1
    #     cnt[a-1] += 1
    #     cnt[b-1] += 1
    num = 0
    # print(G)
    print(max(cnt))

    tmp_clr = [0] * (n-1)
    tmp_edge = [0] * n

    # print(G)
    for frm, child in enumerate(G):
        clr = 1
        for j, to  in enumerate(child):

            if tmp_edge[frm] == clr :
                clr += 1
            tmp_clr[to[1]] = clr
            # tmp_edge[frm] = clr
            tmp_edge[to[0]] = clr
            clr+=1
    # print(tmp_edge)
    # print(tmp_clr)
    print('\n'.join(map(str, tmp_clr)))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
to_edges = [e[1] for e in edges] 

tree = [[] for _ in range(n + 1)]
for x, y in edges:
    tree[x].append(y)

queue = deque([1])
colors = [0] * (n + 1)
while queue:
    x = queue.popleft()
    c = 0
    for y in tree[x]:
        c += 1 + (c + 1 == colors[x])
        colors[y] = c
        queue.append(y)

print(max(colors))
for e in to_edges:
    print(colors[e])

Submission status: Accepted

Solution code:
import sys
from collections import deque
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
B = [e[1] for e in edges] 

E = [[] for _ in range(n + 1)]
for a, b in edges:
    E[a].append(b)

Q = deque([1])
C = [0] * (n + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Submission status: Accepted

Solution code:
from collections import deque
 
N, *AB = map(int, open(0).read().split())
B = AB[1::2]
 
E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
#https://atcoder.jp/contests/abc146/tasks/abc146_d
#D - Coloring Edges on Tree
"""
for each edge, keep track of parent, and each edges color
while we are BFSing, we can just iterate from 1, and skip if the next one is same as parents
"""

# reads a single line
N = gi()
ecs = {}
nbls = [[] for i in range(N + 5)]  #[] * N won't work
p = [0] * (N + 5)
in_l = []

max_d = 0

for i in range(1, N):
    a = gi()
    b = gi()
    nbls[a].append(b)
    nbls[b].append(a)
    max_d = max(max_d, len(nbls[a]), len(nbls[b]))
    in_l.append((min(a, b), max(a, b)))
p[1] = 0  #sentinel node to keep code clean
ecs[(0, 1)] = -1

c_i = 0
q = deque()
q.append(1)

while len(q):
    v = q.pop()
    #by the time we reach the node, the parent edge of this node has been colored
    parent_ci = ecs[(min(v, p[v]), max(v, p[v]))]
    for u in nbls[v]:
        if u == p[v]:
            continue
        q.append(u)
        p[u] = v
        if parent_ci == c_i:
            c_i += 1
            c_i %= max_d
        ecs[(min(u, v), max(u, v))] = c_i
        c_i += 1
        c_i %= max_d

print(max_d)
for e in in_l:
    print(ecs[e] + 1)

Submission status: Accepted

Solution code:

import math
import fractions

def makeDivisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def makeNeighbor(es,n):
    nlist = [[] for i in range(n+1)]
    for i in es:
        nlist[i[0]].append(i[1])
        nlist[i[1]].append(i[0])
    return nlist
    
#a = list(map(int, input().split()))
# --------------------------------------------

n = int(input())
es = []
for i in range(n-1):
    es.append(list(map(int, input().split())))
nb = [[] for i in range(n+1)]
ct = 0

for i in es:
    nb[i[0]].append([i[1],ct])
    nb[i[1]].append([i[0],ct])
    ct+=1
#print(nb)
ans = [-1 for i in range(n-1)]
mx = 0
for i in nb:
    if mx<len(i) : mx = len(i)

que = [[1,0]]
end = [0 for i in range(n+1)]
done = 0
end[1]=1
while(len(que) > done):
    nowpos = que[done][0]
    nowcol = que[done][1]
    end[nowpos]=1
    for k in nb[nowpos]:
        if(end[k[0]]==0):
            nowcol += 1
            nowcol %= mx
            que.append([k[0],nowcol])
            ans[k[1]] = nowcol+1
    done+=1
print(mx)
for i in range(n-1): print(ans[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
que = deque([root])
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while que:
    x = que.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        que.append(y)
print(max([len(i) for i in graph]))
color = [0 for i in range(n+1)]
cnt = [0 for i in range(n+1)]
ng = [0 for i in range(n+1)]
for x in order:
    if x == 1:
        continue
    px = parent[x]
    color[x] = cnt[px]+1
    if color[x] == ng[px]:
        color[x] += 1
    cnt[px] = color[x]
    ng[x] = color[x]
for a,b in ab:
    if parent[a] == b:
        p = b
        c = a
    else:
        p = a
        c = b
    print(color[c])

Submission status: Accepted

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

C = [0] * (N-1)
stack=[0]
parent_e=[0]*N
max_c=0
while stack:
    n=stack.pop()
    c=1
    for to,i in E[n]:
        if n!=0 and parent_e[n]==i:
            continue
        c+=1 if n!=0 and C[parent_e[n]]==c else 0
        C[i]=c
        max_c=max(max_c,c)
        c+=1
        stack.append(to)
        parent_e[to]=i

print(max_c)
print('\n'.join(map(str,C)))

Submission status: Accepted

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

C = [0] * (N-1)
stack=[0]
max_c=0
while stack:
    n=stack.pop()
    u=set()
    for to,i in E[n]:
        if C[i]!=0:
            u.add(C[i])
    c=1
    for to,i in E[n]:
        if C[i]!=0:
            continue
        while c in u:
            c+=1
        C[i]=c
        max_c=max(max_c,c)
        c+=1
        stack.append(to)

print(max_c)
print('\n'.join(map(str,C)))

Submission status: Accepted

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

    # 辺のindexを持っておく
    T[a].append([b, i])
    T[b].append([a, i])


stack = [[0, 0]]  # [次の頂点番号, 親に続く辺の色]
visited = [0] * N
colors = [0] * (N - 1)
while stack:
    n, parent_color = stack.pop()
    visited[n] = 1
    color = 1

    for to, i in T[n]:
        if visited[to]:
            continue

        if color == parent_color:
            color += 1

        colors[i] = color
        stack.append([to, color])

        color += 1


print(len(set(colors)))
print(*colors, sep='\n')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    G = [[] for _ in range(N)]
    edges = []
    edge2color = {}
    for _ in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
        edges.append((a, b))
    K = -1
    for adj_v in G:
        K = max(K, len(adj_v))
    visited = [0] * N
    def colorGraph(v, parColor=-1):
        children = G[v]
        colorNum = 1
        visited[v] = 1
        for child_v in children:
            if visited[child_v]:
                continue
            if colorNum == parColor:
                colorNum += 1
            edge2color[(v, child_v)] = colorNum
            edge2color[(child_v, v)] = colorNum
            colorGraph(child_v, colorNum)
            colorNum += 1
    # import pdb
    # pdb.set_trace()
    colorGraph(0)
    print(K)
    for edge in edges:
        key = (edge[0], edge[1])
        print(edge2color[key])

main()

Submission status: Accepted

Solution code:

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

v_color = [0] * N
e_color = [0] * (N-1)
K = 1
for a, children in enumerate(G):
    c = 1
    for b, i in children:
        if c == v_color[a]:
            c += 1
        v_color[b] = c
        e_color[i] = c
        K = max(K, c)
        c += 1

print(K)
print('\n'.join(map(str, e_color)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
A=[]
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    A.append((a,b))

P=[-1 for i in range(N+1)]
P[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(N):
    if len(Q)==i:
        break
    P[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if P[j]==-1:
            Q.append([j,Q[i][0]])
#print(P)
#print(Q)
D={}
D[(0,1)]=0
cnt=1
p=0
for i in range(N-1):
    if p!=Q[i][1]:
        p=Q[i][1]
        cnt=1
        for j in range(cnt,10**6):
            if D[(min(Q[i][1],P[Q[i][1]]),max(Q[i][1],P[Q[i][1]]))] != j:
                D[(min(Q[i]),max(Q[i]))] = j
                cnt = j+1
                break
    else:
        for j in range(cnt,10**6):
            if D[(min(Q[i][1],P[Q[i][1]]),max(Q[i][1],P[Q[i][1]]))] != j:
                D[(min(Q[i]),max(Q[i]))] = j
                cnt = j+1
                break
print(max(D.values()))
for i in range(N-1):
    print(D[A[i][0],A[i][1]])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from collections import defaultdict
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))


def solve(N: int, a: "List[int]", b: "List[int]"):

    g = Graph(N)
    for i, (aa, bb) in enumerate(zip(a, b)):
        g.add_edge(aa-1, bb-1, i)

    visited = [False]*N
    edge_color = [-1]*(N-1)

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

    while len(q) > 0:
        node, color = q.popleft()
        penki = 1
        if color == penki:
            penki += 1

        for to_, weight in g.E[node]:
            if edge_color[weight] != -1:
                continue
            edge_color[weight] = penki
            q.append((to_, penki))
            penki += 1
            if color == penki:
                penki += 1

    print(max([len(g.E[k]) for k in g.E]))
    print(*edge_color, sep="\n")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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())
G = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    d[(a,b)] = d[(b,a)] = i

k = 0
ans = [None]*(n-1)

stack = [(0,-1)] #node, par

while stack:
    now,pre = stack.pop()
    color = 1
    for nex in G[now]:
        if nex == pre:continue
        stack.append((nex,now))
        if pre != -1:
            if color == ans[d[(now,pre)]]:
                color += 1
        ans[d[(now,nex)]] = color
        k = max(k,color)
        color += 1

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

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
G = [[] for _ in range(N)]
E = {}

for i in range(N-1):
  a, b = ints()
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)
  E[(a, b)] = i

C = [0]*(N-1)
S = [(0, None, None)]
max_color = 0
while len(S)>0:
  node, from_node, from_color = S.pop()

  c = -1
  for n in G[node]:
    if n==from_node:
      continue
    c += 1
    if c==from_color:
      c += 1

    max_color = max(max_color, c)
    C[E[(min(n, node), max(n, node))]] = c
    S.append((n, node, c))

print(max_color+1)
for i in C:
  print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for u, i in next_v:
        # すでに彩色されている辺はダメ
        if ans[i] > 0:
            continue
        # 親と色がかぶったら+1
        if cnt == c_p:
            cnt += 1
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for j, (u, i) in enumerate(next_v):
        # すでに彩色されている辺はダメ
        if ans[i] > 0:
            continue
        # 親と色がかぶったら+1
        if cnt == c_p:
            cnt += 1
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

ans = [0] * (N-1)

def dfs(v, p=-1, c=-1): #親p(はじめはいないので-1), 子がv, 親の色も渡す必要あり
    # 子が次の子孫をグラフから探す
    global ans
    next_v = edges[v]
    cnt = 1 # num of colors
    for u,i in next_v:
        # 子孫の中には親もいて、それは除外
        if u == p: continue
        # 子供に対しては自分が親となり、同様のことをする
        if cnt == c:
            cnt += 1
        ans[i] = cnt      
        cnt += 1
        dfs(u, v, ans[i])


dfs(0)
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

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

n = int(input())
es = [[] for _ in range(n)]

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

ans = [0] * (n-1) 

def coloring(vi,prev_color):
  color = 1    
  for to,i in es[vi] :
    if color == prev_color:
      color += 1        
    ans[i] = color     
    coloring(to,color)
    color += 1
    
coloring(0,0)

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

Submission status: Accepted

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)
from collections import deque


#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        copyedge=sorted(self.edge)
        checkedge=deque()
        for edge in copyedge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
                
        while checkedge:
            edge=checkedge.popleft()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)