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:
import numpy as np

n = int(input())
l = np.zeros((n,n))
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    l[a,b] = 0.1
#print(l)                                                                                   
l_ = l.T
L = l+l_
s = np.sum(L,axis=0)
min_color = np.max(s)
c = 1

def search(l,idx,c):
    if c in l[idx[0],] or c in l[:,idx[1]]:
        return False
    else:
        return True
idxs = np.where(l==0.1)
C = 1
for i,j in zip(idxs[0],idxs[1]):
    idx = (i,j)
    c = 1
    while True:
        if search(L,idx,c):
            L[idx] = c
            L[idx[::-1]] = c
            break
        else:
            c += 1
    if c > C:
        C = c
print(C)
#print(L)                                                                                   
idxs_ = np.where(L*l*10 >= 1)
for i,j in zip(idxs_[0],idxs_[1]):
    print(int(L[(i,j)]))

Submission status: Runtime Error

Solution code:
n = int(input())

Adj_dict = {}
All_edges = []
for i in range(n):
    new = {i:[]}
    Adj_dict.update(new)
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a-1].append(b-1)
    Adj_dict[b-1].append(a-1)
    All_edges.append((a-1,b-1))

max_val_count = 0
start_node = 0
for key, val in Adj_dict.items():
    if len(val) >= max_val_count:
        max_val_count = len(val)
        start_node = key


Visited = [False for _ in range(n)]
Colors_use = [False for _ in range(max_val_count)]
edges_colors = {}

def coloring(Adj_dict, start, Visited, Colors_use):
    
    # 終端処理
    if Visited[start]:
        return
    
    Visited[start] = True

    for node in Adj_dict[start]:
        if Visited[node] == False:
            color = Colors_use.index(False) + 1
            Colors_use[color-1] = True
            
            edge_color = {(min(node, start), max(node, start)): color}
            edges_colors.update(edge_color)
            
            New_Colors_use = [False for _ in range(max_val_count)]
            New_Colors_use[color-1] = True
            
            coloring(Adj_dict, node, Visited, New_Colors_use)
    return

coloring(Adj_dict, start_node, Visited, Colors_use)

print(max_val_count)
for edge in All_edges:
    print(edges_colors[edge])

Submission status: Runtime Error

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

N = int(input())
A = [None]*N
B = [None]*N
K = 0

adj_list=[[] for _ in range(N)]
c_mat = [[-1]*N for _ in range(N)]
c_min_list=[-1]*N #A[i]に隣接する中で使っている色の最小値をメモ

for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    adj_list[A[i]-1].append(B[i]-1)
    adj_list[B[i]-1].append(A[i]-1)
    
#着色
def dfs(node_num,p_num,p_col):
    for i in range(len(adj_list[node_num])):
        to=adj_list[node_num][i]
        #親以外につながる辺を塗る
        if to!=p_num:
            #色を決める
            c_to = c_min_list[node_num]+1
            if c_to==p_col:
                c_to+=1
            c_min_list[node_num] = c_to
            c_mat[node_num][to] = c_to
            c_mat[to][node_num] = c_to
            dfs(to,node_num,c_to)



#計算，出力
dfs(0,-1,N)
K = max(c_min_list)+1
print(K)
for i in range(N-1):
    print(c_mat[A[i]-1][B[i]-1]+1)

Submission status: Runtime Error

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

N = int(input())
A = [None]*N
B = [None]*N
K = 0

adj_list=[[] for _ in range(N)]
c_list = [[] for _ in range(N)]
c_min_list=[-1]*N #A[i]に隣接する中で使っている色の最小値をメモ

for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    adj_list[A[i]-1].append(B[i]-1)
    adj_list[B[i]-1].append(A[i]-1)
    
#幅優先で着色
def bfs(node_num,p_num,p_col):
    for i in range(len(adj_list[node_num])):
        to=adj_list[node_num][i]
        #親以外につながる辺を塗る
        if to!=p_num:
            #色を決める
            c_to = c_min_list[node_num]+1
            if c_to==p_col:
                c_to+=1
            c_min_list[node_num] = c_to
            c_list[node_num].append((to,c_to))
            c_list[to].append((node_num,c_to))
            bfs(to,node_num,c_to)



#計算，出力
bfs(0,-1,N)
K = max(c_min_list)+1
print(K)
for i in range(N-1):
    for j in range(N-1):
        if c_list[A[i]-1][j][0]==B[i]-1:
            print(c_list[A[i]-1][j][1]+1)
            break

Submission status: Runtime Error

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

N = int(input())
A = [None]*N
B = [None]*N
K = 0

adj_list=[[] for _ in range(N)]
c_list = [[] for _ in range(N)]

for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    adj_list[A[i]-1].append(B[i]-1)
    adj_list[B[i]-1].append(A[i]-1)
    
#幅優先で着色
def bfs(node_num,p_num,p_col):
    global K
    for i in range(len(adj_list[node_num])):
        to=adj_list[node_num][i]
        #親以外につながる辺を塗る
        if to!=p_num:
            #色をiで振っていくが，もし親の色がiよりも小さい場合，色を１つ進める
            c_to=i
            if i>=p_col:
                c_to+=1
            if c_to>K:
                K=c_to
            c_list[node_num].append(c_to)
            bfs(to,node_num,c_to)
        else:
            #indexを揃えるため-1で埋める？
            c_list[node_num].append(-1)

#計算，出力
bfs(0,-1,-1)
print(K)
for i in range(N-1):
    j=adj_list[A[i]-1].index(B[i]-1)
    print(c_list[A[i]-1][j])

Submission status: Runtime Error

Solution code:
a, b, x = map(int, input().split())
def pb(y):
  return(b*int(len(str(y))))

def p(y):
  return(a*y + pb(y))

def by(y):
  l = 1
  for j in range(y):
    l = 10*l
  return(l)

if x >= p(by(9)):
  print(by(9))
elif x < p(1):
  print(0)
else:
  for i in range(9):
    if p(by(i)) <= x < p(by(i+1)):
      ans = int((x-pb(by(i)))/a)
      if ans < by(i+1):
        print(ans)
      else:
        print(by(i+1)-1)
      break

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b-1,i))
    graph[b-1].append((a-1,i))
ans = 0
pos = 0
for i in range(N-1):
    if ans < len(graph[i]):
        ans = len(graph[i])
        pos = i
print(ans)

color = [-1 for i in range(N-1)]
def dps(now,pare,par_col=-1):
    col = 1
    for u,idx in graph[now]:
        if u != pare :
            if col == par_col :
                col += 1
            color[idx] = col
            dps(u,now,col)
            col += 1

dps(0,-1,-1)
print("\n".join(map(str,color)))

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b-1,i))
    graph[b-1].append((a-1,i))
ans = 0
print(graph)
pos = 0
for i in range(N-1):
    if ans < len(graph[i]):
        ans = len(graph[i])
        pos = i
print(ans)

color = [-1 for i in range(N-1)]
def dps(now,pare,par_col=-1):
    col = 1
    for u,idx in graph[now]:
        if u != pare :
            if col == par_col :
                col += 1
            color[idx] = col
            dps(u,now,col)
            col += 1

dps(0,-1,-1)
print("\n".join(map(str,color)))

Submission status: Runtime Error

Solution code:
from sys import stdin

input = stdin.buffer.readline

n = int(input())
v = [[] for _ in range(n+1)]
edge = [0] * -~n

ans = 0


def dfs(c,fa,x):
    global ans
    color = 1
    for to, eg in v[x]:
        if to == fa:
            continue
        if color == c:
            color += 1
        edge[eg] = color
        ans = max(ans, color)
        dfs(color, x, to)
        color += 1


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

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

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
x=np.zeros((n,n), dtype=np.int32)
m=0
y=[]
yedge=[]

for _ in range(n-1):
    a,b=map(int, input().split())
    x[a-1][b-1]= 1
    x[b-1][a-1]= 1
    
    yedge.append((a,b))
    m=max(m,sum(x[a-1]))
    
count=0

#print (x)
for rank in range(n):
    count=0
    #print(rank, " - " , x[rank])
    for r,d in enumerate(x[rank]):
        #print("d = ", d)
        if ( d == 1 ):
            count = (count + d)
            if ( count % m > 0 ):
                count = count %m 
            x[rank][r]= count
            x[r][rank]= count 

print(m)

#print (x)
for (a,b) in yedge:
    print ( x[a-1][b-1]) 
    

#print(yedge)

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
x=np.zeros((n,n), dtype=np.int32)
m=0
y=[]

for _ in range(n-1):
  a,b=map(int, input().split())
  a0=max(x[a-1])
  n=a0+1 
  
  for e in range(a0):
    if (e not in x[b-1]) and (e not in x[a-1]):
      n=e
      break
      
  x[a-1][b-1]= n
  x[b-1][a-1]= n
  y.append(n)
  m=max(m,n)
    
print (m)
for d in y:
    print(d)

Submission status: Runtime Error

Solution code:
# input
n = int(input())

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

# process
ans = [0 for i in range(n-1)]

def f(pa, c):
    color = 1
    for pb in edge[pa]:
        if color == c: color += 1
        ans[pb[1]] = color 
        f(pb[0], color)
        color += 1

f(0, 0)

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>


using namespace std;
static const int MAX = 100000;

int N;
int color_num = 0;
vector<int> G[MAX];
vector<int> visited(MAX, 0);
vector<int> E;
void bfs(int node_num, int edge_num);

int main() {
    cin >> N;
    int k, l;
    for (int i = 0; i < N-1; i++) {
        scanf("%d %d", &k, &l);
        k--; l--;
        G[k].push_back(l);
        G[l].push_back(k);
    }

    bfs(0, 0);

    cout << color_num << '\n';
    for (int i = 0; i < E.size(); i++) {
        cout << E[i] << '\n';
    }

}

void bfs(int node_num_start, int edge_num_start) {
    queue<pair<int, int> > q;
    q.push(make_pair(node_num_start, edge_num_start));
    visited[node_num_start] = 1;
    pair<int, int> tmp;
    int node_num, edge_num_cur;
    int edge_num_used;
    while ( !q.empty()) {
        tmp = q.front();
        node_num = tmp.first;
        edge_num_used = tmp.second;
        q.pop();
        edge_num_cur = 1;
        for (int v = 0; v < G[node_num].size(); v++) {
            
            int cur = G[node_num][v];

            if (visited[cur] == 1) continue;
            visited[cur] = 1;
            if (edge_num_cur != edge_num_used) {
                E.push_back(edge_num_cur);
            }
            else {
                edge_num_cur++;
                E.push_back(edge_num_cur);
            }
            color_num = max(color_num, edge_num_cur);
            q.push(make_pair(cur, edge_num_cur));
            edge_num_cur++;
        }
    }
}

Submission status: Runtime Error

Solution code:
N = int(input())
for i in range(N):
    a, b = map(int, input().split())
l = [[i for i in range(10 ** 5)] for i in range(10 * 5)]
print(N)
for i in range(N):
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
for i in range(N):
    a, b = map(int, input().split())
l = [[i for i in range(10 ** 5)] for i in range(10 * 5)]

Submission status: Runtime Error

Solution code:
N = int(input())
for i in range(N):
  a, b = map(int, input().split())
l = [[0] * 100000 for i in range(100000)]

Submission status: Runtime Error

Solution code:
#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(100000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  
for some in edge[start_node]:
    d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                e.append((some,new_color))
while d:
    for some in d:
        determine_edge_color(some[0],some[1])
    d=e
    e=deque()
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

Submission status: Runtime Error

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

class Node:
    nodes = {}
    @classmethod
    def get_root_node(cls):
        #n = Node.nodes[next(iter(Node.nodes))]
        n = Node.nodes[1]
        for _ in range(len(Node.nodes)):
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = []
        list_to_visit += start_node.childs
        list_to_visit.append(-1)


        #while(len(list_to_visit)>0):
        for i in range(1000000)
            if len(list_to_visit)==0:
                break
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.remove(list_to_visit[0])
                continue
            node = list_to_visit[0]
            list_to_visit.remove(list_to_visit[0])
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            list_to_visit += node.childs
            list_to_visit.append(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        #return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"
        return str(self.id)

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)

for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()

Node.color_childs(root)
#Node.dump_all_nodes()
K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
class Node:
    nodes = {}
    @classmethod
    def get_root_node(cls):
        #n = Node.nodes[next(iter(Node.nodes))]
        n = Node.nodes[1]
        for _ in range(len(Node.nodes)):
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = []
        list_to_visit += start_node.childs
        list_to_visit.append(-1)
        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.remove(list_to_visit[0])
                continue
            node = list_to_visit[0]
            list_to_visit.remove(list_to_visit[0])
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            list_to_visit += node.childs
            list_to_visit.append(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)


for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()

Node.color_childs(root)
#Node.dump_all_nodes()
K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000) 
class Node:
    nodes = {}
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[next(iter(Node.nodes))]
        while True:
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = []
        list_to_visit += start_node.childs
        list_to_visit.append(-1)
        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.remove(list_to_visit[0])
                continue
            node = list_to_visit[0]
            list_to_visit.remove(list_to_visit[0])
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            list_to_visit += node.childs
            list_to_visit.append(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)


for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()
Node.color_childs(root)
#Node.dump_all_nodes()
K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Runtime Error

Solution code:

class Node(object):
    nodes = {}
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[next(iter(Node.nodes))]
        while True:
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = []
        list_to_visit += start_node.childs
        list_to_visit.append(-1)
        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.remove(list_to_visit[0])
                continue
            node = list_to_visit[0]
            list_to_visit.remove(list_to_visit[0])
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            list_to_visit += node.childs
            list_to_visit.append(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)


for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()
Node.color_childs(root)
#Node.dump_all_nodes()
K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Runtime Error

Solution code:

class Node:
    nodes = {}
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[next(iter(Node.nodes))]
        while True:
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"

    def append_child(self, node):
        self.childs.append(node)

    def set_parent_edge_color(self, c):
        self.parent_edge_color = c

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = []
        list_to_visit += start_node.childs
        list_to_visit.append(-1)
        while(len(list_to_visit)>0):
            #print("-----")
            #print("length"+ str(len(list_to_visit)))
            #print("visit to: " + str(list_to_visit[0]))
            #print("color with: "+ str(c))

            if list_to_visit[0]==-1:
            #    print("CAME HERE")
                c = 1
            #    print(c)
                list_to_visit.remove(list_to_visit[0])
                continue
            node = list_to_visit[0]
            list_to_visit.remove(list_to_visit[0])
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            #print("after color")
            #print(node)
            list_to_visit += node.childs
            list_to_visit.append(-1)
            c += 1
            #print("-----")

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)


for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()
Node.color_childs(root)
#Node.dump_all_nodes()

# ----- output -----

#print("output:=========================")

K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Submission status: Runtime Error

Solution code:
class Node:
    nodes = {}
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[next(iter(Node.nodes))]
        while True:
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def largest_num_color(cls):
        r = 0
        for key, node in Node.nodes.items():
            if node.num_color > r:
                r = node.num_color
        return r

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent # None if root Node
        self.parent_edge_color = None
        self.childs = {}
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        return f"id: {self.id}, parent: {x}, parent_edge_color: {self.parent_edge_color} ,num_child {len(self.childs)}, num_color {self.num_color}"

    def append_child(self, node):
        self.childs[node.id] = node

    def set_parent_edge_color(self, c):
        self.parent_edge_color = c

    def color_childs(self):
        c = 1
        for key, child_node in self.childs.items():
            if c == self.parent_edge_color:
                c += 1
            child_node.parent_edge_color = c
            c += 1
            child_node.color_childs()

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
for i in range(N-1):
    edge = list(map(int, input().split()))
    Edges.append(edge)


for edge in Edges:
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()
root.color_childs()
#Node.dump_all_nodes()

# ----- output -----

K = Node.largest_num_color()
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)