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().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
try:
    paint(tmp[0][0], -1)
except IndexError:
    print(0)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
from collections import deque
def bfs(succs, preds, start, colors):
    saisyoku = {}
    queue = deque([start])
    used = 0
    while queue:
        v = queue.popleft()
        for u in preds[v]:
            used = saisyoku[preds[v][u]]
        c = 1
        for w in succs[v]:
            if used and c == used:
                c += 1
            saisyoku[succs[v][w]] = c
            queue.append(w)
            c += 1
    return saisyoku
  
n = int(input())
vertices = range(1, n+1)
edges = [list(map(int, input().split())) for _ in range(n-1)]
jisu = {v: 0 for v in vertices}
succs = {v: {} for v in vertices}
preds = {v: {} for v in vertices}
for i, (u, v) in enumerate(edges):
  succs[u][v] = i
  preds[v][u] = i
  jisu[u] += 1
  jisu[v] += 1
colors = max(jisu.values())
print(colors)
saisyoku = bfs(succs, preds, 1)
for _, c in sorted(saisyoku.items()):
    print(c)

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    try:
        n_list[node]
    except Exception as e:
        exit(0)
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

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[12] => 1->2の辺の色を入れておく
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には色の種類を入れる
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:
        #まだ見てなかったら、dfsを掛ける
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            #小さいほうから大きいほうに文字を並べ、ハッシュに値を保存
            edgedata[(s, t)] = color_list[c_i]
            #color_list[c_i]は使ったので、使った色として引数で渡す。
            dfs(i, color_list[c_i])
            #この色は使ったから、一個ずらす
            c_i += 1
#一番のノードを根とし、dfsをかける
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])
#output k

Submission status: Runtime Error

Solution code:
iro = []
res = []
r = 0
cm = []
for i in range(N):
  cm.append([])
N = int(input())
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = 0
  while cr < r
    if a not in iro[cr] and b not in iro[cr]:
      iro[cr].append(a)
      iro[cr].append(b)
      res.append(cr+1)
      break
    cr += 1
  else:
    r = cr
    iro.append([a,b])
    res.append(cr+1)
print(r+1)
for i in res:
  print(i)

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            try: 
                if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                    tmp_color += 1
                colors[edge[1]] = tmp_color
            except Exception as e:
                print(0)
                exit(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    if a >= len(nodes):
        exit()
    if b >= len(nodes):
        exit()
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    if links is None:
        exit()
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, links, edge, pc):
    c = 1
    if pc == c:
        c += 1

    for n, i in links:
        if n < 0 or i < 0:
            exit()
        if n >= len(nodes) or i >= len(edge):
            exit()

        if edge[i] != 0:
            continue
        edge[i] = c
        fill(nodes, nodes[n], edge, c)

        c += 1
        if pc == c:
            c += 1

    
fill(nodes, nodes[max_i], edge, 0)

print(max_l)
for e in edge:
    print(e)

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        if len(edge) != 2:
            exit(0)
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            try: 
                if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                    tmp_color += 1
                colors[edge[1]] = tmp_color
            except Exception as e:
                print(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            try: 
                if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                    tmp_color += 1
                colors[edge[1]] = tmp_color
            except Exception as e:
                print(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            #try: 
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            #except Exception as e:
                #print(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, links, edge, pc):
    c = 1
    if pc == c:
        c += 1

    next_fills = []
    for n, i in links:
        if edge[i] != 0:
            continue
        edge[i] = c
        fill(nodes, nodes[n], edge, c)

        c += 1
        if pc == c:
            c += 1

    
fill(nodes, nodes[max_i], edge, 0)

print(max_l)
for e in edge:
    print(e)

Submission status: Runtime Error

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


def solve(i, prev, prevc, t, d, ans):
    num = len(t[i])
    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
sys.setrecursionlimit(10**6)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
i: int
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)


def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color

    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color


print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(10**7)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
i: int
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)


def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color

    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color


print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline()
N = int(input())

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

eda = [set() for i in range(N)]

for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda) == max_e:
        id = i

ans = [1]*(N-1)
q = collections.deque()
q.append(id)
print(max_e)
eda2 = [set() for i in range(N)]
for a, b in ab:
    for i in range(1, max_e+1):
        if i not in eda2[a-1] and i not in eda2[b-1]:
            ans = i
            break
    print(ans)
    eda2[a-1].add(i)
    eda2[b-1].add(i)

Submission status: Runtime Error

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

K = max(len(S) for S in ad)
d = dict()

def dfs(v=0, pv=-1, memo=-1):
    color = 0
    for nv in ad[v]:
        if nv == pv:
            continue
        if color == memo:
            color += 1
        d[(v, nv)] = color
        d[(nv, v)] = color
        dfs(nv, v, color)
        color += 1

dfs()

print(K)
for e in edge:
    print(d[e]+1)

Submission status: Runtime Error

Solution code:
iro = []
res = []
r = 0
cc = {}
N = int(input())
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = 0
  for p in iro:
    if a in iro:
      cr += 1
      continue
    elif b in iro:
      cr += 1
      continue
    elif a not in p and b not in p:
      iro[cr].append(a)
      iro[cr].append(b)
      res.append(cr+1)
      else:
        if cc[a] > 

      break
    cr += 1
  else:
    r = cr
    iro.append([a,b])
    res.append(cr+1)
print(r+1)
for i in res:
  print(i)

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []

for i in range(N):
    nodes.append([])

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

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, links, edge, pc):
    c = 1
    while pc & (1 << c) != 0:
        c += 1

    next_fills = []
    for n, i in links:
        if edge[i] != 0:
            pc |= (1 << edge[i])
            continue
        edge[i] = c
        next_fills.append((n, c))

        c += 1
        while pc & (1 << c) != 0:
            c += 1

    for n, c in next_fills:
        fill(nodes, nodes[n], e, (c << 1))
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)

print(max_l)
for i in e:
    print(i)

Submission status: Runtime Error

Solution code:
iro = []
res = []
r = 0
cc = {}
N = int(input())
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = 0
  for p in iro:
    if a in iro:
      continue
    elif b in iro:
      continue
    elif a not in p and b not in p:
      iro[cr].append(a)
      iro[cr].append(b)
      res.append(cr+1)
      else:
        if cc[a] > 

      break
    cr += 1
  else:
    r = cr
    iro.append([a,b])
    res.append(cr+1)
print(r+1)
for i in res:
  print(i)

Submission status: Runtime Error

Solution code:
from collections import Counter


def main(n: int, points: list):
    # print(n)
    # print(points)

    # c = Counter([p[0] for p in points])
    # deg = max(c.values()) + 1
    # print(max(list(c.items()), key=lambda pair: pair[1]))
    # print()
    c = Counter()
    for p in points:
        c.update(p)

    max_degree = max(c.values())
    colors = set(list(range(1, max_degree+1))[::-1])
    print(max_degree)

    painted = {}
    for v in range(1, n+1):
        painted.setdefault(v, set())

    results = []
    for edge in points:
        _from = edge[0]
        _to = edge[1]
        # print(edge)

        _ = colors.difference(painted[_from] | painted[_to])
        color = min(_)
        painted[_from].add(color)
        painted[_to].add(color)
        # print((_from, _to), color, painted[_from], painted[_to])
        results.append(color)

    for c in results:
        print(c)


if __name__ == '__main__':
    n = int(input())
    a = [input() for i in range(n-1)]

    points = [s.split(' ') for s in a]


    main(
        n,
        [(int(p[0]), int(p[1])) for p in points]
    )

Submission status: Runtime Error

Solution code:
import itertools
import collections
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])
for j in l:
    print(j)

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []

for i in range(N):
    nodes.append([])

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


max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, links, e, pc):
    c = 1
    if c == pc:
        c += 1

    next_fills = []
    for n, i in links:
        if e[i] != 0:
            continue
        e[i] = c
        next_fills.append((n, c))

        c += 1
        if c == pc:
            c += 1

    for n, c in next_fills:
        fill(nodes, nodes[n], e, c)
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)

print(max_l)
for i in e:
    print(i)

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])
for j in l:
    print(j)

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])
for i in l:
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
M=np.zeros((N,N),int)
AB=[]
for _ in range(N-1):
    i,j=map(int,input().split())
    AB.append([i,j])
    M[i-1,j-1]=1
    M[j-1,i-1]=1
    
k=0
for i in range(N):
    if k<M[i].sum():
        k=max(k,M[i].sum())
        I=i
j=1
for i in range(N):
    if M[I,i]==1:
        M[I,i]=j
        j+=1
j=1
for i in range(N):
    if M[i,I]==1:
        M[i,I]=j
        j+=1
for i in range(N):
    for j in range(I,N):
        if j==I:
            x=M[i,j]
        
        if M[i,j]==1:
            x=(x+1)%k
            if x==0:
                x=k
            M[i,j]=x

for i in range(N):
    flag=0
    for j in reversed(range(N)):
        if M[i,j]!=0 and flag==0:
            x=M[i,j]
            flag=1
        
        if M[i,j]!=0:
            x=(x-1)%k
            if x==0:
                x=k
            M[i,j]=x
print(k)
for ab in AB:
    
    print(M[ab[0]-1,ab[1]-1])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[0 for i in range(n-1)]for j in range(n)]
m=[0]*n
t=[]
w=[]
for p in range(n-1):
    e = list(map(int, input().split()))
    w.append(e)

for i in range(n-1):
    a=w[i][0]-1
    b=w[i][1]-1
    m[a] +=1
    m[b] +=1
    k=0
    while True:

        if l[a][k]==0 and l[b][k]==0:
            l[a][k]=1
            l[b][k]=1
            break
        else:
            k +=1

    print(l)
c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []
edges = []

for i in range(N):
    nodes.append([])


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

    nodes[a].append((b, i))
    nodes[b].append((a, i))

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l <= l:
        max_l = l
        max_i = i


def fill(nodes, links, e, pc):
    c = 1
    if c == pc:
        c += 1
    for n, i in links:
        if e[i] != 0:
            continue
        e[i] = c
        fill(nodes, nodes[n], e, c)

        c += 1
        if c == pc:
            c += 1
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)

print(max_l)
for i in e:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []
edges = []

for i in range(N):
    nodes.append([])


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

    nodes[a].append((b, i))
    nodes[b].append((a, i))

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i


def fill(nodes, links, e, pc):
    c = 1
    if c == pc:
        c += 1
    for n, i in links:
        if e[i] != 0:
            continue
        e[i] = c
        fill(nodes, nodes[n], e, c)

        c += 1
        if c == pc:
            c += 1
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)

print(max_l)
for i in e:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())

nodes = []
edges = []

for i in range(N):
    nodes.append([])


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

    nodes[a].append((b, i))
    nodes[b].append((a, i))

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i


def fill(nodes, links, e, pc):
    c = 1
    if c == p:
        c += 1
    for n, i in links:
        if e[i] != 0:
            continue
        e[i] = c
        fill(nodes, nodes[n], e, c)

        c += 1
        if c == pc:
            c += 1
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)

print(max_l)
for i in e:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())       

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

max_edge = 0
tmp = 0
edge_num = 0
color = 1

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

for i in range(1, N+1):
  tmp = a.count(i) + b.count(i)
  if max_edge < tmp:
    max_edge = tmp
    edge_num = i

print(max_edge)

for i in range(0, N-1):
  print(color)
  if a[i] ==  edge_num or b[i] edge_num:
    color += 1

Submission status: Runtime Error

Solution code:
import copy

N = int(input())

lst = [[] for _ in range(N + 1)]
ans = []

for _ in range(N - 1):
  a, b = (int(i) for i in input().split(' '))
  
  lsttmp = [i for i in range(max(1,len(lst[a]) + len(lst[a])) + 1)]
  lsttmp = lsttmp[1:]
  lsttmp = list(set(lsttmp) - set(lst[a]))
  lsttmp = sorted(list(set(lsttmp) - set(lst[b])))
  
  cnt = lsttmp[0]
  
  ans.append(cnt)
  lst[a].append(cnt)
  lst[b].append(cnt)

ans.insert(0, max(ans))

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

Submission status: Runtime Error

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N-1)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            try: 
                colors[edge[1]] = tmp_color
            except Exception as e:
                print(0)
            paint(edge[0], edge[1])
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Runtime Error

Solution code:
N=int(input())
graph={i+1:[] for i in range(N)}
coloured=[0 for i in range(N+1)]
#↑0から始まってる（ただしkeyはそのまま使える）
node_list=[]

for i in range(N-1):
    node=tuple([int(thing) for thing in input().split(" ")])
    a=node[0]
    b=node[1]
    graph[a].append((b,i))
    graph[b].append((a,i))
# ranking=sorted(range(1,N),key=lambda x:len(graph[x]),reverse=True)

cc=0
ret=["" for i in range(N-1)]
def what_colour(a_bit,b_bit):
    i=0
    while True:
        if (2**i&a_bit!=0) or (2**i&b_bit!=0):
            i=i+1
            continue
        else:
            if i>cc:
                c=cc+1
            return i


for i in range(N):
    for thing in graph[i]:
        j=thing[0]
        num=thing[1]

        c=what_colour(coloured[i],coloured[j])
        coloured[i]=coloured[i]+2**c
        coloured[j]=coloured[j]+2**c

        graph[j].remove((i,num))
        ret[num]=c
print(cc)
for thing in ret:
    print(thing+1)

Submission status: Runtime Error

Solution code:
N=int(input())
arr=[[] for i in range(N+1)]
key=[[i for i in range(1,N+1)] for j in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    arr[a].append([a,b])
m=[]
maxk=1
for i in range(1,N+1):
    k=0

    for ele in arr[i]:
        m.append(key[i][k])
        maxk=max(maxk,m[-1])
        key[arr[i][0][1]].remove(key[i][k])
        
print(maxk)
for ele in m:
    print(ele)

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:
N = int(input())

nodes = []
edges = []

for i in range(N):
    nodes.append([])


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

    nodes[a].append((b, i))
    nodes[b].append((a, i))

max_l = 0
max_i = 0
for i in range(N):
    l = len(nodes[i])
    if max_l < l:
        max_l = l
        max_i = i


def fill(nodes, links, e, p):
    c = 1
    if c == p:
        c += 1
    for n, i in links:
        if e[i] != 0:
            continue
        e[i] = c
        fill(nodes, nodes[n], e, c)

        c += 1
        if c == p:
            c += 1
    
e = [0] * (N - 1)
fill(nodes, nodes[max_i], e, 0)
print(max_l)

for i in e:
    print(i)

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(nodes[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()