Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
E = np.zeros([N-1,2])
for n in range(N-1):
    temp = input().split()
    E[n,0]=int(temp[0])-1
    E[n,1] = int(temp[1])-1
starts = []; ends = []
for n in range(N-1):
    starts.append(E[n,0])
    ends.append(E[n,1])
edges = np.zeros([N-1])
for i in range(N-1):
    edges[i] = starts.count(i)+ends.count(i)
K = int(max(edges))
iro = np.zeros([N-1])
iro_set = [[] for i in range(N)]
for i in range(N-1):
    start = int(E[i,0]); end = int(E[i,1])
    kouho = list(range(1,K+1))
    for sude in iro_set[start]:
        kouho.remove(sude)
    for sude in iro_set[end]:
        kouho.remove(sude)
    iro[i] = kouho[0]
    iro_set[start].append(kouho[0])
    iro_set[end].append(kouho[0])
print(K)
for i in range(N-1):
    print(int(iro[i]))

Submission status: Runtime Error

Solution code:
def dfs(tyoten,oya):
    #print(tyoten)
    if(len(ki[tyoten])==0):
        return
    else:
        for i in range(len(ki[tyoten])):
            temp=-1
            num=eda[tyoten][i]
            if(i>=oya):
                temp=i+1
            else:
                temp=i
            #for j in range(m):
            #    temp=j
            #    if(not iro[tyoten][j]):
            #        iro[tyoten][j]=True
            #        saki=ki[tyoten][i]
            #        iro[saki][j]=True
            #        break
            ans[num]=temp+1
            dfs(ki[tyoten][i],temp)


n=int(input())

ki=[[]for i in range(n)]
eda=[[]for i in range(n)]
ko=[0]*n



for i in range(n-1):
    zen,go=map(int,input().split())
    ki[zen-1].append(go-1)
    eda[zen-1].append(i)

for i in range(n):
    ko[i]=len(ki[i])+1
    if(i==0):
        ko[i]-=1
        pass
#print(ko)

#print(ki)
#print(eda)
m=max(ko)
#if(m==ko[0]+1):
#    herasu=True
#    for i in range(1,n):
#        if(m==ko[i]+1):
#            herasu=False
#    if(herasu):
#        m-=1
print(m)


#iro=[[False]*m for i in range(n)]
#print(iro)
ans=[-1]*(n-1)
dfs(0,10**9)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    colors = [1]*(n+1)
    all_edges = {}
    nodes = {}
    order = []
    edges = []
 
    for i in range(1,n+1):
        nodes[i] = []
        
    for i in range(n-1):
        a,b = map(int,input().split())
        nodes[a].append(b)
        nodes[b].append(a)
        all_edges[(a,b)] = 0
        order.append((a,b))
        edges.append((a,b))

    k = 0
    for i in nodes.keys():
        k = max(k,len(nodes[i]))

    visited = set()
    for i in range(1,n):
        if i not in visited and len(edges[i]) > 1:
            visited.add(i)
            avail = []
            if i == 1:
                limit = colors[i]+1
            else:
                limit = colors[i]
            for j in range(1,limit):
                avail.append(j)
            for j in range(colors[i]+1,k+1):
                avail.append(j)
            #print(i,avail)
            for kid in nodes[i]:
                if kid not in visited:
                    #print(i,kid)
                    all_edges[(i,kid)] = avail.pop()
                    colors[kid] = all_edges[(i,kid)]

    print(k)
    for i in order:
        print(all_edges[i])
    
    
 
main()

Submission status: Runtime Error

Solution code:
def dfs(s, targets):
    global K
    visited[s] = True
    # print(targets)
    for t in targets:
        if visited[t]:
            continue
        mab = max(G3[s], G3[t])
        while (mab in G2[s]) or (mab in G2[t]):
            mab += 1
        K = max(K, mab)
        ans[p2i[(s, t)]]= mab
        G2[s].add(mab)
        G2[t].add(mab)
        while G3[s] in G2[s]:
            G3[s] += 1
        while G3[t] in G2[t]:
            G3[t] += 1
        dfs(t, G[t])

K = 0
N = int(input())
G = [[] for i in range(N+1)]
G2 = [set() for i in range(N+1)]
p2i = {}
visited = [False for i in range(N+1)]
ans = [0 for i in range(N-1)]
G3 = [1] * (N+1)
for i in range(N-1):
    a, b = map(int, input().split())
    p2i[(a, b)] = i
    p2i[(b, a)] = i
    G[a].append(b)
    G[b].append(a)
# print(max(p2i.values()))
s = 1
targets = G[s]
dfs(s, targets)
print(K)
for a in ans:
    print(a)

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)


colors = [0]
maxc = 0
i = 0
stack = [0]
visited = [0]*n
while stack:
    v = stack.pop(0)
    visited[v] = 1
    first = 0
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
        if first == 0:
            first = colors[v]
            i = 1

        if first == i:
            i +=1
        colors.append(i)
        maxc = max(maxc, i)

        i += 1

print(maxc)

colors.pop(0)
for _ in range(len(colors)):
    print(colors[_])

Submission status: Runtime Error

Solution code:
def dfs(tyoten,oya):
    #print(tyoten)
    if(len(ki[tyoten])==0):
        return
    else:
        for i in range(len(ki[tyoten])):
            temp=-1
            num=eda[tyoten][i]
            if(i>=oya):
                temp=i+1
            else:
                temp=i
            #for j in range(m):
            #    temp=j
            #    if(not iro[tyoten][j]):
            #        iro[tyoten][j]=True
            #        saki=ki[tyoten][i]
            #        iro[saki][j]=True
            #        break
            ans[num]=temp+1
            dfs(ki[tyoten][i],temp)


n=int(input())

ki=[[]for i in range(n)]
eda=[[]for i in range(n)]
ko=[0]*n



for i in range(n-1):
    zen,go=map(int,input().split())
    ki[zen-1].append(go-1)
    eda[zen-1].append(i)

for i in range(n):
    ko[i]=len(ki[i])+1
    if(i==0):
        ko[i]-=1
        pass
print(ko)

#print(ki)
#print(eda)
m=max(ko)
#if(m==ko[0]+1):
#    herasu=True
#    for i in range(1,n):
#        if(m==ko[i]+1):
#            herasu=False
#    if(herasu):
#        m-=1
print(m)


#iro=[[False]*m for i in range(n)]
#print(iro)
ans=[-1]*(n-1)
dfs(0,10**9)

for a in ans:
    print(a)

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+1):
            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())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            vv = str(s)+str(t)
            edgedata[vv] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    sss = (str(i[0]) + str(i[1]))
    print(edgedata[sss])
#output k

Submission status: Runtime Error

Solution code:

N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            d=1
        mmx = max(mmx, dfs(t, mx, i+d))
        # dfs(t, mx, i)
    return mmx
for bgn in range(N):
    if len(T[bgn])>0:
        break
# print(bgn)
M = dfs(bgn, 1, -1)
# print(R)
# print(F)
print(M)
for i,f in enumerate(F):
    print(R[f])

Submission status: Runtime Error

Solution code:
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n-1)]
xy_1d = list(itertools.chain.from_iterable(xy))
c = collections.Counter(xy_1d)
cc = c.most_common()
num_max = cc[0][0]
color = cc[0][1]
color_list = [i+1 for i in range(color)]
length = len(xy)
l = [color]
for i in range(length):
    if i <= color:
        l.append(color_list[i])
    elif i > color:
        num = i - int(length/color)*color
        l.append(color_list[num])
print(l)

Submission status: Runtime Error

Solution code:
N = int(input())
g = {i:[] for i in range(N)}
AB = []
K = -float('inf')
for _ in range(N-1):
  a,b = map(int,input().split())
  AB.append([a-1,b-1])
  g[a-1].append(b-1)
  g[b-1].append(a-1)
  K = max(K,len(g[a-1]), len(g[b-1]))

print(K)
k = 1
print(k)
for i in range(1,N-1):
  a,b = AB[i]
  if (AB[i][0] in g[a-1] and AB[i][0] in g[b-1]) or (AB[i][1] in g[a-1] and AB[i][1] in g[b-1]):
    k +=1
    k = 1 if k==5 else k
  print(k)

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)


colors = [0]
maxc = 0
i = 0
stack = [0]
visited = [0]*n
while stack:
    v = stack.pop(0)
    visited[v] = 1
    first = 0
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
        if first == 0:
            first = colors[v]
            i = 1

        if first == i:
            i +=1
        colors.append(i)
        mzxc = max(maxc, i)

        i += 1


print(maxc)

colors.pop(0)
for _ in range(len(colors)):
    print(colors[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5 + 10)

N = int(input())

branch = [[0] + list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
branch_color = [0] * (N - 1)
vertex = [False] * N


def bfs():
    q = deque()
    v = 0
    bc = 0
    q.append((v, bc))

    while len(q):
        v, bc = q.popleft()
        vertex[v] = True
        b_list = [c for c in branch if v in c[1:]]

        for i in [x for x in range(len(b_list)) if x != bc]:
            if (b_list[i][0] == 0):
                b_list[i][0] = i

        for b in b_list:
            nv = b[1] if b[2] == v else b[2]
            if vertex[nv] is False:
                q.append(nv)


bfs()
for b in branch:
    print(b[0])

Submission status: Runtime Error

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

c = 0
k = 1

for i in range(1, n - 1):
    a, b = ab[i]
    pre, _ = ab[i - 1]
    if a == pre:
        c += 1
    else:
        c = 1
    if k >= c:
        k += 1

t = [None for _ in range(n + 1)]
a, b = ab[0]
c = 0
t[a] = c
t[b] = c


print(k)
print(c + 1)

for i in range(1, n - 1):
    a, b = ab[i]
    pre, _ = ab[i - 1]
    if a == pre:
        pass
    else:
        c = t[a]

    c = (c + 1) % k
    t[b] = c
    print(c + 1)


exit(0)

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]
print(tree)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
ans = []
sub = [0 for i in range(n+1)]
k = 0
for i in range(n+1):
    color = 0
    for j in range(len(tree[i])):
        color += 1
        if color == sub[i]:
            color += 1
        ans.append(color)
        sub[tree[i][j]].append(color)
        if k > color:
            k = color
print(k)
for i in range(len(ans)):
    print(ans[i])

Submission status: Runtime Error

Solution code:
#input = raw_input
#range = xrange

n = int(input())

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

edges = []
for i in range(n-1):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    #edge = (a, b)
    edge = tuple(sorted([a, b]))
    edges.append(edge)

#node_nums = [len(node) for node in graph]
node_nums = [len(graph[node]) for node in range(n)]
num_color = max(node_nums)
print(num_color)


def coloring(edge_colors, parent_node, cur_node, former_color):
    kid_nodes = graph[cur_node]

    if len(kid_nodes) == 1:
        return edge_colors

    cur_color = 1
    for kid_node in kid_nodes:
        if kid_node == parent_node:
            continue

        if former_color == cur_color:
            cur_color += 1
        edge = tuple(sorted([cur_node, kid_node]))
        edge_colors[edge] = cur_color
        edge_colors = coloring(edge_colors, cur_node, kid_node, cur_color)

        cur_color += 1

    return edge_colors
        

edge_colors = {}
start_node = node_nums.index(1)
kid_nodes = graph[start_node]
#assert len(kid_nodes) == 1
kid_node = kid_nodes[0]
edge = tuple(sorted([start_node, kid_node]))
cur_color = 1
edge_colors[edge] = cur_color
former_color = cur_color

edge_colors = coloring(edge_colors, start_node, kid_node, former_color)

for edge in edges:
    color = edge_colors[edge]
    print(color)

Submission status: Runtime Error

Solution code:
n = int(input())
v = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    v[ai-1].append(bi-1)
    v[bi-1].append(ai-1)
    edge.append((ai-1,bi-1))
    
vedges = [len(v[i]) for i in range(n)]
ncolor = max(vedges)

colors = [list(range(i%ncolor,(i%ncolor+vedges[i])%ncolor)) for i in range(n) ]

print(ncolor)
for i in range(n-1):
    ai, bi = edge[i]
    c = colors[ai][v[ai].index(bi)]
    print(c+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 10)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            vv = str(s)+str(t)
            edgedata[vv] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    sss = (str(i[0]) + str(i[1]))
    print(edgedata[sss])
#output k

Submission status: Runtime Error

Solution code:
def dfs(tyoten,oya):
    #print(tyoten)
    if(len(ki[tyoten])==0):
        return
    else:
        for i in range(len(ki[tyoten])):
            temp=-1
            num=eda[tyoten][i]
            if(i>=oya):
                temp=i+1
            else:
                temp=i
            #for j in range(m):
            #    temp=j
            #    if(not iro[tyoten][j]):
            #        iro[tyoten][j]=True
            #        saki=ki[tyoten][i]
            #        iro[saki][j]=True
            #        break
            ans[num]=temp+1
            dfs(ki[tyoten][i],temp)


n=int(input())

ki=[[]for i in range(n)]
eda=[[]for i in range(n)]
ko=[0]*n



for i in range(n-1):
    zen,go=map(int,input().split())
    ki[zen-1].append(go-1)
    eda[zen-1].append(i)

for i in range(n):
    ko[i]=len(ki[i])+1
    if(i==0):
        #ko[i]-=1
        pass
#print(ko)

#print(ki)
#print(eda)
m=max(ko)+1
if(m==ko[0]+1):
    herasu=True
    for i in range(1,n):
        if(m==ko[i]+1):
            herasu=False
    if(herasu):
        m-=1
print(m)


#iro=[[False]*m for i in range(n)]
#print(iro)
ans=[-1]*(n-1)
dfs(0,10**9)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

results = list()

for i in range(n):
    for j in range(n):
        seq = a[j:j + i + 1]
        remainder = sum(seq) % k
        if (remainder == len(seq)):
            temp_seq = tuple(seq)
            if (temp_seq not in results):
                results.append(tuple(seq))

print(results)

Submission status: Runtime Error

Solution code:
n = int(input())
edge = []
color = [0]*n
color[0]=1


def ironuri(k,color):#edge k (0~n-1)
    a = edge[k][0]
    b = edge[k][1]
    koho = []
    for j in range(len(edge)):
        if color[j] ==0:#まだ色なし
            if (edge[j][0] in edge[k]) or (edge[j][1] in edge[k]):
                koho.append(j)
    col = 1
    for i in koho:
        if col == k:
            col +=1
        color[i]=col
    for l in koho:
        ironuri(l,color)
        
    return color


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

color = ironuri(0,color)
print(max(color))
for c in color:
    print(color)

Submission status: Runtime Error

Solution code:
import collections
from collections import defaultdict
N = int(input())
edges = []
vertexes = []
parent = {}
childs = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  childs[a].append(b)
  edges.append((a,b))
  vertexes.append(a)
  vertexes.append(b)
  
#print(edges)
#print(vertexes)
#print(parent)
#childs = dict(childs)
#print(childs)

c = collections.Counter(vertexes)
max_color = max(c.values())
print(max_color)

parent_color = {1: -1}
color_dict = defaultdict(dict)

def set_color(i, pc):
  if i not in childs:
    return
  allowed_colors = [j for j in range(1, max_color + 1) if j != pc]
  for child, color in zip(childs[i], allowed_colors):
    color_dict[i][child] = color
    set_color(child, color)

set_color(1, 1)

for e in edges:
  print(color_dict[e[0]][e[1]])

Submission status: Runtime Error

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(i, prev, prevc, t, d, ans):
    if i == 0:
        num = len(t[i])
    else:
        num = len(t[i]) + 1
    x = 1
    if prevc == 1:
        x = 2
    for c in t[i]:
        if c == prev:
            continue
        ans[d[i, c]] = x
        num = max(num, solve(c, i, x, t, d, ans))
        x += 1
        if x == prevc:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = np.empty((N, N), i8)
    d.fill(-1)
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
        d[a - 1, b - 1] = count
        d[b - 1, a - 1] = count
        count += 1
    num = solve(0, -1, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)

main()

Submission status: Runtime Error

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


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
    print(K)
    S = []
    for _ in range(N):
        s = set()
        for i in range(1, K+1):
            s.add(i)
        S.append(s)
    for a, b in E2:
        s = s[a]
        s -= C[a]
        s -= C[b]
        c = s.pop()
        print(c)
        C[a].add(c)
        C[b].add(c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
g = {i:[] for i in range(N)}
AB = []
K = -float('inf')
for _ in range(N-1):
  a,b = map(int,input().split())
  AB.append([a-1,b-1])
  g[a-1].append(b-1)
  g[b-1].append(a-1)
  K = max(K,len(g[a-1]), len(g[b-1]))

print(K)
k = 1
print(k)
for i in range(1,N-1):
  a,b = AB[i]
  if AB[i][0] in g[a-1] + g[b-1] or AB[i][1] in g[a-1] + g[b-1]:
    k +=1
    k = 1 if k==5 else k
  print(k)

Submission status: Runtime Error

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

color = [i+1 for i in range(max(si))]
cnt = [[] for i in range(n)]
for i in range(n-1):
	new = min(set(color) - (set(cnt[ab[i][0]-1]) | set(cnt[ab[i][1]-1])))
	cnt[ab[i][0]-1].append(new)
	cnt[ab[i][1]-1].append(new)
	print(new)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def tree(l, x):
    z = 0
    for i in l:
        if ans[i] == 0:
            z += 1
            if z == x:
                z += 1
            ans[i] = z
            tree(d[i], z)


def resolve():
    n = int(input())
    a = []
    b = []
    global d
    d = defaultdict(list)
    for _ in range(n - 1):
        x, y = sorted(map(int, input().split()))
        d[x - 1] += [y - 1]
        d[y - 1] += [x - 1]
    global ans
    ans = [0] * n
    ans[0] = 1
    a = 1
    for i in d[0]:
        a += 1
        tree(d[i], a)
    for i in ans:
        print(i)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [[0] for _ in range(N)]
print(A)
a = 0
b = 0
c = []
for i in range(N):
    a,b = map(int,input().split())
    A[a - 1].append(max(max(A[a-1])+1,max(A[b-1]+1)))
    A[b - 1].append(max(max(A[a-1])+1,max(A[b-1]+1)))
    c.append(max(max(A[a-1])+1,max(A[b-1]+1)))
print(c)
for j in c:
    print(j)

Submission status: Runtime Error

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

K = max(count)
All = set(range(1, K+1))
memo = [[] for i in range(N)]
print(K)
for a, b in n:
  m = list(All - set(memo[a-1] + memo[b-1]))[0]
  memo[a-1].append(m)
  memo[b-1].append(m)
  print(m)

Submission status: Runtime Error

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    history = []
    int_list = [list(range(1, n)) for _ in range(n//2)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        smaller = min(a, b)
        larger = max(a, b)
        vmax = int_list[smaller-1].pop(0)
        int_list[larger-1].remove(vmax)
        history.append(vmax)

    all_max = max(history)
    print(all_max)

    for h in history:
        print(h)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            vv = str(s)+str(t)
            edgedata[vv] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    sss = (str(i[0]) + str(i[1]))
    print(edgedata[sss])
#output k

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
color_dict = {i : set(range(1,1+_max)) for i in range(n)}
candidate = set(range(1,_max+1))
def dfs(_from, ind, last):
    next_constain = []
    for _next in graph[ind]:
        if _next == _from:
            continue
        res = dfs(ind, _next, next_constain)
        last.append(res)
        next_constain.append(res)
    if _from == -1:
        return 0
    used = list(candidate - set(last))[0]
    colors[ind][_from] = used
    colors[_from][ind] = used
    return used

dfs(-1, _max_node, [])
print(_max)
for a, b in ls:
    print(colors[a][b])

Submission status: Runtime Error

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


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
    print(K)
    for a, b in E2:
        s = set()
        for i in range(1, K+1):
            s.add(i)
        s -= C[a]
        s -= C[b]
        c = s.pop()
        print(c)
        C[a].add(c)
        C[b].add(c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from operator import itemgetter

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i) for i in input().split()])

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0] - 1].append(row[1] - 1)
edge_color = dict()

def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    if target_list == []:
        pass
    else:
        for ko_node in target_list:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color 
            DFS_color(ko_node, color)
            color += 1

DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1 - 1, node2 - 1])

Submission status: Runtime Error

Solution code:
n = int(input())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append([b, i])
  else:
    edges[a] = [[b, i]]
  if b in edges.keys():
    edges[b].append([a, i])
  else:
    edges[b] = [[a, i]]
colors = [0 for i in range(n-1)]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  global edges
  flags[node] = True
  for edge in edges[node]:
    if flags[edge[0]] == False:
      if i != cannot:
        colors[edge[1]] += i
      else:
        i += 1
        colors[edge[1]] += i
      i += 1
      search(edge[0], i-1)
search(2, 0)
print(max(colors))
for i in range(n-1):
  print(colors[i])

Submission status: Runtime Error

Solution code:
n = int(input())
tree_i = {}
tree_n = {}
for i in range(n-1):
  a,b = map(int,input().split())
  tree_i[(a,b)] = i
  if a in tree_n:
    tree_n[a].append(b)
  else:
    tree_n[a] = [b]
  if b in tree_n:
    tree_n[b].append(a)
  else:
    tree_n[b] = [a]

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

def coloring(n_b,n,color_b,tree_i,tree_n):
  nodes = tree_n[n]
  color = 0
  for node in nodes:
    if node ==n_b:
      continue
    if color == color_b:
      color += 1
    a = min(n,node)
    b = max(n,node)
    ans[tree_i[(a,b)]] = color
    coloring(n,node,color,tree_i,tree_n)
    color +=1

coloring(-1,1,-1,tree_i,tree_n)
print(max(ans)+1)
for i in ans:
  print(i+1)

Submission status: Runtime Error

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

max_num = 0
used = {}
for i in range(N):
    tmp = c.count(i+1)
    if tmp > max_num:
        max_num = tmp
    used[i] = []
print(max_num)

value = []
for i in range(max_num):
    value.append(i)

for i in range(N-1):
    tmp = used[a[i]-1]
    tmp.extend(used[b[i]-1])
    res = list(set(value)-set(tmp))
    print(res[0]+1)

    used[a[i]-1].append(res[0])
    used[b[i]-1].append(res[0])

    #　計算オーダーN**2のためTLE
    # for k in range(max_num):
    #     if not k in used[a[i]-1] and not k in used[b[i]-1]:
    #         print(k+1)
    #         used[a[i]-1].append(k)
    #         used[b[i]-1].append(k)
    #         break

Submission status: Runtime Error

Solution code:
# coding: utf-8


def main():
    N = int(input())

    a = [None] * (N-1)
    b = [None] * (N-1)

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

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

    # edges = zip(a, b)
    for i in range(N-1):
        nodes[a[i]].append([i, b[i]])
        nodes[b[i]].append([i, a[i]])

    K = 0
    for i in range(N-1):
        if len(nodes[i]) > K:
            K = len(nodes[i])
    # K is n_color

    colors = [k+1 for k in range(K)]

    edge_colors = [None] * (N-1)

    def rec(node, parent=None, used=None):
        if used is None:
            available = colors
        else:
            available = [color for color in colors if color != used]

        # print("availarble: {}".format(available))
        # print("nodes[node]: {}".format(nodes[node]))

        j = 0
        for i in range(len(nodes[node])):
            edge, child = nodes[node][i]
            if parent is not None and child == parent:
                continue
            # print("edge: {}".format(edge))
            # print("edge_colors: {}".format(edge_colors))
            # print()
            edge_colors[edge] = available[j]
            rec(child, parent=node, used=available[j])
            j += 1


    rec(0)

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


if __name__ == "__main__":
    main()