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:
from collections import deque
import sys

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]

input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

q = deque()
q.extend(tr.childs(1))
while q != deque():
    node = q.pop()
    V[node] += V[tr.parent(node)]
    if tr.childs(node):
        q.extend(tr.childs(node))

print(*V[1:])

Submission status: Runtime Error

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    for i in range(1, vertex):
        a, b = map(int, input().split())
        tree[a].append((b, i))
        tree[b].append((a, i))
    max_deg = 0
    root = 0
    for i in range(1, vertex):
        if max_deg < len(tree[i]):
            root = i
            max_deg = len(tree[i])
    queue = deque([root])
    while not queue == deque():
        color_list = [i for i in range(1, max_deg + 1)]
        now = queue.pop()
        for i, n in enumerate(tree[now]):
            if color[n[0]] == 0:
                color[n[0]] = color_list[0]
                queue.append(n[1])
                color_list.pop(0)
            else:
                color_list.remove(color[n[0]])
    print(max_deg)
    for c in color[2:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]

path=[[] for _ in range(n)]
for i,(a,b) in enumerate(AB):
  a,b=a-1,b-1
  path[a].append((b,i))
  path[b].append((a,i))
  
visited=[0]*n
ans=[None]*(n-1)
  
def dfs(v,c=-1):
  nc=1
  for to,i in path[v]:
    if visited[to]: continue
    visited[v]=1
    if nc==c: nc+=1
    ans[i]=nc
    dfs(to,nc)
    nc+=1
dfs(0)
print(max(ans))
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
N = int(input())


class Node:
    def __init__(self, index):
        self.index = index
        self.edges = []

class Edge:
    def __init__(self, index, a, b):
        self.a = a
        self.b = b
        self.index = index
        self.color = 0

    def to(self, fm):
        if fm == self.a:
            return self.b
        elif fm == self.b:
            return self.a
        else:
            return None


nodes = [Node(i) for i in range(N)]
edges = []
for i in range(N-1):
    a, b = map(int, input().split())
    edge = Edge(i, a-1, b-1)
    edges.append(edge)
    nodes[a-1].edges.append(edge)
    nodes[b-1].edges.append(edge)

passed = set()


def rec(node, via_color, K):
    passed.add(node.index)
    color = 1
    for edge in node.edges:
        to_node_index = edge.to(node.index)
        if to_node_index in passed:
            continue
        if color == via_color:
            color += 1
        edge.color = color
        K = rec(nodes[to_node_index], color, K)
        color += 1
    return max(color-1, K)


K = rec(nodes[0], 0, 1)
print(K)
for edge in edges:
    print(edge.color)

Submission status: Runtime Error

Solution code:

N = int(input())
E = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    E[a].append([b,i])
 
ans = [None]*(N-1)
 
def paint(now,color):
    No = 1
    for (to, en) in E[now]:
        if No == color:
            No += 1
        ans[en] = No
        paint(to,No)
        No += 1
 
paint(0,0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for b,i in E[p]:
    if m == n: m+=1
    ans[i]=m
    sub(b,m)
    m+=1
sub(0,0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for b,i in E[p]:
    if m == n: m+=1
    ans[i]=m
    sub(b,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
  E[b-1].append((a-1,i))
ans=[[] for _ in range(N-1)]
visitted=[False for _ in range(N)]
def sub(p, n):
  m=1
  visitted[p]=True
  for a,b in E[p]:
    if not visitted[a]:
      if m == n: m+=1
      ans[b]=m
      sub(a,m)
      m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
  E[b-1].append((a-1,i))
ans= np.empty(N-1)
def sub(p, n):
  m=1
  for a,b in E[p]:
    if not ans[b]:
      if m == n: m+=1
      ans[b]=m
      sub(a,m)
      m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
  E[b-1].append((a-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for a,b in E[p]:
    if not ans[b]:
      if m == n: m+=1
      ans[b]=m
      sub(a,m)
      m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for a,b in E[p]:
    if m == n: m+=1
    ans[b]=m
    sub(a,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a,b = min(a-1,b-1),max(a-1,b-1)
  E[a].append((b,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for a,b in E[p]:
    if m == n: m+=1
    ans[b]=m
    sub(a,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
E=[[] for _ in range(N-1)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for a,b in E[p]:
    if m == n: m+=1
    ans[b]=m
    sub(a,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

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

adj = defaultdict(list)
for i, (a, b) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))

k = max([len(li) for li in adj.values()])
print(k)

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

def dfs(u, p_col):
	col = 1
	for v, i in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1


dfs(0, -1)

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

Submission status: Runtime Error

Solution code:
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    ans = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()
            cnt=1

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if ans[x]!=cnt:
                        ans[y]=cnt
                        cnt+=1
                    else:
                        cnt+=1
                        ans[y]=cnt
                        cnt+=1

        return ans
    return bfs()

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

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

x=tree(0)
print(max(x))
for i in range(1,n):
    print(x[a[i][1]-1])

Submission status: Runtime Error

Solution code:
def Treemake(node,parent,root,num):
    A.append([node,parent,root,num])
    for i,j in root:
        Treemake(i,node,Tree[i],j)


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

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

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

Submission status: Runtime Error

Solution code:
def rootedTrees(node,parent,depth,name,root):
    A.append([node,parent,depth,name,root])
    for i in root:
        if len(Tree[i])!=0:
            rootedTrees(i,node,depth+1,"internal node",Tree[i])
        else:
            rootedTrees(i,node,depth+1,"leaf",Tree[i])


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

A=[]
rootedTrees(0,-1,0,"root",Tree[0])

for node,parent,depth,name,root in A:
    cnt=0
    if node==0:continue
    for i,j in enumerate(root):
        if color[node]==i:
            cnt +=1
        color[j]=i+cnt

print(max(color)+1)
for i in range(2,n+1):
    print(color[i]+1)

Submission status: Runtime Error

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

ans=[0]*(n-1)
g=[0]*n
def dfs(v,h=-1):
  res=1
  for i,j in c[v]:
      if g[i]:
            continue
      g[v]=1
      if h==res:
            res+=1
      ans[j]=res
      dfs(i,res)
      res+=1

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

Submission status: Runtime Error

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

ans=[0]*(n-1)
g=[0]*n
def dfs(v,h=-1):
  res=1
  for i,j in c[v]:
      if g[i]:
            continue
      g[v]=1
      if h==res:
            res+=1
      ans[j]=res
      dfs(i,res)
      res+=1

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      else:
         ans[ni]=color
         color+=1
         que.append(ni)
print(max(ans))
for i in L:
   print(ans(i))

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
l=[[] for i in range(n)]
ans=[0]*(n-1)

def dfs(v,c,p):
  k=1
  for i in range(len(l[v])):
    u=l[v][i][0]
    id=l[v][i][1]
    if(u==p):continue
    if(k==c):k+=1
    ans[id]=k
    k+=1
    dfs(u,ans[id],v)
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append((b-1,i))
  l[b-1].append((a-1,i))
dfs(0,-1,-1)
print(max(ans))
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
hen_count=[0 for i in range(n+1)]
HEN=[]
for i in range(n-1):
  a,b=map(int,input().split())
  hen_count[a]+=1
  hen_count[b]+=1
  HEN.append([a,b])
print(max(hen_count))

qwe=max(hen_count)
color=[0]+[[i+1 for i in range(qwe)] for i in range(n)]

for q in HEN:
  p=max(min(color[q[0]]),min(color[q[1]]))
  color[q[0]].remove(p)
  color[q[1]].remove(p)
  print(p)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, i))
  e[v].append((u, i))
res = [0] * (N - 1)
def dfs(x):
  global res
  c = 1
  vis = set()
  for y, i in e[x]: vis.add(res[i])
  #print(x, vis)
  for y, i in e[x]:
    if res[i] > 0: continue
    while c in vis: c += 1
    #print(x, c)
    res[i] = c
    vis.add(c)
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)

Submission status: Runtime Error

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

def col(now,color):
  c=1
  for (b,j) in A[now]:
    if c==color:
      c+=1
    ans[j]=c
    col(b,c)
    c+=1
col(0,0)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
n=int(input())
node={i:[] for i in range(1,n+1)}
visited=[False for i in range(n+1)]
q=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    q.append((a,b))

mother=q[0][0]
visited[mother]=True

d=[]
e=[]


paint={i:{} for i in range(1,n+1)}

mother_paint=[0 for i in range(n+1)]

#使う要素 node visited paint mother_paint の四つのリスト
c=1
for child in node[mother]:
    visited[child]=True
    paint[mother][child]=c
    paint[child][mother]=c
    mother_paint[child]=c
    c+=1
    d.append(child)
    
while d:
    for parent in d:
        p=1 
        for child in node[parent]:
            if visited[child]==False:
                visited[child]=True
                if p!=mother_paint[parent]:
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
                else:
                    p+=1
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
    if e:
        d=e.copy()
        e=[]
    else:
        d=[]
        e=[]
K=0
for i in range(1,n+1):
    K=max(K,len(node[i]))
print(K)
for i in range(n-1):
    s,t=q[i][0],q[i][1]
    print(paint[s][t])

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
con = [set() for _ in range(N+1)]

for ab in AB:
    con[ab[0]].add(ab[1])
    con[ab[1]].add(ab[0])

max_len = 0
for i, c in enumerate(con):
    if max_len <= len(c):
        max_len = len(c)
        max_ind = i

colors = [set() for i in range(N+1)]
all_colors = set([i for i in range(1, max_len+1)])
res = [0] * (N - 1)


for i, ab in enumerate(AB):
    res[i] = list(all_colors.difference(colors[ab[0]].union(colors[ab[1]])))[0]
    colors[ab[0]].add(res[i])
    colors[ab[1]].add(res[i])

print(max_len)
for r in res:
    print(r)

Submission status: Runtime Error

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

max_len = 0
for i, c in enumerate(con):
    if max_len <= len(c):
        max_len = len(c)
        max_ind = i

colors = [set() for i in range(N+1)]
all_colors = set([i for i in range(1, max_len+1)])
res = [0] * (N - 1)


for i, ab in enumerate(AB):
    res[i] = list(all_colors.difference(colors[ab[0]].union(colors[ab[1]])))[0]
    colors[ab[0]].add(res[i])
    colors[ab[1]].add(res[i])

print(max_len)
for r in res:
    print(r)

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N)]
ans = [[] for _ in range(N - 1)]

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

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

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:
N = int(input())
g = [[] for _ in range(N)]
ans = [[0] for _ in range(N - 1)]

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

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

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:
n=int(input())
edge={i:[] for i in range(n+1)}
colored={j:{} for j in range(n+1)}
before_colored=[0 for i in range(n+1)]
querie=[]
start=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    querie.append((a,b))
    if i==0:
        start=[a,b]
    
    
#どの点とどの点がつながっているかを隣接リスト型にして保管する
from collections import deque
d=deque()
e=deque()
#訪れたリスト
visited=[False for i in range(n+1)]

visited[start[0]]=True
#頂点を一つ登録
color=1
for node in edge[start[0]]:
    visited[node]=True
    d.append(node)
    colored[start[0]][node]=color
    colored[node][start[0]]=color
    before_colored[node]=color
    color+=1
while d:
    for some in d:
        if before_colored[some]!=1:
        	color=1
        else:
            color=2
        for node in edge[some]:
            if visited[node]==False:
                e.append(node)
                visited[node]=True        
                if before_colored[some]!=color:
                    colored[some][node]=color
                    colored[node][some]=color
                    before_colored[node]=color
                    color+=1
                elif before_colored[some]==color:
                    colored[some][node]=color+1
                    colored[node][some]=color+1
                    before_colored[node]=color+1
                    color+=2
        if e:
            d=e
            e=deque()
        else:
            d=deque()
K=0
for i in range(n):
    K=max(K,len(edge[i+1]))
print(K)
for  i in range(n-1):
    a,b=querie[i][0],querie[i][1]
    print(colored[a][b])

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

mmk = {}

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


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


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


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

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

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

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


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

print(max(childNodeNums))

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

Submission status: Runtime Error

Solution code:
from collections import deque


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

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


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


def dfs(currentNode, arr):
    status[currentNode] = 1
    childNodes = arr[currentNode]

    for j in childNodes:
        if status[j] == -1:
            childNodeNums[currentNode] += 1
            dfs(j, arr)

class Node:
    def __init__(self,index,parentNum):
        self.index = index
        self.parentNum = parentNum


def bfs(arr):
    while len(q) > 0:
        node = q.popleft()
        status2[node.index] = 1
        if node is not None:
            childNodes = arr[node.index]
            kk = 0
            for index, val in enumerate(childNodes):
                if status2[val] == -1:
                    kk = kk + 1
                    if kk == node.parentNum:
                        kk = kk + 1
                    print(kk)
                    q.append(Node(val,kk))


data, lens = prepare(n, arr)
dfs(0, data)
rootIndex = childNodeNums.index(max(childNodeNums))
print(max(lens))

q = deque()
q.append(Node(rootIndex,-1))
bfs(data)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

mmk = np.zeros([n+1,n+1],dtype=int)

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


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


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

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

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

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

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

print(max(childNodeNums))

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

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

mmk = np.zeros([n+1,n+1],dtype=int)

childNodeNums = np.zeros(n,dtype=int)
childNodeStatus = [-1 for i in range(n)]


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


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

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

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

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




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

print(max(childNodeNums))

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

Submission status: Runtime Error

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


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


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


def dfs(currentNode, arr):
    status[currentNode] = 1
    childNodes = arr[i]

    for j in childNodes:
        if status[j] == -1:
            childNodeNums[currentNode] += 1
            dfs(j, arr)


def dfs2(currentNode, arr, x):
    status2[currentNode] = 1
    childNodes = arr[currentNode]
    kk = 0
    for index,val in enumerate(childNodes):
        if status2[val] == -1:
            kk = kk + 1
            if kk == x:
                kk = kk + 1
            print(kk)

    kk2 = 0
    for index,val in enumerate(childNodes):
        if status2[val] == -1:
            kk2 = kk2 + 1
            if kk2 == x:
                kk2 = kk2 + 1
            dfs2(val,arr,kk2)


data,lens = prepare(n, arr)
dfs(0, data)
lastIndex = childNodeNums.index(max(childNodeNums))
print(max(lens))
dfs2(lastIndex,data,-1)

Submission status: Runtime Error

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


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


def prepare(n, arr):
    data = [[] for i in range(n)]

    for ar in arr:
        data[ar[0] - 1].append(ar[1] - 1)
        data[ar[1] - 1].append(ar[0] - 1)

    return data


def dfs(currentNode, arr):
    status[currentNode] = 1
    for i in range(n):
        childNodes = arr[i]

        for j in childNodes:
            if status[j] == -1:
                childNodeNums[i] += 1
                dfs(j, arr)


def dfs2(currentNode, arr, x):
    status2[currentNode] = 1
    childNodes = arr[currentNode]
    kk = 0
    for index,val in enumerate(childNodes):
        if status2[val] == -1:
            kk = kk + 1
            if kk == x:
                kk = kk + 1
            print(kk)

    kk2 = 0
    for index,val in enumerate(childNodes):
        if status2[val] == -1:
            kk2 = kk2 + 1
            if kk2 == x:
                kk2 = kk2 + 1
            dfs2(val,arr,kk2)


data = prepare(n, arr)
dfs(0, data)
lastIndex = childNodeNums.index(max(childNodeNums))
dfs2(lastIndex,data,-1)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

Ans = [-1] * (N-1)
def dfs(v, pc=-1, p=-1):
    c = 1
    for u, idx in E[v]:
        if (u == p):
            continue
        if (c == pc): 
            c += 1
        Ans[idx] = c
        c += 1
        dfs(u, c, v)
        
dfs(1)
print("\n".join(map(str, Ans)))

Submission status: Runtime Error

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

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


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


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

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

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

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLines[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)



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

print(max(childNodeNums))

for ar in nodeLines:
    for r in ar:
        print(r)