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:
# -*- coding: utf-8 -*-
import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    n = ii()
    g = [[] for i in range(n)]
    edge = collections.namedtuple('edge', ['src', 'to', 'info'])
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append(edge(a - 1, b - 1, i))
        g[b - 1].append(edge(a - 1, b - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e.info] != -1:
                continue
            idx += 1
            ans[e.info] = idx
            q.append((e.to, idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.append((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max([len(g[i]) for i in range(n)])
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.append((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import queue
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max([len(g[i]) for i in range(n)])
    print(color)
    q = queue.Queue()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.put((0, 0))
    while not q.empty():
        t, idx = q.get()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.put((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
for i in path_num_to_edges[0]:
    d.append(i)
while d:
    temp_edge=d.pop()
    if temp_edge in tree_edge_flag:
        continue
    tree_edge_flag.add(temp_edge)
    new_path_color=1
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            old_color=path_color[path_num]
            break
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            continue
        if new_path_color==old_color:
            new_path_color+=1
        path_color[path_num]=new_path_color
        new_path_color+=1
        d.append(other_edge)

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

Submission status: Accepted

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

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

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

edges.sort()

used = [0]*(n)
ans = [0]*(n-1)
num = 1
prev = 0
for edge in edges:
    _from, to, id = edge
    if _from != prev:
        num = 1
    if used[_from] == num:
        num += 1
    ans[id] = num
    used[to] = num
    num += 1
    prev = _from

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

Submission status: Accepted

Solution code:
n = int(input())
edges = []

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

edges.sort()

used = [0]*(n)
ans = [0]*(n-1)
num = 1
prev = 0
for edge in edges:
    _from, to, id = edge
    if _from != prev:
        num = 1
    if used[_from] == num:
        num += 1
    ans[id] = num
    used[to] = num
    num += 1
    prev = _from

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

Submission status: Accepted

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

def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c]
        use = set(range(1, len(_next.keys()) + 1)) - set(next_[c].values())
        for _n, u in zip((k for k, v in _next.items() if v == 0), use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c]
        use = set(range(1, len(_next.keys()) + 1)) - set(next_[c].values())
        _next = (k for k, v in _next.items() if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    # color = [set([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        # use = set(range(1, len(_next) + 1)) - color[c]
        use = set(range(1, len(_next) + 1)) - set(next_[c].values())
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            # color[c].add(u)
            # color[_n].add(u)
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    # i != j => (ai, bi) != (aj, bj)
    next_ = [dict([]) for _ in range(n + 1)]
    color = [set([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        use = set(range(1, len(_next) + 1)) - color[c]
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            color[c].add(u)
            color[_n].add(u)
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
N = int(input())

from collections import defaultdict
from collections import deque

g = defaultdict(list)
idx = defaultdict(int)

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

#print(g)
q = deque()
q.append((1, 0))

res = [0] * (N-1)
n = 0
while q:
  #print(q)
  node, color = q.popleft()
  
  n = max(n, color)
  i = 1
  for nei in g[node]:
    if i == color:
      i += 1
    q.append((nei, i))
    res[idx[node, nei]] = i
    i += 1
print(n)
for c in res:
  print(c)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

ls = [list() for _ in range(n)]
ls2 = [list() for _ in range(n)]
edge = []
for i in range(n-1):
    x,y = map(int,input().split())
    ls[x-1].append(i)
    ls2[y-1].append(i)
    edge.append([x-1,y-1])

d = deque()
color = [0]*(n-1)
d.append(0)
while len(d):
    c = d.pop()
    cl = []
    for i in ls2[c]:
        if color[i]:
            cl.append(color[i])
    idx = 1
    for i in ls[c]:
        while(1):
            if not idx in cl:
                break
            else:
                idx += 1
        color[i] = idx
        cl.append(idx)
        d.append(edge[i][1])

print(max(color))
for i in color:
    print(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 deque
import sys
input = sys.stdin.readline

n = int(input())
adj = [[] for _ in range(n)]
edge = {}

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

que = deque()
que.append(0)
usd = [0]+[-1]*(n-1)
ans = [0]*(n-1)

while que:
    v = que.pop()
    j = 1
    for u in adj[v]:
        if usd[u] < 0:
            if j == usd[v]:
                j += 1
            usd[u] = j
            ans[edge[(u, v)]] = j
            que.appendleft(u)
            j += 1
print(max(ans))
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def kolorowe_grafy():
    N = wczytaj_liste()[0]
    lista_krawedzi = []
    listy_krawedzi = [[]]
    for i in range(N-1):
        lista_krawedzi.append(wczytaj_liste())
        listy_krawedzi.append([])
    for w1, w2 in lista_krawedzi: 
        listy_krawedzi[w1-1].append(w2)
        listy_krawedzi[w2-1].append(w1)
        
    do_przejrzenia = [1]
    kolory_zabronione = {1: 0}
    indeks_przegladanego = 0 
    kolor_tenczy = {}
    while indeks_przegladanego < len(do_przejrzenia): 
        aktualnie_przegladany = do_przejrzenia[indeks_przegladanego]
        kolor = 1
        if kolor == kolory_zabronione[aktualnie_przegladany]:
            kolor += 1
        for sasiad in listy_krawedzi[aktualnie_przegladany-1]: 
            if sasiad not in kolory_zabronione: 
                kolory_zabronione[sasiad] = kolor
                kolor_tenczy[(aktualnie_przegladany,sasiad)]=kolor
                kolor_tenczy[(sasiad,aktualnie_przegladany)]=kolor
                kolor += 1
                
                if kolor == kolory_zabronione[aktualnie_przegladany]:
                    kolor += 1
                do_przejrzenia.append(sasiad)
        indeks_przegladanego += 1
    maximum = 0
    for w1, w2 in lista_krawedzi:
        maximum = max(kolor_tenczy[(w1,w2)], maximum)
    print(maximum)
    for w1, w2 in lista_krawedzi:
        print(kolor_tenczy[(w1,w2)])

kolorowe_grafy()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
s=[[]for i in range(n+1)]
t=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    s[a-1].append([b-1,i])
def f(x,r):
    c=1
    for (i,j) in s[x]:
        if c==r:
            c+=1
        t[j]=c
        f(i,c)
        c+=1
f(0,0)
print(max(t))
for i in t:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict

children = defaultdict(list)
parent = defaultdict(list)
le = []

N = int(input())
for _ in range(N - 1):
    ai, bi = list(map(int, input().split()))
    le.append((ai, bi))
    children[ai].append(bi)
    parent[bi].append(ai)

# print(children)
# print(parent)

K = -1
degree = {}
for n in range(1, N + 1):
    knp = 0 if n not in parent else len(parent[n])
    knc = 0 if n not in children else len(children[n])
    # print(n, knp + knc)
    degree[n] = knp + knc
    K = max(K, knp + knc)

print(K)


root = 1
color = {}
queue = []

# init
for idx, v in enumerate(children[root]):
    color[root, v] = idx + 1
    queue.append((v, idx + 1))

while queue:
    u, pc = queue.pop()
    new_color = 1
    for idx, v in enumerate(children[u]):
        if new_color == pc:
            new_color += 1
        # print(u, pc, idx, v, new_color)
        color[u, v] = new_color
        queue.append((v, new_color))
        new_color += 1

# print(color)
for edge in le:
    print(color[edge])

Submission status: Accepted

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

def create_graph(N, a, b):
    g = {}
    for i in range(N-1):
        if a[i] in g:
            g[a[i]][b[i]] = 0
        else:
            g[a[i]] = {b[i]: 0}
        if b[i] in g:
            g[b[i]][a[i]] = 0
        else:
            g[b[i]] = {a[i]: 0}
    return g


def bfs(g, s):
    Q = queue.Queue()
    Q.put(s)
    while not Q.empty():
        p = Q.get()
        cs = set(range(len(g[p])+2)) - set([v for k, v in g[p].items()])
        for q in g[p].keys():
            # print(f"p:{p} q:{q} g:{g[p][q]}")
            if not g[p][q]:
                c = cs.pop()
                g[p][q] = c
                g[q][p] = c
                Q.put(q)


def solve(N: int, a, b):
    g = create_graph(N, a, b)
    bfs(g, a[0])
    # print(g)
    m = 1
    for i in range(N-1):
        m = max(m, g[a[i]][b[i]])
    print(m)
    for i in range(N-1):
        print(g[a[i]][b[i]])


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

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

class DFSState:
  def __init__(self, vertex, parent_color = -1, parent = -1):
    super().__init__()
    self.vertex = vertex
    self.parent_color = parent_color
    self.parent = parent

def solve(input_stream):
  N = read_int(input_stream)
  graph = [[] for i in range(N)]
  answer = [0 for i in range(N - 1)]
  K = 0
  for index in range(N-1):
    i,j = read_ints(input_stream)
    i-=1
    j-=1
    graph[i].append(Edge(j, index))
    graph[j].append(Edge(i, index))
  dfs = [DFSState(0)]
  while len(dfs) > 0 :
    color = 1
    state = dfs.pop(0)
    for index, value in enumerate(graph[state.vertex]):
      to = value.to
      edge_id = value.edge_id
      if to == state.parent:
        continue
      if color == state.parent_color:
        color += 1
      answer[edge_id] = str(color)
      dfs.append(DFSState(to, color, state.vertex))
      color += 1
  for value in graph:
    K = max(K, len(value))
  ans = [str(K)]
  ans.extend(answer)
  return ans

    


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
n = int(input())
edge = [tuple(map(int,input().split()))for _ in range(n - 1)]
T = [[] for _ in range(n)]
for i,(a,b) in enumerate(edge):
  # 木といいつつ有向グラフのように処理
  T[a -1].append([b - 1,i])
  #T[b - 1].append([a - 1,i])
ans = [None] * (n - 1)
def rec(cur,color):
  cnt = 1
  for (to,j) in T[cur]:
    if cnt == color:
      cnt += 1
    ans[j] = cnt
    rec(to,cnt)
    cnt += 1
rec(0,0)
print(max(ans))
[print(a) for a in ans]

Submission status: Accepted

Solution code:
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  val=len(set)+1
  if not(val in set):
    return(val)
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

ans = [None]*(N-1)
def rec(cur, color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1

rec(0,0)
print(max(ans))
[print(a) for a in ans]

Submission status: Accepted

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

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

def rec(cur,color):
    count = 1
    for (to,j) in G[cur]:
        if count == color:
            count += 1
        ans[j] = count
        rec(to,count)
        count += 1
rec(0,0)
print(max(ans))
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])

Submission status: Accepted

Solution code:
N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])

Submission status: Accepted

Solution code:
from queue import Queue

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

color = [0] * (N-1)
used_color =  [set() for _ in range(N)]

adj = [set() for _ in range(N)]
for i, (a, b) in enumerate(ab):
    adj[a - 1].add((i, b - 1))
    adj[b - 1].add((i, a - 1))

root = max(range(N), key=lambda x: len(adj[x]))

q = [root]

while q:
    node1 = q.pop()
    c=1
    for i, node2 in adj[node1]:
        while c  in used_color[node1]:
            c += 1
        color[i]=c
        used_color[node1].add(c)
        used_color[node2].add(c)
        adj[node2].remove((i, node1))
        q.append(node2)

print(len(used_color[root]))
for c in color:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ki = [[]for j in range(n)]
for i in range(n-1):
	    a,b=map(int,input().split())
	    a-=1
	    b-=1
	    ki[a].append([b,i])
	    ki[b].append([a,i])


a=[0]*n
for i in range(n):
	    a[i]= len(ki[i])
print(max(a))
clist=[-1]*(n-1)
visited=[[0]for i in range(n)]
def dfs(now,last,ban_color=-1):
	    color =1
	    for next,id in ki[now]:
	    	    
                     
	    	    if next == last:continue
	    	    if color == ban_color:
	    	    	    color+=1
	    	    clist[id] = color
	    	    dfs(next,now,color)
	    	    
	    	    color+=1
	    	    
dfs(0,-1)
print(*clist)

Submission status: Accepted

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

n = int(input())
T = [[] for _ in range(n)]
ab = [ tuple(map(int, input().split())) for _ in range(n-1) ]
for a, b in ab:
  T[a-1].append(b-1)
  T[b-1].append(a-1)
d = { (min(a)-1, max(a)-1):i for i, a in enumerate(ab) }
A = [1]*(n-1)
M = [set() for _ in range(n)]
seen = [False]*n
seen[0] = True
def dfs(v):
  now = 1
  for nv in T[v]:
    if not seen[nv]:
      seen[nv] = True
      while now in M[v]:
        now += 1
      A[d[(min(v, nv), max(v, nv))]] = now
      M[v].add(now)
      M[nv].add(now)
      dfs(nv)
dfs(0)
print(max(A), *A, sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
edges = []
node = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges += (a-1, b-1),
  node[a-1] += b-1,
  node[b-1] += a-1,

stuck = [(0,0)]
f = [1]+[0]*N
color_dic = dict()
while stuck:
  v, color = stuck.pop()
  i = 0
  for w in node[v]:
    if f[w]:
      continue
    f[w] = 1
    i += 1
    if i == color:
      i += 1
    stuck += (w,i),
    color_dic[v,w] = i

ans = []
for a,b in edges:
  if (a,b) in color_dic:
    ans += color_dic[a,b],
  else:
    ans += color_dic[b,a],

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

Submission status: Accepted

Solution code:
N=int(input().strip())
ab=[]
from collections import defaultdict
node=defaultdict(list)
edge={}
ans={}
for i in range(N-1):
    a,b=(map(int, input().strip().split()))
    edge[i]=(a,b)
    node[a].append(b)
    node[b].append(a)
from queue import Queue
q=Queue()
q.put(1)
K=0
col=defaultdict(set)
K=0
while not q.empty():
    i=q.get()
    nxt=[j for j in node[i] if j>i]
    c=1
    for n in nxt:
        while c in col[i]or c in col[n]:
            c+=1
        ans[(i,n)]=c
        col[i].add(c)
        col[n].add(c)
        K=max(K,c)
        q.put(n)
print(K)
for i in range(N-1):
    print(ans[edge[i]])

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

import sys
sys.setrecursionlimit(10**6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])
 
ans = [None] * (N-1)
 
def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])

    link = [set() for _ in range(n+1)]
    edge = []

    for i, ab in enumerate(args[1:]):
        a, b = sorted(map(int, ab.split()))
        edge.append((a, b))
        link[a].add(b)
        link[b].add(a)

    n_color = max(map(len, link))

    color = {}

    queue = [(0, 1)]

    while queue:
        parent, cur = queue.pop()
        used = color[tuple(sorted((parent, cur)))] if 0 < parent else 0
        c = 1

        for child in link[cur]:
            if child == parent:
                continue

            if c == used:
                c += 1
            color[tuple(sorted((cur, child)))] = c
            c += 1

            queue.append((cur, child))

    return str(n_color) + '\n' \
        + '\n'.join(map(str, (color[ab] for ab in edge)))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

from collections import deque


test = ""
#test = \
"""
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
"""
test = list(reversed(test.strip().splitlines()))
if test:
    def inp():
        return test.pop()
else:
    def inp():
        return input()
    

n = int(inp())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, inp().split()))


adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)


tag_dict = {1: 0}
edge_dict = dict()
nodeQ = deque([1])

while len(nodeQ):
    current_node = nodeQ.popleft()
    tag = tag_dict[current_node]
    
    a_list = [a for a in adjacency_list[current_node] if current_node < a]
    for (i, a) in enumerate(a_list):        
        tag_dict[a] = (tag + i) % (max_order) + 1
        edge_dict[(current_node, a)] = tag_dict[a]
        nodeQ.append(a)
             
print(max_order)
for edge in edges:
    print(edge_dict[edge])

Submission status: Accepted

Solution code:
import queue

n = int(input())
G = [[] for i in range(n)]
vp = [() for i in range(n - 1)]

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

que = queue.Queue()
que.put(0)
used = [0] * n
used[0] = 1
K = 0
cs = [0] * n
dic = {}
while not que.empty():
        v = que.get()
        if len(G[v]) > K:
                K = len(G[v])
        col = 1
        for u in G[v]:
                if used[u]:
                        continue
                if col == cs[v]:
                        col += 1
                cs[u] = col
                dic[(u, v)] = col
                dic[(v, u)] = col
                col += 1
                used[u] = 1
                que.put(u)
print(K)
for i in vp:
        print(dic[i])

Submission status: Accepted

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

ans = [None] * (N-1)

def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]