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: Time Limit Exceeded

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

    k=max(len(E[v]) for v in range(n))

    # DFSで辺に色付け
    Q=[0]
    while(Q):
        v=Q.pop()
        if(v==0):
            col=list(range(1,k+1))
        else:
            p=min(E[v])
            c=edges[(p,v)][1]
            col=set(range(1,k+1))
            col.remove(c)
            col=list(col)
        for nv in E[v]:
            if(v==0):
                c=col.pop()
                edges[(v,nv)][1]=c
                Q.append(nv)
            else:
                if(nv==p): continue
                c=col.pop()
                edges[(v,nv)][1]=c
                Q.append(nv)

    res=list(edges.values())
    res.sort()
    print(k)
    for i,c in res:
        print(c)

resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            queue.append(s[(s.index(q)+1)%2])

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]

memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].append(b)
    E[b].append(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

K = max(len(e) for e in E)

A = [0] * (N - 1)

cand = {i for i in range(1, K + 1)}

visited = [False] * (N + 1)

Q = deque([(-1, 1)])
visited[1] = True
while Q:
    c, v = Q.popleft()
    C = cand - {c}
    for u in E[v]:
        if visited[u]:
            continue
        visited[u] = True
        c = C.pop()
        Q.append((c, u))
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            queue.append(s[(s.index(q)+1)%2])

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#「辺」彩色
#最大次数で可
#構成はset()使って色管理
#Adいらない
n = int(input())
#Ad = [set() for i in range(n)]
Deg = [0]*n
E = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    #Ad[ai].add(bi)
    #Ad[bi].add(ai)
    Deg[ai]+=1
    Deg[bi]+=1
    E.append((ai,bi))

cl = max(Deg)
Deg2 = [set(range(cl)) for i in range(n)]
print(cl)
for ai,bi in E:
    c = 0
    while c  not in Deg2[ai] or c not in Deg2[bi]:
        c+=1
    print(c+1)
    Deg2[ai].remove(c)
    Deg2[bi].remove(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
kind=[0]*n
aa=[]
bb=[]
for _ in range(n-1):
	a,b=map(int,input().split())
	aa.append(a)
	bb.append(b)
	kind[a-1]+=1
	kind[b-1]+=1
print(max(kind))
p=[[set()]for _ in range(n)]
for i in range(n-1):
	flag=False
	for j in range(1,max(kind)+1):
		if flag==True:
			break
		if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
			p[aa[i]-1][0].add(j)
			p[bb[i]-1][0].add(j)
			flag=True
			print(j)

Submission status: Time Limit Exceeded

Solution code:
#「辺」彩色
#最大次数で可
#構成はset()使って色管理
n = int(input())
Ad = [set() for i in range(n)]
Deg = [0]*n
E = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].add(bi)
    Ad[bi].add(ai)
    Deg[ai]+=1
    Deg[bi]+=1
    E.append((ai,bi))

cl = max(Deg)
Deg2 = [set(range(cl)) for i in range(n)]
print(cl)
for ai,bi in E:
    c = 0
    while c  not in Deg2[ai] or c not in Deg2[bi]:
        c+=1
    print(c+1)
    Deg2[ai].remove(c)
    Deg2[bi].remove(c)

Submission status: Time Limit Exceeded

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

for a, b in ab:
    c = [0] * n
    for f in e[a]:
        c[d[a][f]] = 1
    for f in e[b]:
        c[d[b][f]] = 1
    for i, x in enumerate(c):
        if x == 0:
            print(i)
            d[a][b] = i
            d[b][a] = i
            break

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
routings = [[] for _ in range(N+1)]
colors = [0 for _ in range(N+1)]
vertexes = [tuple(map(int, input().split())) for _ in range(N-1)]

for a, b in vertexes:
  routings[a].append(b)
  routings[b].append(a)
  
edges = deque([1])
colors[1] = 0
answer = 0
while len(edges) > 0:
  edge = edges.pop()
  color = colors[edge]
  nc = 1
  answer = max(answer, len(routings[edge]))
  for ne in routings[edge]:
    if colors[ne] == 0 and ne != 1:
      if nc == color:
        nc += 1
      colors[ne] = nc
      edges.append(ne)
      nc += 1
print(answer)
for a, b in vertexes:
  print(colors[b])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def dfs(u, p, c, color, tree):
    color[(u, p)] = c
    color[(p, u)] = c

    now = 0
    for v in tree[u]:
        if v == p:
            continue
        if now == c:
            now += 1

        dfs(v, u, now, color, tree)
        now += 1


def solve():
    N = int(input())

    tree = [[] for _ in range(N)]
    edges = []
    for _ in range(N - 1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        tree[A].append(B)
        tree[B].append(A)
        edges.append((A, B))

    color = dict()
    dfs(0, -1, -1, color, tree)

    print(max(color.values()) + 1)
    for e in edges:
        print(color[e] + 1)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    edge_colors = dict()
    node_colors = [0] * len(tree)
    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        parent_color = node_colors[q]

        cnt = 1
        for v in tree[q]:
            if not seen[v]:
                if cnt == parent_color:
                    cnt += 1

                edge_colors[(q, v)] = cnt
                node_colors[v] = cnt
                queue.append(v)
                cnt += 1



    """
    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)
    """

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


setrecursionlimit(10**6)



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



hands = [0 for _ in range(n+1)]
for a, b in t:
    hands[a] += 1
    hands[b] += 1

number_of_colors = max(*hands)

def next_color(i):
    return i+1 if i < number_of_colors else 1



class edge():
    def __init__(self, en):
        self.ends = en
        self.color = 0

    def set_color(self, co):
        self.color = co

class nord():
    def __init__(self, tr):
        self.parent = tr
        self.edges = []

    def add(self, ed):
        self.edges.append(ed)

    def set_color(self, previous_color):
        co = next_color(previous_color)
        for ed in self.edges:
            if ed.color == 0:
                ed.set_color(co)
                for i in ed.ends:
                    no = self.parent.nords[i-1]
                    if self is not no:
                        no.set_color(co)
                co = next_color(co)

class tree():
    def __init__(self):
        self.nords = []

    def add_nord(self, no):
        self.nords.append(no)

    def add_edge(self, ed):
        for i in ed.ends:
            self.nords[i-1].add(ed)

    def set_color(self):
        self.nords[0].set_color(0)


tr = tree()
for _ in range(n):
    no = nord(tr)
    tr.add_nord(no)

e_tree = []
for en in t:
    ed = edge(en)
    e_tree.append(ed)
    tr.add_edge(ed)

tr.set_color()

print(number_of_colors)
for e in e_tree:
    print(e.color)

Submission status: Accepted

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

col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [0]

while v:
  d = v.pop(0)
  k = 1
  for i in a[d]:
    if visited[i] == False:
      if col[d] == k:
        k += 1
      col[i] = k
      visited[i] = True
      v.append(i)
      k += 1

print (max(col))
for i in e:
  print (col[i])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].append(c)
  e.append(c)
col = [0 for i in range(n)]
v = deque([0])

while v:
  d = v.popleft()
  k = 1
  for i in a[d]:
    if col[d] == k:
      k += 1
    col[i] = k
    v.append(i)
    k += 1
print (max(col))
for i in e:
  print(col[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    global visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    global color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print("\n".join(map(str, color_list)))

Submission status: Accepted

Solution code:
N=int(input())
l=[[] for i in range(N)]
color=[0]*N
mem=[]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   mem.append(b)
from collections import deque
que=deque([0])
while que:
   node=que.popleft()
   c=1
   for i in l[node]:
      if color[node]==c:
         c+=1
      color[i]=c
      c+=1
      que.append(i)
print(max(color))
for i in mem:
   print(color[i])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
e=[]
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
    e.append(str(x-1)+" "+str(y-1))
par=[0]*n #自分の親と何番でつながっているか
visited=[0]*n
visited[0]=1
que=deque([0])
ans=dict()
K=0
while que:
    now=que.popleft()
    color=1
    for x in edge[now]:
        if visited[x]:
            continue
        visited[x]=1
        que.append(x)
        if color==par[now]:
            color+=1
        par[x]=color
        ans[str(min(x,now))+" "+str(max(x,now))]=color
        color+=1
print(max(ans.values()))
for i in e:
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    AB=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        AB.append(str(a)+" "+str(b))

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    ans=dict()
    #bfs
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                ans[str(min(now,x))+" "+str(max(now,x))]=color
                color+=1
        color-=1
        K=max(K,color)

    #出力
    print(K)
    for key in AB:
        print(ans[key])
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    num = 1
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    #print(a ^ b)
if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N=intput()
node=[list() for _ in range(N+1)]
done=[False]*(N+1)
color=[0]*(N+1)
ans=[0]*(N-1)
S=dict()
for i in range(N-1):
    u,v=mint()
    node[u].append(v)
    node[v].append(u)
    S[(u,v)]=i
    S[(v,u)]=i
q=deque([1])
done[1]=True
while q:
    u=q.popleft()
    c=1
    for v in node[u]:
        if not done[v]:
            if c==color[u]:
                c+=1
            color[v]=c
            ans[S[(u,v)]]=c
            done[v]=True
            q.append(v)
            c+=1
print(max(ans))
lprint(ans)

Submission status: Accepted

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

n = int(input())
t = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int,input().split())
    t[a].append((b,i))
    t[b].append((a,i))
num = max([len(tmp) for tmp in t])
print(num)

ans = [-1]*(n-1)

def dfs(n, before, bcol):
    col = 1
    for i, j in t[n]:
        if i == before:
            continue
        if col == bcol:
            col += 1
        ans[j] = col
        dfs(i, n, col)
        col += 1

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

Submission status: Accepted

Solution code:
from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
Q = [{} for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    Q[a-1][b-1] = i

K = max(list(map(len, G)))
print(K)
ans = [0] * (N-1)
q = Queue()
q.put(0)
while not q.empty():
    v = q.get()
    c = set()
    for u in G[v]:
        if u < v:
            c.add(ans[Q[u][v]])
    
    i = 1
    for u in G[v]:
        if u > v:
            while i in c: i += 1
            ans[Q[v][u]] = i
            i += 1
            q.put(u)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

root,res=0,0
for i in range(1,N+1):
    tmp=len(G[i])
    if tmp>res:
        res=tmp
        root=i
        
q=deque()
q.append((root,0))
color=[0]*N
D=[N+10]*(N+1)
D[root]=0
while q:
    p,c=q.popleft()
    nc=1
    while G[p]:
        np,ni=G[p].pop()
        if D[np]>D[p]:
            D[np]=D[p]+1
            if nc==c:
                nc+=1
            color[ni]=nc
            q.append((np,nc))
            nc+=1
print(res,*color[1:],sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-09-15 21:36:31 +0900
# LastModified: 2020-09-15 22:19:28 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


class BFS():
    def __init__(self, path, N):
        self.N = N
        self.color_path = [-1]*self.N
        self.path = path
        self.init = 1
        self.Q = deque([[0, self.init]])

    def forward(self):
        while self.Q:
            prev_path, u = self.Q.popleft()
            p_cnt = 1
            for cp, v in self.path[u]:
                if self.color_path[cp] == -1:
                    if prev_path == p_cnt:
                        p_cnt += 1
                    self.Q.append([p_cnt, v])
                    self.color_path[cp] = p_cnt
                    p_cnt += 1
#            print(self.color_path)

    def print_ans(self):
        self.color_path.pop(0)
        print(max(self.color_path))
        for cp in self.color_path:
            print(cp)


def main():
    N = int(input())
    path = [[] for _ in range(N+1)]
    for i in range(1, N):
        a, b = map(int, input().split())
        path[a].append([i, b])
        path[b].append([i, a])
    bfs = BFS(path, N)
    bfs.forward()
    bfs.print_ans()



if __name__ == "__main__":
    main()

Submission status: Accepted

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

q = collections.deque()
ans = [-1]*(N-1)
q.append([0,-1])
while len(q) != 0:
    tmp = 1
    v, v2 = q.popleft()
    for w, i in graph[v]:
        if ans[i] != -1:
            continue
        if ans[v2] == tmp:
            tmp += 1
        ans[i] = tmp
        tmp += 1
        q.append([w,i])

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

Submission status: Accepted

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

N = int(readline())

G = [[] for i in range(N)]
from collections import defaultdict
E = defaultdict(int)

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

from collections import deque
q = deque([])
ans = [None] * (N - 1)

q.append([0, -1, 0])
maxcol = 0
while q:
  v, parent, color = q.popleft()
  if color > maxcol:
    maxcol = color
  if (v, parent) in E:
    ans[E[(v, parent)]] = color
  elif (parent, v) in E:
    ans[E[(parent, v)]] = color
  next_col = 0
  for child in G[v]:
    if child == parent:
      continue
    next_col += 1
    if next_col == color:
      next_col += 1
    q.append([child, v, next_col])
    
print(maxcol)
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for n in range(N)]
vc = N*[0]
ec = (N-1)*[0]
h = 1

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

for v,g in enumerate(G):
  t = 1
  for b,i in g:
    if vc[v]==t:
      t+=1
    vc[b] = t
    ec[i] = t
    h = max(h,t)
    t+=1

print(h)
for n in range(N-1):
  print(ec[n])

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	vertex = [[] for i in range(N)]

	ini_v = 0
	for i in range(N - 1):
		a, b = [int(x) for x in input().split(" ")]
		if i == 0:
			ini_v = a - 1
		vertex[a - 1].append({"v": b - 1, "e": i})
		vertex[b - 1].append({"v": a - 1, "e": i})

	checked_v = [0] * N
	checked_e = [0] * (N - 1)
	to_visit = [ini_v]
	checked_v[ini_v] = 1
	color_e = [-1] * (N - 1)

	while len(to_visit):
		visiting = to_visit.pop(0)
		vs = vertex[visiting]
		used_cs = []
		cless_e = []
		for d in vs:
			if checked_v[d["v"]] == 0:
				checked_v[d["v"]] = 1
				to_visit.append(d["v"])
			if color_e[d["e"]] == -1:
				cless_e.append(d["e"])
			else:
				used_cs.append(color_e[d["e"]])
		s = 0
		for j in range(len(vs)):
			if s >= len(cless_e) or len(cless_e) == 0:
				break
			elif j in used_cs:
				continue
			else:
				color_e[cless_e[s]] = j
				s += 1

	print(max(color_e) + 1)
	for i in range(len(color_e)):
		print(color_e[i] + 1)

main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()

dist = [[] for i in range(N)]
edges = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
    edges[(a - 1, b - 1)] = i
    edges[(b - 1, a - 1)] = i

color = [-1] * N
color[0] = 0
ans = [0] * (N - 1)
pos = deque([0])

while pos:
    u = pos.popleft()
    j = 1
    for i in dist[u]:
        if color[i] != -1:
            continue
        if j == color[u]:
            j += 1
        color[i] = j
        ans[edges[(i, u)]] = j
        pos.append(i)
        j += 1

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

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n = int(input())
    e = [[i] + list(map(int,stdin.readline().split())) for i in range(n-1)]
    return n,e

def main(n,e):
    tree = [[] for i in range(n)]
    ans = [0 for i in range(n-1)]
    for i in e:
        tree[i[1]-1].append([i[2]-1,i[0]])
    tree[0].append(0)
    k = 1
    q = [0]
    while q:
        n = 0
        idx = q.pop(0)
        for i in range(len(tree[idx])-1):
            n += 1
            if n==tree[idx][-1]:
                n += 1
            ans[tree[idx][i][-1]] = n
            tree[tree[idx][i][0]].append(n)
            q.append(tree[idx][i][0])
        k = max(k,n)

    print(k)
    for i in ans:
        print(i)
            
            
if __name__=="__main__":
    n,e = getval()
    main(n,e)

Submission status: Accepted

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


N = int(input())
to = [[] for _ in range(N)]
order = []

for _ in range(N - 1):
    a, b = list(map(lambda x:int(x) - 1, input().split()))
    to[a].append(b)
    to[b].append(a)
    order.append(b)


def solve():
    dist = [-1] * N
    # 頂点iに向かう辺をiとする
    color = [0] * N
    dist[0] = 0
    color[0] = 0
    que = deque([0])

    while que:
        v = que.popleft()
        used_color = [color[v]]
        next_color = 1
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                while next_color in used_color:
                    next_color += 1
                color[nv] = next_color
                used_color.append(next_color)
                que.append(nv)

    print(len(set(color[1:])))
    for i in range(N - 1):
        print(color[order[i]])


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N =int(input())

edge = [[] for i in range(N)]
adj = [[] for i in range(N)]

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

K = 0
for i in range(N):
    K = max(K, len(adj[i]))
print(K)

from collections import deque
color = [-1] * (N - 1)
qu = deque([0])
done = [False] * N
done[0] = True
vc = [-1] * N
while(len(qu) > 0):
    v = qu.popleft()
    for nv, e in adj[v]:
        if not done[nv]:
            vc[v] = (vc[v] + 1) % K
            color[e] = vc[v]
            qu.append(nv)
            vc[nv] = vc[v]
            done[nv] = True

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