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:
N = int(input())
edges = []
count = [0 for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = max(count)

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

for k, [i,j] in enumerate(edges):
  for l in range(MAX):
    c = l+1
    if c in used[i-1] or c in used[j-1]:
      continue
    used[i-1].add(c)
    used[j-1].add(c)
    color[k] = c
    break

print(MAX)
for i in color:
  if i == 0:
    print(input())
  print(i)

Submission status: Runtime Error

Solution code:
#input
N = int(input())
A = []
B = []
for i in range(N-1):
    p, q = map(int, input().split())
    A.append(p)
    B.append(q)

#output
from itertools import chain
C = [[]]*(N-1)
#便宜的に頂点から-1しておく。
for a in A:
    C[a-1] = [b-1 for i, b in enumerate(B) if A[i] == a]

D = [len(c) for i, c in enumerate(C)]

K = 0
for i in range(len(D)-1):
    temp = D[i] + D[i-1]
    K = max(temp, K)

E = [[]]*(N-1)
for a in A:
    E[a-1] = [(b-1) % K for i, b in enumerate(B) if A[i] == a]

F = list(chain.from_iterable(E))
F = [f if f > 0 else K for f in F]

print(K)
for f in F:
    print(f)

Submission status: Runtime Error

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

ans = [None] * (N-1)

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

Submission status: Runtime Error

Solution code:
N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)

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

Submission status: Runtime Error

Solution code:
N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)
def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
#        print('vertices=',v)
#        print('child=',child)
#        print('parent=',p)
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)
        

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

Submission status: Runtime Error

Solution code:
N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)
def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
#        print('vertices=',v)
#        print('child=',child)
#        print('parent=',p)
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        dfs(child,v,c)
        c+=1

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

Submission status: Runtime Error

Solution code:
# coding: utf-8


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

    link = {}
    edge = []

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

        if b in link:
            link[b].append(a)
        else:
            link[b] = [a]

    n_color = len(max(link.items(), key=lambda x: len(x[1]))[1])

    color = {}
    seek(1, 0, color, link)

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


def seek(i: int, parent: int, color: dict, link: dict):
    c = 1
    inlet = tuple(sorted((i, parent)))
    for node in link[i]:
        if node == parent:
            continue

        if 0 < parent and c == color[inlet]:
            c += 1
        color[tuple(sorted((i, node)))] = c
        c += 1
        seek(node, i, color, link)


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

Submission status: Runtime Error

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

for edge in range(1,N):
    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette[:]
    if parent > 0:
        del current_palette[current_palette.index(colors[parent])]
    for edge in edges[root]:
        if edge == parent:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette[0]
            del current_palette[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

color_edges(0, 1)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Submission status: Runtime Error

Solution code:
# coding: utf-8


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

    link = {}
    for ab in args[1:]:
        a, b = map(int, ab.split())
        if a in link:
            link[a].append(b)
        else:
            link[a] = [b]
        if b in link:
            link[b].append(a)
        else:
            link[b] = [a]

    n_color = len(max(link.items(), key=lambda x: len(x[1]))[1])

    color = [0]*n

    color[0] = 1
    seek(1, 0, color, link)

    return str(n_color) + '\n' + '\n'.join(map(str, color[:-1]))


def seek(i: int, parent: int, color: list, link: dict):
    c = 1
    for node in link[i]:
        if node == parent:
            continue

        if c == color[i-1]:
            c += 1
        color[node-1] = c
        c += 1
        seek(node, i, color, link)


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

Submission status: Runtime Error

Solution code:
# coding: utf-8


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

    link = {}
    for ab in args[1:]:
        a, b = map(int, ab.split())
        if a in link:
            link[a].append(b)
        else:
            link[a] = [b]
        if b in link:
            link[b].append(a)
        else:
            link[b] = [a]

    color = [0]*n

    color[0] = 1
    seek(1, 0, color, link)

    return '\n'.join(map(str, color))


def seek(i: int, parent: int, color: list, link: dict):
    c = 1
    for node in link[i]:
        if node == parent:
            continue

        if c == color[i-1]:
            c += 1
        color[node-1] = c
        c += 1
        seek(node, i, color, link)


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

Submission status: Runtime Error

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)


def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
    for i in ends[root]:
        if i == parent:
            continue
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

color_edges(0, 1)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

root = [node for node in ends if len(ends[node]) > 1][0]

def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

"""
for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color
"""

color_edges(0, root)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Runtime Error

Solution code:
def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(range(1,k+1))
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
print(solve(n, a, b))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
count = 0
f0,f1 = -1,-1
for ans in range(1000):
  f0,f1 = -1,-1
  ans_str = "{0:03d}".format(ans)
  for i in range(n):
    if s[i] == ans_str[0]:
      f0 = i
      break
  if f0 == -1:
    continue
  for j in range(f0+1,n):
    if s[j] == ans_str[1]:
      f1 = j
      break
  if f1 == -1:
    continue
  for k in range(f1+1,n):
    if s[k] == ans_str[2]:
      count += 1
      break

print(count)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<bits/stdc++.h>
#include<map> 
using namespace std;

int main()
{
  int n;
  cin>>n;
  vector<int> deg(n+1);
  vector<vector<int> > adj(n+1);
  map<pair<int,int>,int> m;
  int maxd=0,a,b;
  vector<int> color(n);
  for(int i=0;i<n;i++){color[i]=0;}
  for(int i=0;i<n-1;i++)
  {
    cin>>a>>b;
    adj[a].push_back(b);
    deg[a]++;
    deg[b]++;
    m[{a,b}]=i+1;
    maxd=max(maxd,max(deg[a],deg[b]));
  }
  deg.clear();
  vector<int> v(maxd);
  for(int i=0;i<maxd;i++)
    v[i]=i+1;
  vector<vector<int> > available(n+1,v);
  for(int i=1;i<adj.size();i++)
  {
    for(int j:adj[i])
    {
      color[m[{i,j}]]=available[i][0];
      auto position=find(available[j].begin(),available[j].end(),available[i][0]);
      if(position!=available[j].end())
        available[j].erase(position);
      available[i].erase(available[i].begin());
    }
  }
  cout<<maxd<<endl;
  for(int i=1;i<color.size();i++)
    if(i==color.size()-1)
    	cout<<color[i]<<" ";
    else
      cout<<color[i]<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<bits/stdc++.h>
#include<map> 
#include<iterator>
using namespace std;

int main()
{
  int n;
  cin>>n;
  vector<int> deg(n+1);
  vector<vector<int> > adj(n+1);
  map<pair<int,int>,int> m;
  int maxd=0,a,b;
  vector<int> color(n);
  for(int i=0;i<n;i++){color[i]=0;}
  for(int i=0;i<n-1;i++)
  {
    cin>>a>>b;
    adj[a].push_back(b);
    deg[a]++;
    deg[b]++;
    m[{a,b}]=i+1;
    maxd=max(maxd,max(deg[a],deg[b]));
  }
  deg.clear();
  vector<int> v(maxd);
  for(int i=0;i<maxd;i++)
    v[i]=i+1;
  vector<vector<int> > available(n+1,v);
  for(int i=1;i<adj.size();i++)
  {
    for(int j:adj[i])
    {
      color[m[{i,j}]]=available[i][0];
      auto position=find(available[j].begin(),available[j].end(),available[i][0]);
      if(position!=available[j].end())
        available[j].erase(position);
      available[i].erase(available[i].begin());
    }
  }
  cout<<maxd<<endl;
  for(int i=1;i<color.size();i++)
    cout<<color[i]<<endl;
  
  return 0;
}

Submission status: Runtime Error

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	maxd=0
	edges=[0]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		edges.append(0)
		dic[(a,b)]=i+1
		if(maxd<len(adj[a])):
			maxd=len(adj[a])
			indx=a
		if(maxd<len(adj[b])):
			maxd=len(adj[b])
			indx=b
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	for i in range(1,n+1):
		for j in adj[i]:
			if (i,j) in dic:
				if(edges[dic[(i,j)]]==0):
					edges[dic[(i,j)]]=available[i][0]
					available[j].remove(available[i][0])
					available[i].pop(0)
					
			if (j,i) in dic:
				if(edges[dic[(j,i)]]==0):
					edges[dic[(j,i)]]=available[j][0]
					available[i].remove(available[j][0])
					available[j].pop(0)
	print(maxd)
	for i in range(1,len(edges)):
		if i==len(edges)-1:
			print(edges[i],end="")
		else:
			print(edges[i])	

main()

Submission status: Runtime Error

Solution code:
import queue
n = int(raw_input())
edges = []
for i in range(n - 1):
    edges.append(map(int, raw_input().split()))
edge_num = {}
G = [[] for i in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = queue.Queue(n)
q.put(0)
vis.add(0)
while q.qsize() > 0:
    u = q.get()
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            vis.add(v)
            q.put(v)
    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1
print len(set(ans))
for i in ans:
    print i

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(raw_input())
edges = []
for i in range(n - 1):
    edges.append(map(int, raw_input().split()))
edge_num = {}
G = [[] for i in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = deque([0])
vis.add(u)
while q:
    u = q.popleft()
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            vis.add(v)
            q.append(v)
    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1
print len(set(ans))
for i in ans:
    print i

Submission status: Runtime Error

Solution code:
import queue
n = int(raw_input())
edges = []
for i in range(n - 1):
    edges.append(map(int, raw_input().split()))
edge_num = {}
G = [[] for i in range(n + 1)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = queue.Queue(n)
vis.add(u)
q.put(0)
while q.qsize() > 0:
    u = q.get()
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            vis.add(v)
            q.put(v)
    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1
print len(set(ans))
for i in ans:
    print i

Submission status: Runtime Error

Solution code:
import queue
n = int(raw_input())
edges = []
for i in range(n - 1):
    edges.append(map(int, raw_input().split()))
edge_num = {}
G = [[] for i in range(n + 1)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = queue.Queue(n)
q.put(0)
while q.qsize() > 0:
    u = q.get()
    vis.add(u)
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            q.put(v)
    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1
print ans
print len(set(ans))
for i in ans:
    print i

Submission status: Runtime Error

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

ans = [None]*(N-1)
def dfs(cur, p_color, p=-1):
    color = 1
    for (to, i) in graph[cur]:
        if to == p: continue
        if color == p_color:
            color = color+1
        ans[i] = color
        dfs(to, color, p=cur)
        color = color+1

dfs(0, -1)
print(max(ans))
[print(a) for a in ans]

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)

colors = [0 for _ in range(N)]
visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    if node < ner:
      colors[ner] = c
    else:
      colors[node] = c
    dfs(ner, c)

dfs(0, 0)
for i in range(1, N):
  print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)

colors = [0 for _ in range(N)]
visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    colors[ner] = c
    dfs(ner, c)

dfs(0, 0)
for i in range(1, N):
  print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)
# print(edges)

edgesM = {}
visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    edgesM[(node, ner)] = c
    dfs(ner, c)

dfs(0, 0)
#print(edgesM)
for e in edges:
  print(edgesM[(e)])

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)
# print(edges)

edgesM = {}
visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    if node <= ner:
      edgesM[(node, ner)] = c
    else:
      edgesM[(ner, node)] = c
    dfs(ner, c)

dfs(0, 0)
#print(edgesM)
for e in edges:
  print(edgesM[(e[0], e[1])])

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)
# print(edges)

edgesM = {}
visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    if node <= ner:
      edgesM[(node, ner)] = c
    else:
      edgesM[(ner, node)] = c
  c2 = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c2 += 1
    if c2 == color:
      c2 += 1
    dfs(ner, c2)

dfs(0, 0)
#print(edgesM)
for e in edges:
  print(edgesM[(e[0], e[1])])

Submission status: Runtime Error

Solution code:
N = int(input())

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

k = 0
for i in g:
  k = max(len(i), k)
print(k)

visited = [False for _ in range(N)]
def dfs(node, color):
  visited[node] = True
  c = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c += 1
    if c == color:
      c += 1
    print(c)
  c2 = 0
  for ner in g[node]:
    if visited[ner]:
      continue
    c2 += 1
    if c2 == color:
      c2 += 1
    dfs(ner, c2)

dfs(0, 0)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import numpy as np

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2)

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    parent = np.zeros(n + 1, dtype=np.int64)
    color = np.zeros((n + 1, n + 1), dtype=np.int64)
    root = 1
    ng = None
    q = deque()
    q.append((root, ng))

    while q:
        x, ng = q.popleft()
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[x][y] = c
            color[y][x] = c
            q.append((y, c))
            c += 1

    print(np.amax(color))
    for a, b in ab:
        print(color[a][b])
            
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import numpy as np

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = np.array(sys.stdin.read().split(), dtype=np.int32).reshape(-1, 2)

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    parent = np.zeros(n + 1, dtype=np.int32)
    color = np.zeros((n + 1, n + 1), dtype=np.int32)
    root = 1
    ng = None
    q = deque()
    q.append((root, ng))

    while q:
        x, ng = q.popleft()
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[x][y] = c
            color[y][x] = c
            q.append((y, c))
            c += 1

    print(np.amax(color))
    for a, b in ab:
        print(color[a][b])
            
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
import numpy as np
children = ddict(list)
parents = ddict(list)
for ab in AB:
    children[ab[0]].append(ab[1])
    parents[ab[1]].append(ab[0])
ans = []
ans_trans = ddict(int)
for i in range(N-1):
    used = set()
    # 親チェック
    if parents[AB[i][0]] != []:
        used.add(ans_trans[str(parents[AB[i][0]][0]) + "-" + str(AB[i][0])])
    # 子チェック
    for child in children[AB[i][1]]:
        used.add(ans_trans[str(AB[i][1])+"-"+str(child)])
    # 兄弟チェック
    for child in children[AB[i][0]]:
        used.add(ans_trans[str(AB[i][0])+"-"+str(child)])
    ans.append(min(set(range(1,max(used)+2)) - used))
    ans_trans[str(AB[i][0]) + "-" + str(AB[i][1])] = ans[-1]
print(max(ans))
for a in ans:
    print(a)

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):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  for y, i in e[x]:
    if i in vis:
      while t in viss:
        t += 1
      continue
    vis.add(i)
    res[i] = t
    t += 1
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)

Submission status: Runtime Error

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

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

#BFS
colors = {}
colors[(0,1)] = 0
color_parent = 0
k = 0
i = 0
queue = [0]
visited = [0]*n
while queue:
    v = queue.pop(0)
    visited[v] = 1
    color = 0

    color_parent = colors[(v, es[v][0])]

    for to in es[v]:
        if visited[to]: continue
        queue.append(to)

        if color == color_parent and v != 0:
            color += 1

        colors[(v,to)] = color
        colors[(to,v)] = color


        k = max(k, color)
        color += 1

print(k+1)

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

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
for i in range(n-1): #因数注意！
    M = input()    
    m = M.split()
    p = [int(i) for i in m] #1列の数列をリスト化
    p = p + [i]
    list.append(p) #list(行列)
color = [0 for i in range(n-1)] #各辺の色
maxcolor = 1
N = deque([[1,0]]) #頂点と使用されている色
delete = deque() #listから探索済みの辺を削除する
while len(list) != 0:
    a = N.popleft()
    b = 0
        for i, value in enumerate(list):
            if value[0] == a[0]:
                b = b + 1
                if b == a[1]:
                    b = b + 1
                N.append([value[1],b])
                color[value[2]] = b
                delete.append(i)
                if maxcolor < b:
                    maxcolor = b
            elif value[1] == a[0]:
                b = b + 1
                if b == a[1]:
                    b = b + 1
                N.append([value[0],b])
                color[value[2]] = b
                delete.append(i)
                if maxcolor < b:
                    maxcolor = b
        else:
            c = 0
            while len(delete) != 0:
                c = c + 1
                d = delete.popleft()
                del list[d-c+1]
print(maxcolor)
for i in color:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10000)
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])