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
input = sys.stdin.buffer.readline

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

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
  
def make_tree(graph, root) -> (list, list, list):
    INF = 10 ** 15
    dist = [INF] * len(graph)
    parent = [-1] * len(graph)
    stack = [root]
    dist[root] = 0
    order = []
    parent[root] = root
    while stack:
        s = stack.pop()
        order.append(s)
        for g in graph[s]:
            if dist[g] > dist[s] + 1:
                dist[g] = dist[s] + 1
                parent[g] = s
                stack.append(g)
    return dist, parent, order
    
dist, parent, order = make_tree(graph, 1)

color = [-1] * (N + 1)
for s in order:
    ng = color[s]
    c = 1
    for g in graph[s]:
        if parent[s] == g:
            continue
        if c == ng:
            c += 1
        color[g] = c
        c += 1

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

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

Submission status: Accepted

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

vc=[0]*n
ec=[0]*(n-1)
h=1

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

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

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)] # 0-indexed
edges = [[] for _ in range(N+1)] # 1-indexed
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

order = [] # 頂点１を根とした時、上からの頂点の順番
parent = [0] * (N+1) # 1-indexed
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for y in edges[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1) # 1-indexed 頂点iの親方向への辺の色
for o in order:
    ng = color[o]
    c = 1
    for z in edges[o]:
        if z == parent[o]:
            continue
        if c == ng:
            c += 1
        color[z] = c
        c += 1

answer = []
append = answer.append
for i in range(N-1):
    a, b = AB[i]
    if a == parent[b]:
        append(color[b])
    else:
        append(color[a])

print(max(answer))
print('\n'.join(map(str, answer)))
# 12

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)] # 0-indexed
edges = [[] for _ in range(N+1)] # 1-indexed
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

order = [] # 頂点１を根とした時、上からの頂点の順番
parent = [0] * (N+1) # 1-indexed
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for y in edges[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1) # 1-indexed 頂点iの親方向への辺の色
for o in order:
    ng = color[o]
    c = 1
    for z in edges[o]:
        if z == parent[o]:
            continue
        if c == ng:
            c += 1
        color[z] = c
        c += 1

answer = []
for i in range(N-1):
    a, b = AB[i]
    if a == parent[b]:
        answer.append(color[b])
    else:
        answer.append(color[a])

print(max(answer))
print('\n'.join(map(str, answer)))
# 12

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n+1)]
color = [set([]) for _ in range(n+1)]
ans = {}
for a, b in ab:
    tree[a].append(b)

q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    cnt = 1
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            # non-used color decided
            if cnt in color[now]:
                cnt += 1
            color[i].add(cnt)
            ans[(now, i)] = cnt
            cnt += 1

print(max(ans.values()))
for i in ab:
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)

n = int(input())
arr = []

for i in range(n-1):
    S = input()
    ar = [int(s) for s in S.split(" ")]
    arr.append(ar)

def prepare(n, arr):
    data = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    childNums = [0 for i in range(n)]

    for ar in arr:
        start = ar[0] - 1
        to = ar[1] - 1
        data[start].append(to)
        data[to].append(start)
    return data, nodeStates, childNums


data, nodeStates, childNums = prepare(n, arr)
mmk = {}
def generateID(start,to):
    if start < to:
        start,to = to, start

    return start * 100000 + to

def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    nodeStates[currentNode] = 1
    childNums[currentNode] = len(childNodes)
    kk = 0
    for ch in childNodes:
        if nodeStates[ch] == -1:
            kk = kk + 1
            if kk == x:
                kk = kk + 1
            mmk[generateID(currentNode+1,ch+1)] = kk
            dfs(ch, arr, kk)

dfs(0, data, -1)
print(max(childNums))
for ar in arr:
    start = ar[0]
    to = ar[1]
    print(mmk[generateID(start,to)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

N=int(input())
ab=[list(map(int, input().split())) for _ in range(N-1)]
to=[[] for _ in range(N)]
color=[0 for _ in range(N-1)]
for i in range(N-1):
    a, b=ab[i]
    a-=1
    b-=1
    to[a].append([b, i])
    to[b].append([a, i])

def dfs(v, p=-1, c=-1):
    k=1
    for i in range(len(to[v])):
        u, index=to[v][i]
        if u==p:
            continue
        if k==c:
            k+=1
        color[index]=k
        dfs(u, v, k)
        k+=1

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(100000)

n = int(input())
arr = []
for i in range(n - 1):
    arr.append([int(s) for s in input().split(" ")])

mmk = {}

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]


def generateID(fr, to):
    if to < fr:
        fr, to = to, fr
    return fr * 100000 + to


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mmk[generateID(currentNode + 1,childNodeIndex + 1)] = kk
            dfs(childNodeIndex, arr, kk)


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in arr:
    a0 = ar[0]
    a1 = ar[1]
    print(mmk[generateID(a0,a1)])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

from collections import deque

n = ni()
ab = nan(n - 1)

to = [[] for i in range(n)]
for i in range(n - 1):
    a, b = ab[i][0] - 1, ab[i][1] - 1
    to[a].append(b)
    to[b].append(a)

q = deque()
q.append((0, 0, -1))
color = 0
d = dict()
m = 0
while len(q):
    p = q.pop()
    j = 0
    for i in to[p[0]]:
        if i == p[2]:
            continue
        j += 1
        if j == p[1]:
            j += 1
        m = max(m, j)
        q.append((i, j, p[0]))
        d[(p[0], i)] = j

print(m)
for i in range(n - 1):
    print(d[(ab[i][0] - 1, ab[i][1] - 1)])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict, deque

def bfs(tree, k):
  dq = deque()
  dq.append((-1, 1, 0))
  print(k)
  ans = dict()
  while dq:
    _, s, c = dq.popleft()
    if _ != -1:
      ans[(_, s)] = c
    for i, t in enumerate(tree[s]):
      dq.append((s, t, ((c+i) % (k)+1)))
  return ans

def main():
  n = int(input())
  edges = [tuple(map(int, input().strip().split())) for _ in range(n-1)]
  counts = numpy.zeros(n)
  tree = defaultdict(list)
  for s, t in edges:
    counts[s-1] += 1
    counts[t-1] += 1
    tree[s].append(t)
  k = int(numpy.max(counts))
  ans = bfs(tree, k)
  for edge in edges:
    print(ans[edge])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:

N = int(input())
EDGES = [[] for _ in range(N+1)]
P = [(set(), 1) for _ in range(N+1)]

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

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

def dfs(root):
  # from, parent, color
  stack = [(root, -1, -1)]
  visited = set()

  while stack:
    u, parent, color = stack.pop()
    visited.add(u)

    nextColor = 1

    for (v, index) in EDGES[u]:
      if v not in visited and v != parent:
        if nextColor == color:
          nextColor += 1
        stack.append((v, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

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

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, AB):
    g = [[] for _ in range(n + 1)]
    for i, (a, b) in enumerate(AB):
        g[a].append(b)

    q = deque(maxlen=n)
    q.append((1, -1))
    k = 0
    color = {}
    while q:
        node, col = q.popleft()
        count = 0
        for i in range(len(g[node])):
            if i == col:
                count += 1
            color[(node, g[node][i])] = count
            q.append((g[node][i], count))
            count += 1
        if k < count - 1:
            k = count - 1
    return [k + 1] + [color[(a, b)] + 1 for a, b in AB]

_n = int(input())
_AB = [tuple(map(int, input().split())) for _ in range(_n - 1)]
print(*solve(_n, _AB), sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
raw = []
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw.append([a,b])
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
clr = [10**6 for _ in range(n)]
clr2 = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
rank[0] = 0
clr[0] = 0
clr2[0] = 0
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        clr[y] = clr2[x] + 1
        clr2[y] = clr[y]
        clr2[x] += 1
        rank[y] = rank[x] + 1
        now.append(y)
maxi = 0
for i in range(n):
  maxi = max(maxi,len(peer[i]))
print(maxi)
for i in range(n-1):
  a,b = raw[i]
  if rank[a] < rank[b]:
    c = b
  else:
    c = a
  print(clr[c] % maxi + 1)
#print(clr)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

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

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

Ans = [-1] * (N-1)
def dfs(v, pc=-1, p=-1):
    c = 1
    for u, idx in E[v]:
        if (u == p):
            continue
        if (c == pc): 
            c += 1
        Ans[idx] = c
        dfs(u, c, v)
        c += 1

dfs(1)
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:
from math import ceil

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

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

    for i in range(N-1):
        a,b = AB[i]
        Edge[a].append((b,i))
        Edge[b].append((a,i))
    Ans = [-1]*N

    stack = [1]
    gone = [False]*(N + 1)
    gone[1] = True
    ans = 0
    Index = {1:0}
    while len(stack) > 0:
        color = 1
        start = stack.pop(-1)
        parent = Index[start]
        for e,index in Edge[start]:
            if not(gone[e]):
                Index[e] = start
                stack.append(e)
                gone[e] = True
                if parent == color:
                    color += 1
                    Ans[index] = color
                    Index[e] = color
                else:
                    Ans[index] = color
                    Index[e] = color
                color += 1
        ans = max(ans,color-1)
    print(ans)
    print(*Ans[:-1],sep="\n")
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())

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


ans = [0]*(n-1)

def col(now,color):
    c = 1
    for [b,j] in graph[now-1]:
        if c == color:
            c += 1
        ans[j-1] = c
        col(b,c)
        c += 1  

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


class Edge():
    def __init__(self, to_, id_):
        self._to = to_
        self._id = id_


G = [[Edge]]
ans = []

sys.setrecursionlimit(1000000)


def dfs(v, color, parent=-1):
    global G
    global ans
    c = 1
    if c == color:
        c += 1
    for g in G[v]:
        if g._to == parent:
            continue
        if ans[g._id] != -1:
            continue
        ans[g._id] = c
        dfs(g._to, c, v)
        c += 1
        if c == color:
            c += 1
    return


def main():
    # sys.stdin = open("sample.txt")
    global G
    global ans
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    ans = [-1 for _ in range(N-1)]
    dfs(0, 0)
    print(max(ans))
    print(*ans, sep="\n")
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)

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

def dfs(a, color):
    c = 1
    for b, i in links[a]:
        if c == color:
            c += 1
        colors[i] = c
        dfs(b, c)
        c += 1


dfs(0, 0)
print(max(colors))
for color in colors:
    print(color)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append((b, itr))
  e[b].append((a, itr))
  
cidx = max([len(i) for i in e])

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

q = deque()
q.append((0, 0, -1))
# 色は１から順に塗っていく
while q:
  v, p, pcol = q.popleft()
  col = 1
  for u, i in e[v]:
    if u != p:
      # 親と色がかぶる時は＋１
      if col == pcol:
        col += 1
      if ans[i] == -1: 
        ans[i] = col
      q.append((u, v, col))
      col += 1 

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**6)
n = int(input())
edge = [tuple(int(i) for i in input().split()) for i in range(n-1)]
to = [[] for _ in range(n+1)]
for e in edge:
    a,b = e
    to[a].append(b)
    to[b].append(a)
color = {}

def f(cn,pn,pc):
    c = 1
    for nn in to[cn]:
        if nn == pn: continue
        if c == pc: c += 1
        tmp = (cn,nn)
        color[(min(tmp),max(tmp))] = c
        f(nn,cn,c)
        c += 1

f(1,0,0)
print(max(color.values()))
for key in edge: print(color[key])

Submission status: Accepted

Solution code:
import sys,math

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

def main():
	N = II()
	to = [[] for _ in range(N)]
	ans = {}
	order = []
	for i in range(N-1):
		a,b = MI()
		a -= 1;b -= 1
		ans[str(a)+"-"+str(b)] = 0
		order.append(str(a)+"-"+str(b))
		to[a].append(b);to[b].append(a)
	
	def bfs():
		from collections import deque
		hist = [True]*N
		que = deque()
		que.append(0)
		e_colors = [0]*N
		max_c = 0
		while len(que) > 0:
			n = que.popleft()
			hist[n]=False
			for i in to[n]:
				if(hist[i]):
					ch = e_colors[n] | e_colors[i]
					index = int(math.log2(~ch & -~ch))
					e_colors[n] += 1 << index
					e_colors[i] += 1 << index
					ans[str(min(n,i))+"-"+str(max(n,i))] = index+1
					if(max_c < index+1): max_c = index+1
					que.append(i)
		print(max_c)
		for i in order:
			print(ans[i])

	bfs()


main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

d = defaultdict(list)
N = int(input())
l = []

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

parent = [0]*(N)
used = [False]*(N)
used[0]=True

q = deque()
q.append(0)
res = {}

max_n = 0
while q:
    p = q.popleft()
    color_num = 0
    for i in d[p]:
        if used[i]:continue

        used[i] = True
        
        color_num += 1
        # 根の値とかぶらない限り、1から小さい順に埋めるとよい
        if color_num == parent[p]:
            color_num+=1 # 根の値とかぶらないようにする
        parent[i] = color_num
        res[(p,i)] = color_num
        q.append(i)
    max_n = max(max_n, color_num)

print(max_n)
for i in l:
    print(res[i])

Submission status: Accepted

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

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

graph = [[] for _ in range(N+1)] #隣接リスト
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

#各子の色を決めていく。
color = [-1]*(N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if parent[x] == y:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

ans = []
for a,b in AB:
    if parent[a] == b: #子の頂点の色を入れる
        ans.append(color[a])
    else:
        ans.append(color[b])

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

Submission status: Accepted

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

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

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue

        over_color = len(tree[u])+1
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else over_color
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])


    
main()

Submission status: Accepted

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

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

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else len(tree[u])+1
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])


    
main()

Submission status: Accepted

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

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    N = int(input())
    edges = list(readlines(N-1))
    tree = {i:[] for i in range(N)}
    for a, b in edges:
        tree[a].append(b)

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else len(tree[u])+1
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for u,v in edges:
        print(ans[u,v])


    
main()

Submission status: Accepted

Solution code:
from collections import namedtuple, deque


def bfs():
    while queue:
        u = queue.popleft()
        i = 1
        for e in adj[u]:
            if e.t == u:
                continue
            if parent[u] == i:
                i += 1
            parent[e.t] = i
            ans[e.id] = i
            queue.append(e.t)
            i += 1


Edge = namedtuple('Edge', ('t', 'id'))

n = int(input())

adj = [[] for _ in range(n)]
for i in range(n - 1):
    s, t = (int(v) - 1 for v in input().split())
    edge = Edge(t, i)
    adj[s].append(edge)
    adj[t].append(edge)

k = len(max(adj, key=lambda x: len(x)))

queue = deque([0])
parent = [-1] * n
ans = [0] * (n - 1)
bfs()

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append((b,i))
    E[b].append((a,i))
#最大の次数を見つける
K = max(len(e) for e in E)
#Kを出力
print(K)
ans = [-1] * (N-1)
#深さ優先探索
#col:色の番号
#v:注目している頂点(スタート地点の頂点の番号は1)
#p:注目している頂点の親の頂点(スタート地点の親は存在しない０)
#p_col:注目している頂点とその親の頂点を結んでいる辺の色の番号(初期値は-1つまり存在しない)
def dfs(v=1,p=0,p_col=-1):
    #colを初期化する
    col = 1
    #idx:注目している辺の番号
    #u:注目している頂点と結ばれる頂点
    for u, idx in E[v]:
        #もし注目している頂点と親の頂点が一致したら何もしない
        if u != p:
            #注目している辺の色の番号と親の辺の色の番号が一致していないか確認
            #もし一致していたら色の番号を変える
            #一致していなければその辺の色の番号をansに格納する
            if col == p_col:
                col += 1
            ans[idx] = col
            #再帰的に深さ優先探索をくりかえす
            #現在注目している頂点を親の頂点に
            #uを次に注目している頂点とする
            #colを親の辺の番号とする
            dfs(u,v,col)
            #次の頂点へ行くために辺の色の番号を変更する
            col += 1

dfs()
#出力する
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append((b,i))
    E[b].append((a,i))
#最大の次数を見つける
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N-1)
def dfs(v=1,p=0,p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u,v,col)
            col += 1
dfs()
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
n = int(input())
g = [[] for _ 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])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)
 
dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
g = [[] for _ 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])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)
 
dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

q=[]

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

ans=[1]*N
ans[0]=0
#print(l)

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

mx=0
for index,item in enumerate(l):
    color=1
    while item:
        temp=item.pop(-1)
        if color==ans[index]:
            color+=1
        ans[temp]=color
        color+=1
    mx=max(color-1,mx)

print(mx)
for _,item in q:
    print(ans[item])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = {}
N = 0

def assign(assignment, u, prev_color):
    color = 1
    for v in tree[u]:
        if color == prev_color:
            color += 1
        assignment[u,v] = color
        assign(assignment, v, color)
        color += 1

def main():
    global tree, N
    N = int(input())
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

def dfs(v, c=-1, p=-1):
  k=1
  for i in range(len(to[v])):
    u, id=to[v][i]
    if u==p:
      continue
    if k==c:
      k+=1
    ans[id]=k
    k+=1
    dfs(u, ans[id], v)

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

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

es = [[] for _ in range(N)]
# 戻って塗らないので a->bだけ記録
for i in range(N-1):
    a,b = map(int, input().split())
    es[a-1].append((i, b-1))


ans = [0] * (N-1)
c = 1
prev_c = -1
"""
現在ノード、そこに至るための直前の辺の色を知っておく必要がある
q : (current_node, prev_color)
今見てるノードと、そこに来る直前のへんが何色かを示す
"""
q = deque()
q.append((0, prev_c))
while q:
    curr_node, pc = q.popleft()
    c = 1
    for edge_num, node in es[curr_node]:
        if c == pc:
            c += 1
        ans[edge_num] = c
        # 次確認するノードがnodeで、そこに至る直前の辺が色cでしたよ、を保存
        q.append((node, c))
        # curr_nodeに繋がる今のnodeの色と、のちのやつが被らないようにする
        c += 1

print(len(set(ans)))
print(*ans, sep="\n")