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:
module vector_int32_mod
    use,intrinsic :: iso_fortran_env
    type vector
        integer(int32),allocatable:: array(:)
        integer(int32):: l
    contains
        procedure :: push_back => vector_regist
    end type

    interface vector
        module procedure vector_init
    end interface
contains
    function vector_init() result(vec)
        type(vector):: vec
        allocate(vec%array(1))
        vec%l = 0
    end function

    subroutine vector_regist(vec, v)
        class(vector):: vec
        integer(int32):: v

        if (vec%l+1 > size(vec%array)) call add_(vec)
        vec%l=vec%l+1
        vec%array(vec%l) = v
    end subroutine


    subroutine add_(vec)
        type(vector):: vec
        integer(int32),allocatable:: tmp(:)
        integer(int32):: l

        l = size(vec%array)
        allocate(tmp(l))
        tmp(:) = vec%array(:)
        deallocate(vec%array)
        allocate(vec%array(l*2))
        vec%array(1:l) = tmp(:)
        deallocate(tmp)
    end subroutine
end module


module graph_mod
    use,intrinsic :: iso_fortran_env
    use vector_int32_mod
    implicit none

    type graph
        type(vector),allocatable:: n(:)
    contains
        procedure:: regist => graph_regist
        procedure:: l => graph_elem_num
        procedure:: v => graph_elem_val
    end type
    interface graph
        module procedure graph_init
    end interface
    private
    public:: graph
contains
    function graph_init(n) result(g)
        type(graph):: g
        integer(int32),intent(in):: n
        integer(int32):: i

        allocate(g%n(n))
        do i=1,n
            g%n(i) = vector()
        end do
    end function


    subroutine graph_regist(g,x,y)
        class(graph):: g
        integer(int32):: x,y

        call g%n(x)%push_back(y)
        call g%n(y)%push_back(x)
    end subroutine


    function graph_elem_num(g,i) result(ret)
        class(graph):: g
        integer(int32):: i,ret

        ret = g%n(i)%l
    end function


    function graph_elem_val(g,i,j) result(ret)
        class(graph):: g
        integer(int32):: i,j,ret

        ret = g%n(i)%array(j)
    end function
end module


program main
    use,intrinsic :: iso_fortran_env
    use vector_int32_mod
    use:: graph_mod
    implicit none
    integer(int32):: n,i
    integer(int32), allocatable:: a(:), b(:), color(:), mx
    type(graph):: g
    type(vector),allocatable:: id(:)

    read*, n
    g = graph(n)
    allocate(id(n))
    allocate(color(n))
    allocate(a(n-1), b(n-1))
    do i=1,n; id(i) = vector(); end do
    do i=1,n-1
            read*, a(i),b(i)
            call g%regist(a(i),b(i))
            call id(a(i))%push_back(i)
            call id(b(i))%push_back(i)
    end do

    call dfs(1,0,0)
    mx=0
    do i=1,n; mx = max(mx,g%l(i)); end do
    print'(i0)', mx
    do i=1,n-1; print'(i0)', color(i); end do

contains
    recursive subroutine dfs(self, from, c)
        integer(int32):: i,self,from,c,k
        k=1
        do i=1,g%l(self)
            block; integer(int32):: u, ei
            if (k==c) k=k+1
            u = g%v(self,i)
            if (u == from) cycle
            ei = id(self)%array(i)
            color(ei) = k; k=k+1
            call dfs(u, self, color(ei))
        end block; end do
    end subroutine
end program main

Submission status: Runtime Error

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

k = max([len(i) for i in g])
print(k)

c = [[-1]*n for i in range(n)]
from collections import deque
q = deque([(0,-1)])

while q:
    cur,col = q.popleft()
    for next_i in g[cur]:
        if c[cur][next_i]<0:
            col = (col+1)%k
            c[cur][next_i] = col
            c[next_i][cur] = col
            q.append((next_i,col))


for a,b in ab:
    print(c[a][b]+1)

Submission status: Runtime Error

Solution code:
from collections import deque

n=int(input())
g=[[] for i in range(n)]
b=[0]*(n-1)
for i in range(n-1):
    ai,bi=map(int,input().split())
    g[ai-1].append(bi-1)
    g[bi-1].append(ai-1)
    b[i]=bi-1
    
#n=8
#g=[[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
#n=6
#g=[[1, 2, 3, 4, 5], [0], [0], [0], [0], [0]]

q=deque([0])

stack=[0]
parent=[-1]*n
pc=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
    ic=0
    for v in g[state]:
        if parent[v] !=-1:
            continue
        else:
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            ic+=1
            if ic==pc[state]:
                ic+=1
            pc[v]=ic

k=max(pc)
print(k)
for i in range(1,n):
    print(pc[bi[i]])

Submission status: Runtime Error

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

graph = [[] for _ in range(n+1)]
ans = [0]*(n-1)
for i in range(n-1):
    graph[ab[i][0]].append((ab[i][1],i))
    graph[ab[i][1]].append((ab[i][0],i))

visit = [False]*(n+1)
def dfs(p,c):
    color = 1
    visit[p] = True
    for n,i in graph[p]:
        if visit[n] == False:
            if color == c:
                color += 1
            ans[i] = color
            dfs(n,color)
            color += 1

dfs(1,0)
print(max(ans))
for t in ans:
    print(t)

Submission status: Runtime Error

Solution code:
def dfs(s, to, color, palette, i=0):
    seen[s] = 1
    for v in to[s]:
        if seen[v]:
            continue
        if s < v:
            color[sides.index([s, v])] = palette[i % len(palette)]
            i += 1
        dfs(v, to, color, palette, i)


N = int(input())
sides = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N - 1)]
to = [[] for _ in range(N)]
for a, b in sides:
    to[a].append(b)
    to[b].append(a)

colors_used = max(len(sub) for sub in to)
palette = [i for i in range(1, colors_used+1)]
seen = [0] * N
color = [0] * (N - 1)

dfs(0, to, color, palette)

print(colors_used)
print(*color, sep='\n')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u)

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int>G[N];
int vis[N],color[N],n,u,v,mx=0,s;
struct node{
    int u,v;
};
vector<node>edge;
map<pair<int,int>,int>m;
void bfs(int s){
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        int c=1;
        for(auto v:G[u]){
            if(!vis[v]){
                q.push(v);
                if(c==color[u]) (c==mx-1)?c=mx:(c=(c+1)%mx);
                color[v]=c;
                //cout<<v<<c<<endl;
                m[{min(u,v),max(u,v)}]=c;
                (c==mx-1)?c=mx:(c=(c+1)%mx);
                vis[v]=1;
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>u>>v;
        edge.push_back({u,v});
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(G[i].size()>mx){
            mx=G[i].size();
            s=i;
        }
    }
    //cout<<s<<mx<<endl;
    bfs(s);
    color[s]=0;
    cout<<G[s].size()<<endl;
    for(auto i:edge) cout<<m[{min(i.u,i.v),max(i.u,i.v)}]<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:

from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      prev_col[i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)

Submission status: Runtime Error

Solution code:
def abc146_d():
    n = int(input())
    Q = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]

    deg = [0] * n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1: nouse = color[(min(s, p), max(s, p))]
        c = 1
        for t in adj[s]:
            if t == p: continue
            if c == nouse: c += 1
            color[(min(s, t), max(s, t))] = c
            dfs(t, s)
            c += 1

    dfs(1, -1)

    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

if __name__ == '__main__':
    abc146_d()

Submission status: Runtime Error

Solution code:
n = int(input())
sides = []
data = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
kinds = -1
for i in range(n):
    kinds = max(kinds,len(data[i]))
print(kinds)
strage = [[i for i in range(1,kinds+1)] for i in range(n)]
for i,j in sides:
    p = strage[i].pop()
    q = strage[j].pop()
    if p == q:
        print(p)
    elif p > q:
        print(q)
        strage[i].remove(q)
        strage.append(p)
    else:
        print(p)
        strage[j].remove(p)
        strage.append(q)

Submission status: Runtime Error

Solution code:
n = int(input())

a = [set() for i in range(n)]

for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  if i == 0:
    s = b
  a[b].add(c)
  a[c].add(b)

col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True

def dfs(s,k):
  visited[s] = True
  col[s] = k
  j = 1
  for i in a[s]:
    if visited[i] == False:
      if col[s] == j:
        j += 1
      dfs(i,j)
      j += 1

dfs(0,0)

print (max(col))
for i in col[1:]:
  print (i)

Submission status: Runtime Error

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


def solve(N: int, a: "List[int]", b: "List[int]"):
    from itertools import count
    edges = [[] for _ in range(N)]
    for i, (aa, bb) in enumerate(zip(a, b)):
        edges[aa-1].append((bb-1, i))
        edges[bb-1].append((aa-1, i))
    ans = [None] * (N-1)
    visited = set()
    def dfs(n, c):
        if n in visited:
            return
        visited.add(n)
        for (nn, i), cc in zip(filter(lambda x: x[0] not in visited, edges[n]),
                          filter(lambda y: y != c, count(1))):
            ans[i] = cc
            dfs(nn, cc)
    dfs(0, None)
    return [max(ans)] + ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(N, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

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

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
K = -1

for x in order:
    temp = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == temp:
            c += 1
        color[y] = c
        K = max(K, c)
        c += 1

ans = []

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

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

Submission status: Runtime Error

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

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

print(max(color))
for i in e:
    print(color[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
ab = [list(map(lambda x:int(x)-1,input().split()))for i in range(n-1)]
count = [0]*n
for i in range(n-1):
    count[ab[i][0]] += 1
    count[ab[i][1]] += 1
aset = {i for i in range(1,max(count)+1)}
edge = [set() for i in range(n)]
anslist = []
for i in range(n-1):
    now = min(aset-(edge[ab[i][0]]|edge[ab[i][1]]))
    edge[ab[i][0]].add(now)
    edge[ab[i][1]].add(now)
    anslist.append(now)
print(max(count))
for ans in anslist:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
ab = [list(map(lambda x:int(x)-1,input().split()))for i in range(n-1)]
count = [0]*n
for i in range(n-1):
    count[ab[i][0]] += 1
    count[ab[i][1]] += 1
print(max(count))
aset = {i for i in range(1,max(count)+1)}
edge = [{i for i in range(1,max(count)+1)} for i in range(n)]
anslist = []
for i in range(n-1):
    now = min(edge[ab[i][0]]&edge[ab[i][1]])
    edge[ab[i][0]].remove(now)
    edge[ab[i][1]].remove(now)
    anslist.append(now)
for ans in anslist:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
ab = [list(map(lambda x:int(x)-1,input().split()))for i in range(n-1)]
count = [0]*n
for i in range(n-1):
    count[ab[i][0]] += 1
    count[ab[i][1]] += 1
print(max(count))
edge = [[i for i in range(1,max(count)+1)] for i in range(n)]
anslist = []
for i in range(n-1):
    a = 0
    b = 0
    while True:
        if edge[ab[i][0]][a] == edge[ab[i][1]][b]:
            anslist.append(edge[ab[i][0]][a])
            edge[ab[i][0]].pop(a)
            edge[ab[i][1]].pop(b)
            break
        if edge[ab[i][0]][a] > edge[ab[i][1]][b]:
            b += 1
        else:
            a += 1

for ans in anslist:
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
lst_n = [[]] * n
lst_ab = []
for i in range(n - 1):
	a, b = [int(j) - 1 for j in input().split()]
	lst_ab.append((a, b))
	if lst_n[a]:
		lst_n[a].append(b)
	else:
		lst_n[a] = [b]
	if lst_n[b]:
		lst_n[b][2].append(a)
	else:
		lst_n[b] = [a]
n_lst_max = max([len(l) for l in lst_n])
lst_color = [[] for i in range(n_lst_max)]
print(n_lst_max)
for ab in lst_ab:
	for i, color in enumerate(lst_color):
		if not ab[0] in color and not ab[1] in color:
			lst_color[i].append(ab[0])
			lst_color[i].append(ab[1])
			print(i + 1)
			break

Submission status: Runtime Error

Solution code:
# 昔同じ問題を atcoder で見た？
n = int(input())
edges = []
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# print(edges)
# print(paths)
colors = {}  # (a->b) 1 とか
current = 1
biggest = 1
def f(current, prev, prev_color):
    global biggest
    color = 0
    for vertex in paths[current]:
        if vertex == prev:
            continue
        color += 1
        if color == prev_color:
            color += 1
        biggest = max(biggest, color)
        colors[(current, vertex)] = color
        f(vertex, current, color)
f(1, None, None)

print(biggest)
for a, b in edges:
    print(colors[(a, b)])

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import deque
        
n = int(input())
uf = UnionFind(n)
g = [[] for i in range(n)]
cnt = [0] * n
ans = [[0] * n for i in range(n)]
ans_index = []

for i in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    uf.union(a, b)
    g[a].append(b)
    g[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
    ans_index.append((a, b))
    

for i in uf.roots():
    visited = [0] * n
    visited[i] = 1
    que = deque()
    que.append([i, 0])
    while que:
        s = que.popleft()
        k = 0
        for j in g[s[0]]:
            if not visited[j]:
                while True:
                    k += 1
                    if k != s[1]:
                        que.append([j, k])
                        visited[j] = 1
                        ans[s[0]][j] = k
                        ans[j][s[0]] = k
                        break

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

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import deque
        
n = int(input())
uf = UnionFind(n)
g = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * (n - 1)
ans_index = []

for i in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    uf.union(a, b)
    g[a].append(b)
    g[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
    ans_index.append((a, b))
    

for i in uf.roots():
    visited = [0] * n
    visited[i] = 1
    que = deque()
    que.append([i, 0])
    while que:
        s = que.popleft()
        k = 0
        for j in g[s[0]]:
            if not visited[j]:
                while True:
                    k += 1
                    if k != s[1]:
                        que.append([j, k])
                        visited[j] = 1
                        ans[ans_index.index((s[0], j))] = k
                        break

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

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = [0] * n
ok = [[0] * (n - 1) for i in range(n)]
ans = []
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    for j in range(n):
        if not ok[a][j] and not ok[b][j]:
            ans.append(j + 1)
            ok[a][j] = 1
            ok[b][j] = 1
            break
    cnt[a] += 1
    cnt[b] += 1
    
print(max(cnt))
print(*ans, sep = "\n")

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = [0] * n
ok = [[0] * (n - 1) for i in range(n)]
ans = []
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    for j in range(n - 1):
        if not ok[a][j] and not ok[b][j]:
            ans.append(j + 1)
            ok[a][j] = 1
            ok[b][j] = 1
            break
    cnt[a] += 1
    cnt[b] += 1
    
print(max(cnt))
print(*ans, sep = "\n")

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

ans = [0] * (n - 1)

q = deque([[1, 0, 0]])a

while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node:
            continue
        if cnt == pcol:
            cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1

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

Submission status: Runtime Error

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


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

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

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

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

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

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


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

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

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

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

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

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


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


class Edge:
    def __init__(self, to_, id_):
        self.to = to_
        self.id = id_


ans = None
G = None
K = None


def dfs(to, c):
    global G
    global ans
    nc = c % K + 1
    for g in G[to]:
        if ans[g.id] != -1:
            continue
        ans[g.id] = nc
        dfs(g.to, nc)
        nc = nc % K + 1


def solve():
    global G
    global ans
    global K
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = Scanner.map_int()
        x -= 1
        y -= 1
        G[x].append(Edge(y, i))
        G[y].append(Edge(x, i))
    K = 0
    for i in range(N):
        K = max(K, len(G[i]))

    ans = [-1 for _ in range(N - 1)]
    dfs(0, 0)
    print(K)
    print(*ans, sep='\n')


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

graph = defaultdict(list)

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

max_c = max([len(x) for x in list(graph.values())])

colors = set(range(1, max_c + 1))


q = deque([1])
ans = [0] * (n + 1)
ans[1] = 1

while q:
    curr = q.popleft()
    can_use = colors - set([ans[curr]])
    for v in graph[curr]:
        if ans[v] == 0:
            ans[v] = min(can_use)
            can_use -= set([min(can_use)])
            q.append(v)

print(*ans[1:], sep="\n")

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
route = [[] for _ in range(N)]
num = np.zeros((N, N), dtype = int)
for i in range(N - 1):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    num[a-1][b-1] = i
    num[b-1][a-1] = i
ans = len(max(route, key = lambda x: len(x)))
colors = {i for i in range(1, ans+1)}
ANS = [0 for i in range(N-1)]
check = [(0, -1, -1)]#now,from, col
while check:
    now, From, col = check.pop()
    precol = list(colors - {col})
    count = 0
    for Next in route[now]:
        if Next == From:
            continue
        else:
            ANS[num[now][Next]] = f'{precol[count]}'
            check.append((Next, now, precol[count]))
            count += 1
print(ans)
print('\n'.join(ANS))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
route = [[] for _ in range(N)]
num = np.zeros((N, N), dtype = int)
for i in range(N - 1):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    num[a-1][b-1] = i
    num[b-1][a-1] = i
ans = len(max(route, key = lambda x: len(x)))
colors = {i for i in range(1, ans+1)}
ANS = ['0' for i in range(N-1)]
check = [(0, -1, -1)]#now,from, col
while check:
    now, From, col = check.pop()
    precol = list(colors - {col})
    count = 0
    for Next in route[now]:
        if Next == From:
            pass
        else:
            ANS[num[now][Next]] = precol[count]
            check.append((Next, now, precol[count]))
            count += 1
print(ans)
print('\n'.join(list(map(str,ANS))))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
route = [[] for _ in range(N)]
num = np.zeros((N, N), dtype = int)
for i in range(N - 1):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    num[a-1][b-1] = i
    num[b-1][a-1] = i
ans = len(max(route, key = lambda x: len(x)))
colors = {i for i in range(1, ans+1)}
ANS = ['0' for i in range(N-1)]
check = [(0, -1, -1)]#now,from, col
while check:
    now, From, col = check.pop()
    precol = list(colors - {col})
    count = 0
    for Next in route[now]:
        if Next == From:
            pass
        else:
            ANS[num[now][Next]] = f'{precol[count]}'
            check.append((Next, now, precol[count]))
            count += 1
print(ans)
print('\n'.join(ANS))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
route = [[] for _ in range(N)]
num = np.zeros((N, N), dtype = int)
for i in range(N - 1):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    num[a-1][b-1] = i
    num[b-1][a-1] = i
ans = len(max(route, key = lambda x: len(x)))
colors = {i for i in range(1, ans+1)}
ANS = [0 for i in range(N-1)]
check = [(0, -1, -1)]#now,from, col
while check:
    now, From, col = check.pop()
    precol = list(colors - {col})
    count = 0
    for Next in route[now]:
        if Next == From:
            pass
        else:
            ANS[num[now][Next]] = f'{precol[count]}'
            check.append((Next, now, precol[count]))
            count += 1
print(ans)
print('\n'.join(ANS))