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 queue
n = int(input())

tree = [[] for i in range(n)]
edges = []

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


ncol = max([len(tree[i]) for i in range(n)])
usedcol = [-1 for i in range(n)]
colour = [dict() for i in range(n)]


visited = [False for i in range(n)]
def bfs(v):
    q = queue.Queue(0)
    q.put(v)
    while not q.empty():
        v = q.get()
        visited[v] = True
        u = usedcol[v]
        col = 0
        # colour each edge and add neighbours
        for i in range(len(tree[v])):
            nv = tree[v][i]
            if not visited[nv]:
                col += 1; col += 1 if col==u else 0
                usedcol[nv] = col
                colour[v][nv] = col; colour[nv][v] = col
                q.put(nv)

bfs(1)
print(ncol)
for (a,b) in edges:
    print(colour[a][b])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    a -= 1
    b -= 1
    query[a].append((b,i))
    query[b].append((a,i))
  ans = 0
  for i in range(n):
    ans = max(ans,len(query[i]))
  print(ans)
  node = deque([])
  stack = [[] for _ in range(n)]
  for i in range(n):
    if len(query[i]) == ans:
      node.append((i,ans,100000))
      break
  for i in range(n):
    stack[i] = (len(query[i]))
  #print(stack)
  tmp = [-1]*(n-1)
  visit = [False]*n
  while node:
    #print(node)
    place,maxnode,last = node.popleft()
    donotuse = [last]
    for j,i in query[place]:
        if tmp[i] == -1:
          while maxnode in donotuse:
            maxnode -= 1
            if maxnode <= -1:
              maxnode = ans
          tmp[i] = maxnode
          donotuse.append(maxnode)
          maxnode -= 1
        
        if visit[j]:
          continue
        else:
          node.append((j,stack[j],tmp[i]))
    visit[place] = True
    
    
  for i in tmp:
    print(i)
solve()

Submission status: Accepted

Solution code:
import collections

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

#print(counter)
#print(counter)
max_e = max(counter)
colors_node = [-1 for _ in range(n + 1)]

edges.sort(key = lambda x: (x[1], x[2]))

colors = [-1 for _ in range(n + 1)]
cnt = 1
origin = -1
for i in range(n - 1):
	if origin == edges[i][1]:
		cnt += 1
	else:
		cnt = 1
		origin = edges[i][1]

	edges[i].append((colors[edges[i][1]] + cnt) % max_e)
	colors[edges[i][2]] = (colors[edges[i][1]] + cnt) % max_e

print(max_e)
edges.sort(key = lambda x: x[0])
for i in range(n - 1):
	print(edges[i][3] + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

print(max(map(len, nl)))

ans = [-1 for _ in range(N - 1)]
q = deque()
q.append((1, -1, -1))
while len(q) > 0:
    v, p, pc = q.popleft()
    color = 1
    for next_v, i in nl[v]:
        if next_v == p:
            continue
        if color == pc:
            color += 1
        ans[i] = color
        q.append((next_v, v, color))
        color += 1
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append((b-1,i))
    l[b-1].append((a-1,i))
from collections import deque
q=deque([(AB[0][0]-1,1),(AB[0][1]-1,1)])
e[0]=1
M=1
while q:
    vp,c=q.popleft()
    x=1
    for vn,en in l[vp]:
        if e[en]==0:
            if x==c:
                x=c+1
            q.append((vn,x))
            e[en]=x
            M=max(M,x)
            x+=1
print(M)
print(*e,sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

def bfs(tree, idx, mx_color, n):
    queue = deque([])
    queue.append([idx, n, color+1])
    edge_color = {}
    visit = [False] * (n)
    visit[idx] = True

    while queue:
        parent,p,cc = queue.popleft()
#         print(parent, cc, '-', tree[parent])
        res_color =  my_index(tree[parent], p, -1)+1
        for i, child in enumerate(tree[parent]):
            if visit[child]:
                continue
            child_color = res_color if i+1 == cc else (i+1)
            edge_color[str(min(parent,child))+','+str(max(parent,child))] = child_color
#             print([child, child_color])
            queue.append([child, parent, child_color])
            visit[child] = True
    return edge_color

n = int(input())
tree = [[] for _ in range(n)]
edge = []
for _ in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    edge.append(str(min(a,b))+','+str(max(a,b)))
color = max(len(i) for i in tree)

edge_color = bfs(tree, 0, color, n)
print(color)
#print(edge_color)
[print(edge_color[c]) for c in edge]

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()

    g = {}
    t = {}
    ans = [1] * (n-1)
    k = [0] * (n+1)

    for i in range(n-1):
        a, b = LMIIS()
        if a in g:
            g[a].append(b)
        else:
            g[a] = [b]
        if b in g:
            g[b].append(a)
        else:
            g[b] = [a]
        t[index(a, b)] = i

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

    while len(q) > 0:
        a, b = q.pop()
        used = ans[t[index(a,b)]]
        if k[a] == 0:
            k[a] = 1
            color = 1
            for x in g[a]:
                if color == used:
                    color += 1
                if x == b:
                    continue
                ans[t[index(a, x)]] = color
                color += 1
                q.append([a,x])

        if k[b] == 0:
            k[b] = 1
            color = 1
            for x in g[b]:
                if color == used:
                    color += 1
                if x == a:
                    continue
                ans[t[index(b, x)]] = color
                color += 1
                q.append([b,x])

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












if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
data = [0]*(N-1)
cho = [0]*(N+1) #cho[i]にi番目の頂点の根元の色
res = [0]*(N-1) #枝の色
for i in range(0,N-1):
    di = list(map(int, input().split()))
    di.append(i)
    data[i] = di

data = sorted(data)
for i in range(0,N-1):
    if i != 0 and data[i][0] == data[i-1][0]:
        cur += 1
    else:
        cur = 1
    if cur == cho[data[i][0]]: cur += 1
    res[data[i][2]] = cur
    cho[data[i][1]] = cur

print(max(cho))
for item in res:
    print(item)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(200000)

def decide_col(colors, edges, node, org, excl_color,max_col):
    if len(edges[node]) > 1:
        i = 1
        for elem in edges[node]:
            next_node = elem[0]
            ind = elem[1]
            if next_node != org:
                while i == excl_color:
                    i = i%max_col + 1
                colors[ind] = i
                decide_col(colors, edges, next_node, node, i,max_col)
                i += 1
    

def det_color(N,edges,start,max_col):
    colors = [0]*(N-1)
    i=1
    for elem in edges[start]:
        node = elem[0]
        ind = elem[1]
        colors[ind] = i
        decide_col(colors, edges, node, start, i, max_col)
        i += 1
    return colors
        

N = int(input())
edges = {}
edge_list = []

for i in range(N):
    edges[i] = []
count = [0]*N

for i in range(N-1):
    A, B = map(int,input().split())
    edge_list.append([A-1,B-1])
    edges[A-1].append([B-1,i])
    edges[B-1].append([A-1,i])
    count[A-1] += 1
    count[B-1] += 1

max_col = max(count)
print(max_col)
start_ind = np.argmax(count)
if type(start_ind)==list:
    start = start_ind[0]
else:
    start = start_ind
colors = det_color(N,edges,start,max_col)

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd, Counter
N = int(input())
edges = [None] * (N-1)
es = dd(dict)
for i in range(N-1):
    a, b = map(int, input().split())
    es[a][b] = es[b][a] = i

q = []
q.append((1, -1))
while q:
    i, used = q.pop()
    color = 0
    for to, eid in es[i].items():
        if edges[eid] is not None:
            continue
        color += 1
        if color == used:
            color += 1
        edges[eid] = color
        q.append((to, color))

ct = Counter(edges)
print(len(ct))
for e in edges:
    print(e)

Submission status: Accepted

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


n = int(input())
routes = []
dic = [{}] * n
edges = [[]for _ in range(n)]
used = [0]*n

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

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        dic[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(dic[_from][to])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
count = [0]*N
ans = [0]*(N-1)
closed = [0]*N
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)
    count[a-1] += 1
    count[b-1] += 1

K = max(count)
print(K)

queue = deque([[0,K+1]])


while queue:
    q,m = queue.popleft()
    p = 1
    for i in node[q]:
        if p == m:
            p += 1
        if ans[i] == 0:
            ans[i] = p
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if closed[next] == 0:
                queue.append([next,p])
                closed[next] = 1
            p += 1

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    ab = [list(map(int, input().split())) for i in range(n - 1)]
    # ab = sorted(ab, key=lambda x: x[1])
    # ab = sorted(ab, key=lambda x: x[0])
    e = [[] for i in range(n + 1)]
    ansl = {}
    for i in range(n-1):
        a, b = ab[i]
        e[a].append(b)
        ansl[(a,b)] = 0

    d = defaultdict(int)
    for i in range(n-1):
        a, b = ab[i]
        d[a] += 1
        d[b] += 1
    ans = 0
    for i in d.keys():
        ans = max(ans, d[i])
    print(ans)

    #ansl = 
    #ansl = [0 for i in range(n+1)]
    col = [-1 for i in range(n+1)]
    def f(v, c):
        col[v] = 1
        t = 1
        for i in e[v]:
            if col[i] == -1:
                if t == c:
                    t+=1
                ansl[(v,i)] = t
                #ansl[i] = t
                f(i, t)
                t+=1
    f(1,0)
    #print(*ansl)
    # for i in range(2,len(ansl)):
    #     print(ansl[i])
    for i in range(n - 1):
        a, b = ab[i]
        print(ansl[(a,b)])



    

    

    


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for p in P:
    if len(p) > C:
        C = len(p)


P2 = dict()
def f(n, pre, used):
    c = 1
    for i, next_n in enumerate(P[n]):
        if pre == next_n: continue
        if c == used: c += 1
        # P2[n][next_n] = c
        # P2[next_n][n] = c
        if n > next_n:
            a, b = next_n, n
        else:
            b,a = next_n, n
        P2[(a,b)] = c
        f(next_n, n, c)
        c += 1


print(C)
f(1, -1, 0)
for ab in AB:
    print(P2[ab])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
ab = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    ab[a].append([b, i])
    ab[b].append([a, i])
re = [False] * n
ed = [0]*(n-1)


def c(i=0, used=-1):
    global re, ed
    if re[i]:
        return 0
    re[i] = True
    k = 1
    for j in ab[i]:
        if re[j[0]]:
            continue
        if k == used:
            k += 1
        ed[j[1]] = k
        c(j[0], k)
        k += 1


c()
print(max(ed))
print(" ".join([str(i) for i in ed]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(N-1):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    T = dict()
    for i in range(N-1):
        T[(a[i]-1, b[i]-1)] = i
        T[(b[i]-1, a[i]-1)] = i
    q = [0]
    cn = max([len(g) for g in G])
    visited = [False] * N
    C = [0] * (N-1)
    while len(q) > 0:
        p = q.pop()
        visited[p] = True
        adj = G[p]
        v = None
        for a in adj:
            if visited[a]:
                v = a
        if v != None:
            ex = C[T[(v, p)]]
        else:
            ex = -1
        counter = 1
        for a in adj:
            if counter == ex:
                counter += 1
            if a != v:
                j = T[(a, p)]
                C[j] = counter
                counter += 1
        for a in adj:
            if not visited[a]:
                q.append(a)
    print(cn)
    for c in C:
        print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

G = defaultdict(list)

v = [-1 for _ in range(N - 1)]

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

def check(p, trg, pc):
    # print(p, trg, pc)
    c = 0
    for next_, vi in G[trg]:
        if next_ != p:
            if c == pc:
                c += 1
            check(trg, next_, c)
            v[vi] = c
            c += 1

check(0, 1, -1)
print(len(set(v)))
for c in v:
    print(c + 1)

Submission status: Accepted

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

Cs = [0] * (N + 1)
Tr = [[] for _ in range(N + 1)]
for i in range(N - 1):
    Cs[ABs[i][0]] += 1
    Cs[ABs[i][1]] += 1
    p = min(ABs[i][0], ABs[i][1])
    c = max(ABs[i][0], ABs[i][1])
    Tr[p].append((c, i))
K = max(Cs)
print(K)

import collections

d = collections.deque()
d.append(1)

Pc = [0] * (N + 1)
Nc = [1] * (N + 1)
ABsc = [0] * (N + 1)
Cis = [1] * N
while (len(d) > 0):
    p = d.popleft()
    for (c, i) in Tr[p]:
        d.append(c)
        col = Nc[p]
        if Pc[p] == col:
            col += 1
        Nc[p] = col + 1
        Pc[c] = col
        Cis[i] = col

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
degree = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_color = [0 for i in range(n)]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append([b,i])
    degree[a] += 1
    degree[b] += 1


maxcolor = max(degree)
search_list = [0]
node_color[0] = 0
color_list = [ k for k in range(1,maxcolor+1) ]

while search_list:
    new_search_list = []
    for i in search_list:
        p = 0
        for j, v in enumerate(connect_list[i]):
            a, b = v
            new_search_list.append(a)
            if node_color[i] == color_list[p]:
                p += 1
            node_color[a] = color_list[p]
            connect_list[i][j] = [b,color_list[p]]
            p += 1
    search_list = new_search_list

ans_list = []
for i in connect_list:
    for j in i:
        ans_list.append(j)

ans_list.sort()
print(maxcolor)
for i in ans_list:
    print(i[1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
L = []
dic = {}
E = [[] for _ in range(N)]
e = [0]*(N)
for i in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    e[a-1] += 1
    e[b-1] += 1
    L.append((a-1, b-1))
    
K = max(e)
print(K)

q = deque()
q.append((0, -1))
used = [0]*N
used[0] = 1
while q:
    t = q.popleft()
    num = 1
    for v in E[t[0]]:
        if used[v] == 0:
            used[v] = 1
            q.append((v, (t[1]+num)%K))
            if t[0] < v:
                dic[(t[0], v)] = (t[1]+num)%K+1
            else:
                dic[(v, t[0])] = (t[1]+num)%K+1
            num += 1
                
for i in range(N-1):
    print(dic[L[i]])

Submission status: Accepted

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
p, k = d.pop()
ans = [None] * (N - 1)
Q = collections.deque([(p, 0)])
while Q:
    p, fr = Q.popleft()
    color = 1
    for i in s[p]:
        if ans[i] is None:
            if color == fr:
                color += 1
            ans[i] = color
            Q += [(A[i] + B[i] - p, color)]
            color += 1
print(k)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
tree = [[] for _ in range(N)]
for n, (i, j) in enumerate(X):
    graph[i - 1].append(j - 1)
    graph[j - 1].append(i - 1)
    
    tree[i - 1].append((n, j - 1))
    
K = max(len(x) for x in graph)
q = deque()
q.append((0, 0))
ans = [0] * (N - 1)

while len(q) > 0:
    # u: node number, c: color
    u, c = q.popleft()
    
    cnt = 1
    for i, (n, v) in enumerate(tree[u]):
        if cnt == c:
            cnt += 1

        ans[n] = cnt
        q.append((v, cnt))
        cnt += 1
        
print(K)
print(*ans, sep="\n")

Submission status: Accepted

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


n = int(input())
dg = 10**6
edge = [[] for _ in [0]*n]
hen = []


for _ in [0]*(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    hen.append((a-1)*dg+b-1)

p = -1
q = -1
for i in range(n):
    if p < len(edge[i]):
        p = max(p,len(edge[i]))
        q = i

par = [-2]*n
chi = [[] for _ in [0]*n]
tank = []
new = [q]
par[q] = -1

while len(new) != 0:
    tank = []
    for e in new:
        for ch in edge[e]:
            if par[ch] < -1:
                par[ch] = e
                chi[e].append(ch)
                tank.append(ch)
    new = tank


co = [0]*n
new = [q]
while len(new) != 0:
    tank = []
    for e in new:
        color = 1
        for ch in chi[e]:
            if color == co[e]:
                color += 1
            co[ch] = color
            color += 1
            tank.append(ch)
    new = tank

print(p)
for e in hen:
    a,b = e//dg,e%dg
    if par[a] == b:
        print(co[a])
    else:
        print(co[b])

Submission status: Accepted

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

import sys

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

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

mx = 0
used = [set() for i in range(N)]
ans = [0] * (N-1)
cnt = 0
for u in range(N):
    mx = max(mx, len(nodes[u]))
    color = 1
    for v in nodes[u]:
        a, b = min(u, v), max(u, v)
        if edges[(a, b)][1] == -1:
            while color in used[a] or color in used[b]:
                color += 1
            edges[(a, b)][1] = color
            used[a].add(color)
            used[b].add(color)
            i = edges[(a, b)][0]
            ans[i] = str(color)
            color += 1
            cnt += 1
            if cnt == N-1:
                break
    else:
        continue
    break
print(mx)
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return "".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(a,b,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2
        if ll == mid:
            return ll
        co = mid * a
        mm = mid
        while mm != 0:
            co += b
            mm //= 10 
        if co >= r:
            rr = mid-1
        else:
            ll = mid


n = onem()

kkk = [[] for i in range(n)]

for i in range(n-1):
    a,b = m()
    kkk[a-1].append([b-1,i+1])
    kkk[b-1].append([a-1,i+1])
de = cl.deque([[0,0,0]])
kk= []
while de:
    j,k,p = de.popleft()
    co = 1
    for i in range(len(kkk[j])):
        if not kkk[j][i][0] == k:
            if co == p:
                co += 1
            de.append([kkk[j][i][0],j,co])
            kk.append([co,kkk[j][i][1]])
            co += 1

kk.sort(key = lambda x:x[1])

print(max(kk,key = lambda x:x[0])[0])

for i in range(n-1):
    print(kk[i][0])

Submission status: Accepted

Solution code:
from collections import deque

def read():
    N = int(input().strip())
    G = [list() for _ in range(N+1)]
    H = [list() for _ in range(N+1)]
    pairs = []
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
        H[a].append(i)
        H[b].append(i)
    return N, G, H

def paint_edges(N, G, max_edges, H):
    C = [-1 for _ in range(N-1)]
    q = deque()
    q.appendleft((1, -1))
    while(len(q) > 0):
        s, c = q.pop()
        for i in range(len(G[s])):
            t = G[s][i]
            idx = H[s][i]
            if C[idx] == -1:
                c = (c + 1) % max_edges
                C[idx] = c
                q.append((t, c))
    return C


def solve(N, G, H):
    max_edges = 0
    for i in range(N):
        max_edges = max(max_edges, len(G[i]))
    C = paint_edges(N, G, max_edges, H)
    return max_edges, C

if __name__ == '__main__':
    inputs = read()
    max_edges, C = solve(*inputs)
    print(max_edges)
    for c in C:
        print(c+1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
already = [1] * n 
k = 0
ans = [0] * (n-1)
queue = deque([0])
parent_colors = deque([0])

for index,(a,b) in enumerate(ab):
  a -= 1
  b -= 1
  tree[a].append((index,b))
  tree[b].append((index,a))
while len(queue):
  now = queue.popleft()
  
  if already[now]:
    already[now] = 0
    color = 1
    parent_color = parent_colors.popleft()
    for index,i in tree[now]:
      if already[i]:
        if color == parent_color:
          color += 1
        ans[index] = color
        parent_colors.append(color)
        color += 1
        queue.append(i)
         
print(max(ans))
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100010)
n=int(input())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
vis=[False for i in range(n+1)]
def dfs(node,lastco=-1):
    tmp=lastco
    for v in G[node]:
        if not vis[v]:
            tmp+=1
            co[v]=tmp%k
            vis[v]=True
            if node==edge[v][0]:
                dfs(edge[v][1],co[v])
            else:
                dfs(edge[v][0],co[v])

dfs(root)
print(k)
for i in range(n-1):
    print(co[i]+1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,pu=-1,pc=-1):
        c=0
        for cu in to[u]:
            if cu==pu:continue
            c+=1
            if c==pc:c+=1
            ei=etoi[(u,cu)]
            e_color[ei]=c
            dfs(cu,u,c)

    to=defaultdict(list)
    n=int(input())
    etoi={}
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append(b)
        to[b].append(a)
        etoi[(a,b)]=etoi[(b,a)]=i
    #print(etoi)
    e_color=[-1]*(n-1)
    max_deg_u=max(to.items(),key=lambda x:len(x[1]))[0]
    dfs(max_deg_u)
    print(max(e_color))
    print(*e_color,sep="\n")

main()

Submission status: Accepted

Solution code:
n = int(input())

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

maxp = 0
ce = [0] * n
cr = [0] * (n+1)
for i in range(1, n+1):
  ptr = 1
  while len(ne[i]) != 0:
    if ptr == cr[i]:
      ptr += 1
      continue
    else:
      cur,root = ne[i].pop()
      if ce[cur] == 0:
        ce[cur] = ptr
        cr[root] = ptr
        if ptr > maxp:
          maxp = ptr
        ptr += 1

print(maxp)
for i in range(1, n):
  print(ce[i])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n-1)

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

q = deque([(0, 0)])
while q:
    v, pc = q.popleft()
    nc = 0
    for nv, edge in t[v]:
        nc += 1
        if nc == pc: nc += 1
        color[edge] = nc
        q.append((nv, nc))

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def pair(a, b):
    return (a, b) if a < b else (b, a)


N = int(input())
E = []
V = defaultdict(list)
C = {}
for i in range(N - 1):
    a, b = map(lambda s: int(s) - 1, input().split())
    E.append((a, b))
    V[a].append(b)
    V[b].append(a)
    C[(a, b)] = 0

K = 1
Q = deque([1])
visited = [False] * N
while Q:
    v = Q.popleft()
    visited[v] = True
    used = []
    to_paint = []
    for nb in V[v]:
        if visited[nb]:
            used.append(C[pair(v, nb)])
        else:
            Q.append(nb)
            to_paint.append(nb)
    i = 0
    for tp in to_paint:
        i += 1
        while i in used:
            i += 1
        C[pair(v, tp)] = i
    K = max(i, K)

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    color=[-1]*n
    color[0]=0
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    print(max(color[1:]))
    for i,j in ab:
        print(color[j-1])
main()