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: Runtime Error

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

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

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

    def dfs(focus,parent_color):
        if focus == N - 1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

    def dfs(focus,parent_color):
        if focus == N - 1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            dfs(child,color)
            color += 1

    dfs(0,0)

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

def main_ver0():
    N = int(input())
    sides = [[int(s) for s in input().split()] for i in range(N-1)]

    # まず最大次数を探す
    sides = sorted(sides)
    max_degree = 0
    current = 1
    current_degree = 0
    for side in sides:
        if side[0]==current:
            current_degree += 1
        else:
            current = side[0]
            current_degree = 2 #見ている頂点が変わるということは、1つ前の頂点から必ず1つ辺が出ているため
        max_degree = max(current_degree,max_degree)
    
    # 上から順番見ていくと、既に使われている色はひとつだけなので、それを除いて塗っていくだけでいい
    # 使用可能な色リスト
    color_list = [i for i in range(1,max_degree+1)]
    color_lists = []
    for i in range(N):
        color_lists.append(copy.copy(color_list))

    sides_color = []
    current = 0
    for side in sides:
        choose_color = color_lists[side[0]-1].pop(0)
        sides_color.append(choose_color)
        color_lists[side[1]-1].remove(choose_color) #次の頂点が使用可能な色から使用済の色を除く

    print(max_degree)
    for color in sides_color:
        print(color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in v:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x-1), input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in v:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Runtime Error

Solution code:
import os
import numpy as np

class getStdin(object):
    @classmethod
    def get_int(self):
        return int(input())

    @classmethod
    def get_ss_int(self):
        return list(map(int, input().split()))

class funcDfs(object):

    SEEN = list()

    def __init__(self, n, l):
        self.l = l
        self.graph = dict()
        for i in range(1, n+1):
            self.graph[i] = list()

        for li in l:
            a = li[0]
            b = li[1]
            self.graph[a].append(b)
            self.graph[b].append(a)

        self.SEEN = [False]*n

        self.k = 0
        for i in range(1, n+1):
            if self.k < len(self.graph[i]):
                self.ln = i
                self.k = len(self.graph[i])

        k = 1
        self.color = dict()
        for v in self.graph[self.ln]:
            if self.ln < v:
                cl = (self.ln, v)
            else:
                cl = (v, self.ln)

            self.color[cl] = k
            k += 1

        #print(self.color)


    def dfs(self, v):
        self.SEEN[v-1] = True

        base = list()
        for i in range(1, self.k+1):
            base.append(i)

        seenc = list()
        for i in self.color:
            if v in i:
                seenc.append(self.color[i])

        #print(self.graph)
        #print(self.color)
        #print(seenc)
        for i in seenc:
            base.remove(i)

        #print(base)
        for i in self.graph[v]:
            if i < v:
                tu = (i, v)
            else:
                tu = (v, i)

            #print(tu)
            if tu not in self.color:
                self.color[tu] = base[0]
                del base[0]


        for i in self.graph[v]:
            if self.SEEN[i-1]:
                continue

            if v < i:
                cl = (v, i)
            else:
                cl = (i, v)

            #if self.color.get(cl) is None:
            #    pass

            self.dfs(i)

        return


if __name__ == '__main__':
    n = getStdin.get_int()
    l = list()
    for _ in range(n-1):
        l.append(getStdin.get_ss_int())

    df = funcDfs(n, l)
    df.dfs(df.ln)
    print(df.k)
    for i in l:
        i.sort()
        print(df.color[tuple(i)])

    #print(df.color)
    os.sys.exit(0)

Submission status: Runtime Error

Solution code:

#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

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

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

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

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



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)

Submission status: Runtime Error

Solution code:

#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

import numpy as np

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

    m = np.zeros((N, N),dtype=int)

    for a, b in As:
        m[a-1][b-1] = m[b-1][a-1] = 1

    ans = np.zeros((N,N),dtype=int)

    from collections import deque

    max_c = 1
    l = deque([(0,0)])
    while (len(l)):
        v0, c0 = l.popleft()
        c1 = 1
        for v1 in range(N):
            if m[v0][v1]:
                m[v0][v1] = m[v1][v0] = 0
                if c1 == c0:
                    c1 += 1
                max_c = max(max_c, c1)
                ans[v0][v1] = ans[v1][v0] = c1
                l.append((v1, c1))
                c1 += 1

    print(max_c)
    for u, v in As:
        print(ans[u-1][v-1])



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]

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

ans = [None]*(N-1)

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

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = [None]*(N-1)

# 引数：今回の基準頂点、前回の基準頂点と今回の頂点を結ぶ辺の色番号
def func(ver, color):
    # 色番号。まずは最低の番号から始める。もし今回と前回の基準頂点の色番号1の場合は後で色番号変更
    cnt = 1
    # for (基準頂点と繋がっている頂点, 辺の番号) in 基準頂点
    for (to, i) in G[ver]:
        # 既使用（前回の基準頂点と今回の頂点を結ぶ辺の色）と今回使う色番号が同じなら+1で色番号変更
        if cnt==color:
            cnt += 1
        # i番目の辺における色番号
        ans[i] = cnt
        # 今回の頂点と、今回の頂点と基準頂点の辺の色番号を入力し、今回の頂点を次の基準頂点にする
        func(to, cnt)
        # 今回の基準頂点と繋がる次の頂点の処理をするために色番号変更
        cnt += 1

func(0, 0)

print(max(ans))

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

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0
keys = []

def get_key(n1, n2):
  if n1 > n2:
    return str(n2) + '-' + str(n1)
  return str(n1) + '-' + str(n2)

for _ in range(n - 1):
  a, b = map(int, input().split())
  keys.append(get_key(a - 1, b - 1))
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  if len(G[a - 1]) > color_num:
    root = a - 1
    color_num = len(G[a - 1])
  elif len(G[b - 1]) > color_num:
    root = b - 1
    color_num = len(G[b - 1])

# print(root) # 最も多い色を持つノードの番号
print(color_num) # 必要な最小色数
queue = [root]
checked = set()
result = {}

while len(queue) > 0:
  node = queue.pop(0)
  # print(node + 1)
  ks = list(range(color_num))
  for node2 in G[node]:
    key = get_key(node, node2)
    if key in result:
      ks.pop(result[key])
    if node2 not in checked:
      result[key] = ks.pop(0)
      queue.append(node2)
  checked.add(node)

for k in keys:
  print(result[k] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
l = [0 for i in range(N)]
li = [[0,0] for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    l[a] += 1
    l[b] += 1
print(max(l))
ans = [i % max(l) + 1 for i in range(N-1)]
for i in range(N-1):
    print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def main():
    N = int(input())
    visited = [False] * N
    d = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        d[a].append((b,i))
        d[b].append((a,i))

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    visited = [False] * N
    d = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        d[a].append((b,i))
        d[b].append((a,i))

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    if node > next_node:
        edge_color_hash[str(next_node) + " " + str(node)] = color
    else:
        edge_color_hash[str(node) + " " + str(next_node)] = color
    new_color = 1
    max_color = color
    if next_node in node_hash_list:
        for new_next_node in node_hash_list[next_node]:
            if color == new_color:
                new_color += 1
            if max_color < new_color:
                max_color = new_color
            temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
            new_color += 1
            if max_color < temp_color:
                max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    node_hash_list[a].append(b)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    new_color = 1
    max_color = color
    if next_node in node_hash_list:
        for new_next_node in node_hash_list[next_node]:
            if color == new_color:
                new_color += 1
            if max_color < new_color:
                max_color = new_color
            temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
            new_color += 1
            if max_color < temp_color:
                max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    node_hash_list[a].append(b)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    node_hash_list[a].append(b)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Submission status: Runtime Error

Solution code:
#D
from collections import deque
#import bisect
#import math
#import heapq
#import sys
#input = sys.stdin.readline

#inf = float("inf")
#mod = 10**9 + 7
#mod = 998244353

#list(map(int,input().split()))

N = int(input())
AB = [list(map(int,input().split())) for i in range(N-1)]
K = [0]*N
for ab in AB:
    a,b = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)

C = [0]*N
D = deque(AB)
flag = 0
visited = [-1]*N
#print(D)
while D:
    a,b = D.popleft()
    if visited[a-1] == -1 and visited[b-1] == -1:
        if flag == 0:
            flag = 1
            visited[a-1] = 0
            visited[b-1] = 0
            print(1)
            C[a-1] = 1
            C[b-1] = 1
        else:
            D.append([a,b])
    else:
        if visited[b-1] == -1:
            if C[a-1] == k:
                print(1)
                C[a-1] = 1
                C[b-1] = 1
            else:
                print(C[a-1]+1)
                C[a-1]+=1
                C[b-1] = C[a-1]
            visited[b-1] = 0
        else:
            visite[a-1] = 0
            if C[b-1] == k:
                print(1)
                C[a-1] = 1
                C[b-1] = 1
            else:
                print(C[b-1]+1)
                C[b-1]+=1
                C[a-1] = C[b-1]

Submission status: Runtime Error

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

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

res = [-1 for _ in range(N-1)]
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dfs(child,v,col)
            col += 1
dfs()
print("\n".join(map(str, res)))

Submission status: Runtime Error

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

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

res = [-1 for _ in range(N-1)]
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dps(child,v,col)
            col += 1
dfs()
print("\n".join(map(str, res)))

Submission status: Runtime Error

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

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

res = [-1 for _ in range(N-1)]
def dps(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dps(child,v,col)
            col += 1
dps()
print("\n".join(map(str, res)))

Submission status: Runtime Error

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

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

res = [-1]*(N-1)
def dps(v=0, p=-1, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dps(child,v,col)
            col += 1
dps()
print("\n".join(map(str, res)))

Submission status: Runtime Error

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

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

res = [-1 for _ in range(N-1)]
def dps(v=0, p=-1, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dps(child,v,col)
            col += 1
dps()
print("\n".join(map(str, res)))

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N+1)]
for i in range(N-1):
    a_,b_ = input().split()#1<=a<=N,1<=b<=N
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
color = 0

import numpy as np
color_map = np.zeros((N+1,K+1))
print(K)
min_color = [1 for i in range(N+1)]
for i in range(N-1):
    a_ = a[i]
    b_ = b[i]
    max_c = 1#max([min_color[a_],min_color[b_]])
    for k in range(max_c,K+1):
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            if(k==min_color[a_]):
                min_color[a_]+=1
            if(k==min_color[b_]):
                min_color[b_]+=1
            print(k)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    m[a-1] +=1
    m[b-1] +=1
    k=1
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    m[a+1] +=1
    m[b+1] +=1
    k=1
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
N = int(input())
ans = [0] * (N - 1)
AB = []
for i in range(N-1):
    a,b = map(int,input().split())
    AB.append([a-1,b-1])
G = [list() for _ in range(N)]
for i in range(N-1):
    G[AB[i][1]].append([AB[i][0],i])
    G[AB[i][0]].append([AB[i][1],i])

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx,len(G[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

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


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

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

Submission status: Runtime Error

Solution code:
def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

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

Submission status: Runtime Error

Solution code:
def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

top=[i+1 for i in range(n)]
for i in tree:
    for j in i:
        top.remove(j[0])
top=top[0]

rootedTree(top,0,tree[top],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    if len(root)==0:continue
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

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

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
vertexes_parent = []
vertexes = [[0, []] for i in range(100000)]
number_list = [0 for i in range(100000)]
vertexes_link = [[] for i in range(100000)]

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

max_color = max(number_list)

queue = deque()
queue.append([0, vertexes_parent[0]])
# print(vertexes_link)
# print(vertexes_parent)
# print(vertexes)

while len(queue) != 0:
    temp = queue.popleft()
#    print(temp)
    root = vertexes_link[temp[1]]
    color = temp[0]
    j = 0
    for i in root:
        j += 1
        if j == color:
            j += 1
        queue.append([j, i])
        vertexes[temp[1]][1].append(j)


print(max_color)

for i in range(n-1):
    print(vertexes[vertexes_parent[i]][1][vertexes[vertexes_parent[i]][0]])
    vertexes[vertexes_parent[i]][0] += 1

Submission status: Runtime Error

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N-1)]
Path=[[] for i in range(N)]
for p in P:
  Path[p[0]-1].append(p[1]-1)
  Path[p[1]-1].append(p[0]-1)
colornum=1
dic={}
def bfs(nodes,p,pcolor,selfnum):
  global colornum
  if len(nodes)-1==0 and p!=-1:
    return
  c=1
  for n in nodes:
    if n == p:
      continue
    if c==pcolor:
      c+=1
    dic[(selfnum+1,n+1)]=c
    dic[(n+1,selfnum+1)]=c
    bfs(Path[n],selfnum,c,n)
    c+=1
  if c>colornum:
    colornum=c
bfs(Path[0],-1,0,0)
print(colornum-1)
for p in P:
  print(dic[p])