Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def main():
    n = int(input())
    color = [None]*(n-1)
    color[0] = -1

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

    def dfs(now=0, prev=-1, mycolor=-1):
        in_use = {mycolor}
        i = 0

        for tup in con[now]:
            if tup[0] != prev:
                while i < 1000:
                    if i not in in_use:
                        color[tup[1]] = i
                        in_use.add(i)
                        break
                    i += 1
                dfs(tup[0], now, i)

    dfs()

    print(max(color)+1)
    for i in color:
        print(i+1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())

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

def search(par, ans, own):
    ans =  max(ans, len(ki[own]))
    for child in ki[own]:
        if child == par:
            continue
        else:
            ans = max(search(own, ans, child),ans)
    return ans

print(search(-1, 0, 0))


def search(par, ans, own, par_num):
    ans =  max(ans, len(ki[own]))
    i = 1
    for child in ki[own]:
        if child == par:
            continue
        else:
            if i == par_num:
                i += 1
            print(i)
            ans = max(search(own, ans, child, i),ans)
            i += 1
    return ans

search(-1, 0, 0, -1)

Submission status: Runtime Error

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

ans = [None]*(n-1)
def rec(cur,color):

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

Submission status: Runtime Error

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = {}

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
        if i != parent:
            if color == used_color:
                color += 1
            abmap[(i,num)] = color
            abmap[(num,i)] = color
            coloring(i,num,color)
            color += 1

coloring(1,0,0)

for i in ab:
    print(abmap[i])

Submission status: Runtime Error

Solution code:
n = int(input())
s = [{0} for i in range(n)]

ans = [0] * n
a = 0
b = 0
sp = {i for i in range(1000)}
for i in range(1,n):
    a,b = list(map(int,input().split()))
    ans[i] = min(sp-(s[a-1]|s[b-1]))

    s[a-1].add(ans[i])
    s[b-1].add(ans[i])

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = [{0} for i in range(n)]

ans = [0] * n
a = 0
b = 0
sp = {i for i in range(100)}
for i in range(1,n):
    a,b = list(map(int,input().split()))
    ans[i] = min(sp-(s[a-1]|s[b-1]))

    s[a-1].add(ans[i])
    s[b-1].add(ans[i])

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = [{i for i in range(1,100)}for j in range(n)]

ans = [0] * n
a = 0
b = 0

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

    s[a-1].remove(ans[i])
    s[b-1].remove(ans[i])

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

Submission status: Runtime Error

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
            if color == used_color:
                color += 1
            abmap[num][i] = color
            abmap[i][num] = color
            coloring(i,num,color)
            color += 1
            print(i,color)

coloring(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Runtime Error

Solution code:
def func(iro,tree,num,max_color):
  if num not in tree:
    return
  
  my_color = iro[num]
  arr = tree[num]
  
  for i in arr:
    my_color += 1
    iro[i] = my_color % max_color
    func(iro,tree,i,max_color)
    

n = int(input())
tree = {}

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

tree = sorted(tree.items())
  
color = len(tree[1])
for key in tree.keys():
  if key == 1:
    continue
    
  arr = tree[key]
  color = max(len(arr)+1, color)

print(color)

iro = [-1] * (n+1)

for key in tree.keys():
  my_color = iro[key]
  arr = tree[key]
  for i in arr:
    my_color += 1
    iro[i] = my_color % color

for i in b_arr:
  print(iro[i]+1)

Submission status: Runtime Error

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    a = 0
    for i in range(1,n+1):
        a = max(a,len(tree[i]))
    return a

print(maxdegree(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def coloring(self_num,parent,used_color):
    global tree
    global abmap
    num = self_num
    color = 1
    nodes = tree[num]
    for i in nodes:
        if i != parent
            if color == used_color:
                color += 1
            abmap[num][i] = color
            abmap[i][num] = color
            coloring(i,num,color)
            color += 1

coloring(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
e=[[] for _ in range(n)]
a=[0]*n
b=[0]*n
d={}
def dfs(x,last=-1,ban=-1):
    c=1
    for to in e[x]:
        if to==last:
            continue
        if c==ban:
            c+=1
        d[(x,to)]=c
        dfs(to,x,c)
        c+=1

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

dfs(0)
print(max(d.values()))
for i in range(n-1):
    if (a[i],b[i]) in d:
        print(d[(a[i],b[i])])
    else:
        print(d[(b[i],a[i])])

Submission status: Runtime Error

Solution code:
N = int(input())

edges = [[] for _ in range(N)]

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

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

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

Submission status: Runtime Error

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

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[0]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]==0:
            if j==viisted[v]:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.appendleft(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())

edges = [[] for _ in range(N)]

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

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    edge_index = []
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(1, -1)

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N = int(input())

graph = [[] for i in range(N)]

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

ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

print(max(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())
    graph[a-1].append((b, i))
    graph[b-1].append((a, i))

print(graph)
ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

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

Submission status: Runtime Error

Solution code:
A,B,X = input().split()
A,B,X = int(A),int(B),int(X)
import math

def keta(N):
    return len(str(N))

def val(N):
        return A*N+B*keta(N)

s = (X-B)//A+1
kouho = [i for i in range(s)]
while(len(kouho)<=2):
    s = len(kouho)
    
    val_ = val(kouho[s//2])
    if(val>X):
        kouho = kouho[:s//2]
    else:
        kouho = kouho[s//2:]   
        
max_ = 0
for i in range(len(kouho)):
    val_ = val(kouho[i])
    if(val_<=X):
        max_ = max([max_,kouho[i]])

        
print(max_)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N+1)]
for i in range(N-1):
    a_,b_ = input().split()
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
import numpy as np
import random
color_map = np.zeros((N+1,K))
print(K)
for i in range(N-1):
    a_ = a[i]
    b_ = b[i]
    for t in range(K):
        k = random.randint(0,K-1)
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            print(k+1)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N+1)]
for i in range(N-1):
    a_,b_ = input().split()
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
import numpy as np
color_map = np.zeros((N+1,K))
print(K)
for i in range(N-1):
    a_ = a[i]
    b_ = b[i]
    for k in range(K):
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            print(k+1)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N+1)]
for i in range(N-1):
    a_,b_ = input().split()
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
import numpy as np
color_map = np.zeros((N+1,K))
print(K)
for i in range(N-1):
    a_ = a[i]
    b_ = b[i]
    for k in range(K):
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            print(k)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N)]
for i in range(N-1):
    a_,b_ = input().split()
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
import numpy as np
color_map = np.zeros((N,K))
print(K)
for i in range(N):
    a_ = a[i]
    b_ = b[i]
    for k in range(K):
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            print(k)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

Solution code:
N = int(input())
a,b = [],[]
color = [0 for i in range(N+1)]
for i in range(N):
    a_,b_ = input().split()
    a_,b_ = int(a_),int(b_)
    a.append(a_)
    b.append(b_)
    
    color[a_] += 1
    color[b_] += 1
    
K = max(color)
import numpy as np
color_map = np.zeros((N,K))
print(K)
for i in range(N):
    a_ = a[i]
    b_ = b[i]
    for k in range(K):
        if(color_map[a_][k]==0 and color_map[b_][k]==0):
            print(k)
            color_map[a_][k]=1
            color_map[b_][k]=1
            break

Submission status: Runtime Error

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

tree = {}
for i in ab:
    if tree.get(i[0],-1) == -1:
        tree[i[0]] = [i[1]]
    else:
        tree[i[0]].append(i[1])
    if tree.get(i[1],-1) == -1:
        tree[i[1]] = [i[0]]
    else:
        tree[i[1]].append(i[0])

def maxdegree(tree,n):
    ret = 0
    for i in range(1,n+1):
        ret = max(sum,len(tree[i]))
    return ret

print(trsum(tree,n))

abmap = [[-1]*(n+1) for i in range(n+1)]

def solve(num,pr,used):
    global tree
    global abmap
    cnt = 1
    nodes = tree[num]
    for i in nodes:
        if i == pr:
            continue
        else:
            if cnt == used:
                cnt += 1
            abmap[num][i] = cnt
            abmap[i][num] = cnt
            solve(i,num,cnt)
            cnt += 1

solve(1,0,0)

for i in ab:
    print(abmap[i[0]][i[1]])

Submission status: Runtime Error

Solution code:
"""
DFS
"""
# 再帰回数の上限を解除
import sys
sys.setrecursionlimit(2000)


class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


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

dfs(0)

# 最大次数が色数となる
mx = max([len(g) for g in graph])
print(mx)

for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# DFS
class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


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

dfs(0)

# 最大次数が色数となる
mx = max([len(g) for g in graph])
print(mx)

for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
def used_col(N):
    col = set()
    # 子供の色
    for child in tree_children[N]:
        col.add(ans[child-2])
    # 親の色
    col.add(ans[tree_parent[N]-2])
    # 兄弟の色
    for child in tree_children[tree_parent[N]]:
        col.add(ans[child-2])
    return col
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    parent_bool = 1 if tree_parent[key] != 0 else 0
    max_col = max(len(tree_children[key])+parent_bool , max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = set(range(1,max_col+1))
    NG_col = used_col(i)
    for NG in NG_col:
        if NG == 0:
            pass
        else:
            available.remove(NG)
    ans[i-2] = available[0]
print(max_col)
for a in ans:
    print(a)

Submission status: Runtime Error

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

ans = [None]*(n-1)
def rec(cur,color):

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

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m=1:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Runtime Error

Solution code:
a, b, x = map(int, input().split())

c = 1000000000
d = 1000000000

for i in range(30):
    d = round(d / 2)
    if x > a * 1000000000 + b * 10:
        continue
    elif x < a * c + b * len(str(c)):
        c -= d
    elif x > a * c + b * len(str(c)):
        c += d
    else:
        continue

if x < a * c + b * len(str(c)):
    c -= d/2

if c < 0:
    print(0)
else:
    print(c)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
l.sort()
#print(l)
r=[0]*n
for i in range(n-1):
    r[l[i][0]-1]+=1
    r[l[i][1]-1]+=1
aa=0
c=0

for i in range(n):
    if aa<=r[i]:
        aa=r[i]
        c=i+1

A=1;print(max(r))
p=[0]*(n-1)
w=[[] for _ in range(n)]
for i in range(n-1):
    if l[i][0]==c or l[i][1]==c:
        p[i]=A
        w[l[i][0]-1].append(A)
        w[l[i][1]-1].append(A)
        A+=1

box=set([i for i in range(1,max(r)+1)])
for i in range(n-1):
    if l[i][0]!=c and l[i][1]!=c:
        B=box-set(w[l[i][0]-1]+w[l[i][1]-1])
        #print(B)
        w[l[i][0]-1].append(list(B)[0])
        w[l[i][1]-1].append(list(B)[0])
        p[i]=list(B)[0]

#print(r,c,w)
#print(p)

for i in range(n-1):
    print(p[i])

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,g=graph()
    check = [False for _ in range(n)]
    color=[]
    for _ in range(n):
        dic=defaultdict(int)
        color.append(dic)
    ans=[0 for _ in range(n-1)]
    que=[]
    que.append(0)
    while len(que)>0:
        x = que.pop(0)
        check[x]=True
        go = g[x][i][0]
        for i in range(len(g[x])):
            if check[go]:
                continue
            else:
                que.append(go)
                for j in range(1,n+1):
                    if color[x][j]==0:
                        ans[g[x][i][1]]=j
                        color[x][j]=1
                        color[go][j]=1
                        break
    print(max(ans))
    for i in range(len(ans)):
        print(ans[i])
 
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:16777216")
#pragma warning( disable : 6031)
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <limits>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-9)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef tuple<int, int, int> tiii;
const long long mod = 1000000007;

template<typename T>
void max_self(T& a, T b)
{
	a = max(a, b);
}
int main()
{
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n;
	cin >> n;
	vpii v;
	vpii cnt(n);
	vvi g(n);
	for (int i = 0; i < sz(cnt); i++)
		cnt[i].second = i;
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		v.emplace_back(min(a, b), max(a, b));
		cnt[a].first++; cnt[b].first++;
		g[a].push_back(i);
		g[b].push_back(i);

	}
	vi color(sz(v), -1);
	sort(all(cnt));
	reverse(all(cnt));
	int k = cnt[0].first;
	for (int i = 0; i < sz(cnt); i++)
	{
		int cur = cnt[i].second;
		set<int> available;
		for (int j = 0; j < k; j++)
			available.insert(j);
		for (int j = 0; j < sz(g[cur]); j++)
		{
			if (color[g[cur][j]] != -1)
			{
				available.erase(color[g[cur][j]]);
				continue;
			}
			if (available.empty())
			{
				k++;
				color[g[cur][j]] = k - 1;
			}
			else
			{
				color[g[cur][j]] = *available.begin();
				available.erase(available.begin());
			}


		}
	}
	cout << k << endl;
	for (int i = 0; i < sz(color); i++)
		cout << color[i] + 1 << "\n";

	return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
from collections import defaultdict
d=defaultdict(lambda:defaultdict(int))
l1=[[] for i in range(n+1)]
#d=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l1[a].append(b)
  l1[b].append(a)
  l.append([a,b])
max1=0
for i in l1:
  if max1<len(i):
    max1=len(i)
def dfs(x,y):#xは頂点yは入ってくる色
  l2=l1[x]
  now=1
  for i in range(len(l2)):
    if d[x][l2[i]]!=0:
      pass
    else:                
      if now==y:
        now+=1
      d[x][l2[i]]=now
      d[l2[i]][x]=now
      dfs(l2[i],now)
      now+=1
print(max1)
dfs(1,0)
for i in range(len(l)):
  print(d[l[i][0]][l[i][1]])

Submission status: Runtime Error

Solution code:
from collections import Counter
l = []
l2 = []
n = int(input())
for i in range(n - 1):
  ll = list(map(int, input().split()))
  a = ll[0]
  b = ll[1]
  l2.append(a)
  l2.append(b)
  l.append(ll)
counter = Counter(l2)
k = max(counter.values())
kk = [i for i in range(1, k+1)]
l3 = [kk.copy() for i in range(n)]
print(k)
for i in range(n - 1):
  a = l[i][0]
  b = l[i][1]
  r = min(set(l3[a-1]) & set(l3[b-1]))
  l3[a-1].remove(r)
  l3[b-1].remove(r)
  print(r)

Submission status: Runtime Error

Solution code:
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[]
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b)))
    w.sort()
    for a,b in w:
        c=x[a]|x[b]
        for j in range(1,n*(n-1)//2):
            if j not in c:
                ans.append(j)
                x[a].add(j)
                x[b].add(j)
                break
    #print(x)
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
import sys

# sys.setrecursionlimit(10**9)

N = int(input())

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

colors = [-1] * (N + 1)
K = 0


def bfs(p_node, p_color):
    global K
    children_node = graph[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1
    K = max(K, c_color - 1)


bfs(1, -1)

print(K)
for a, b in ab:
    print(colors[b])

Submission status: Runtime Error

Solution code:
def coloring2(color,p):
    global K
    dcolor = 1
    for c in Data[p]:
        if dcolor == color:
            dcolor += 1
        s = str(p)+'_'+str(c)
        Edge[s] = dcolor 
        coloring2(dcolor,c)
        dcolor += 1
    K = max(K,dcolor-1)

N = int(input())
Data = [ [] for _ in range(N+1) ]
Edge = {} 
Edge2 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    Data[a].append(b)
    s = str(a)+'_'+str(b)
    Edge[s] = 0
    Edge2.append([a,b])

K = 0
coloring2(0,Edge2[0][0])
print(K)
for [a,b] in Edge2:
    s = str(a)+'_'+str(b)
    print(Edge[s])

Submission status: Runtime Error

Solution code:
def coloring2(color,p):
    global K
    dcolor = 1
    for c in Data[p]:
        if dcolor == color:
            dcolor += 1
        s = str(p)+'_'+str(c)
        Edge[s] = dcolor 
        coloring2(dcolor,c)
        dcolor += 1
    K = max(K,dcolor-1)

N = int(input())
Data = [ [] for _ in range(N+1) ]
Edge = {} 
Edge2 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    Data[a].append(b)
    s = str(a)+'_'+str(b)
    Edge[s] = 0
    Edge2.append([a,b])
print(Data)

K = 0
coloring2(0,Edge2[0][0])
print(K)
for [a,b] in Edge2:
    s = str(a)+'_'+str(b)
    print(Edge[s])