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

Submission status: Runtime Error

Solution code:
import numpy as np

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

Submission status: Runtime Error

Solution code:
n = int(input())
L = []
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    L.append((a, b))
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
k = 0
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
dd = {1: 0}
ans = {}
for i, v in d.items():
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        ans[(i, j)] = c
        dd[j] = c
for a, b in L:
    print(ans[(a, b)])

Submission status: Runtime Error

Solution code:
n = int(input())
d = {}
k = 0
for _ in range(n-1):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
dd = {1: 0}
for i, v in d.items():
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        print(c)
        dd[j] = c

Submission status: Runtime Error

Solution code:
n=int(input())
L=[[] for _ in range(n)]
stem=[]
col=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    a -= 1
    b -= 1
    L[a].append(i)
    L[b].append(i)
    stem.append((a,b))
col[0]=1
def spl(x,y):
    l=L[x]
    if len(l)>1:
        ind=stem.index((min(x,y),max(x,y)))
        fb=col[ind]
        t=1
        nex=[]
        for i in l:
            if t==fb:
                t += 1
            if i!=ind:
                col[i]=t
                if stem[i][0]==x:
                    nex.append(stem[i][1])
                else:
                    nex.append(stem[i][0])
                t += 1
        for i in nex:
            spl(i,x)

spl(stem[0][0],stem[0][1])
spl(stem[0][1],stem[0][0])
m=0
for i in col:
    m=max(m,i)
print(m)
for i in col:
    print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
L=[[] for _ in range(n)]
stem=[]
col=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    a -= 1
    b -= 1
    L[a].append(i)
    L[b].append(i)
    stem.append((a,b))
col[0]=1
print(L,stem)
def spl(x,y):
    l=L[x]
    if len(l)>1:
        ind=stem.index((min(x,y),max(x,y)))
        fb=col[ind]
        t=1
        nex=[]
        for i in l:
            if t==fb:
                t += 1
            if i!=ind:
                col[i]=t
                if stem[i][0]==x:
                    nex.append(stem[i][1])
                else:
                    nex.append(stem[i][0])
                t += 1
        print(nex)
        for i in nex:
            spl(i,x)
spl(stem[0][0],stem[0][1])
spl(stem[0][1],stem[0][0])
print(max(col))
for i in col:
    print(i)

Submission status: Runtime Error

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

n = int(input())
tree = [[] for _ in range(n)]
dic = {}

for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    dic[(a - 1, b - 1)] = i
ans = [0 for _ in range(n - 1)]
max_color = 0

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        ans_ind = dic[(pos, next_pos)]
        if pos < next_pos:
            ans[ans_ind] = color
        else:
            ans[ans_ind] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

print(max_color)
for i in ans:
    print(i)
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
tree = [[] for _ in range(n)]
dic = {}

for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    dic[(a - 1, b - 1)] = i
ans = [0 for _ in range(n - 1)]
max_color = 0

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        ans_ind = dic[(pos, next_pos)]
        if pos < next_pos:
            ans[ans_ind] = color
        else:
            ans[ans_ind] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

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

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for _ in range(n)]
dic = {}

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

max_color = 0

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        if pos < next_pos:
            dic[(pos, next_pos)] = color
        else:
            dic[(next_pos, pos)] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

print(max_color)
for _, i in dic.items():
    print(i)

Submission status: Runtime Error

Solution code:
# 920~
# 解法 よく考えたら一度解いた問題な気がする
#  936 まず，最も接続数が多いノードについて，異なる色を決める，
#  他のノードについては，自分が現在接続されているものとは違う色を適当に選んでつける
# 実装
# ノードの色塗りの仕方がわからない. (x,y) = colorってしちゃうと，N*Nのlistを作らないとイケなくない？？
#

N = int(input())
A = [[] for _ in range(N)]
J = []
col = {}


for _ in range(N-1):
    ai, bi = map(int, input().split())
    A[ai - 1].append(bi)
    A[bi - 1].append(ai)
    J.append([ai, bi])

node_num = [len(a) for a in A]

# 親から子へ探索をする．ノードごとにつながっているノードを取り出してきて，それが親なら無視する．親以外なら親以外の色をつけて，
# 自身が親となってdfsを返す.
def dfs(this_node,parent_node,parent_color):
    # 入力　今のノード,親のエッジ， 親の色，
    # エッジに色を塗る
    # 出力　子のエッジ，子の色
    # 終了条件 なし 親のノードしかないノードに行くと，勝手に探索をやめる
    this_color=0
    for a in A[this_node-1]:
        if a == parent_node:
            continue
        if this_color == parent_color:
            this_color += 1
        if this_node > a:
            tmp = this_node
            this_node = a
            a = tmp
        col[(this_node,a)] = this_color
        this_color += 1
        dfs(a,this_node,this_color-1)

# 子供がいる場合は，そいつらにつなぐ
dfs(1,-1,-1)
# 最終的にはエッジを選んで出力しないといけない
print(max(node_num))
for j in J:
    j = tuple(j)
    print(col[j]+1)

Submission status: Runtime Error

Solution code:
# 920~
# 解法 よく考えたら一度解いた問題な気がする
#  936 まず，最も接続数が多いノードについて，異なる色を決める，
#  他のノードについては，自分が現在接続されているものとは違う色を適当に選んでつける
# 実装
# ノードの色塗りの仕方がわからない. (x,y) = colorってしちゃうと，N*Nのlistを作らないとイケなくない？？
#

N = int(input())
A = [[] for _ in range(N)]
J = []
col = {}


for _ in range(N-1):
    ai, bi = map(int, input().split())
    A[ai - 1].append(bi)
    A[bi - 1].append(ai)
    J.append([ai, bi])

node_num = [len(a) for a in A]

# 親から子へ探索をする．ノードごとにつながっているノードを取り出してきて，それが親なら無視する．親以外なら親以外の色をつけて，
# 自身が親となってdfsを返す.
def dfs(this_node,parent_node,parent_color):
    # 入力　今のノード,親のエッジ， 親の色，
    # エッジに色を塗る
    # 出力　子のエッジ，子の色
    # 終了条件 なし 親のノードしかないノードに行くと，勝手に探索をやめる
    this_color=0
    for a in A[this_node-1]:
        if a == parent_node:
            continue
        if this_color == parent_color:
            this_color += 1
        dfs(a,this_node,this_color)
        if this_node > a:
            tmp = this_node
            this_node = a
            a = tmp
        col[(this_node,a)] = this_color
        this_color += 1

# 子供がいる場合は，そいつらにつなぐ
dfs(1,-1,-1)
# 最終的にはエッジを選んで出力しないといけない
print(max(node_num))
for j in J:
    j = tuple(j)
    print(col[j]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[] for i in range(n+1)]
d = {}
l = [-1] * (n-1)
max_idx = 0
for i in range(n-1):
  u,v = map(int, input().split())
  d[(u,v)] = i
  g[u].append((u,v))
  g[v].append((v,u))
  if len(g[max_idx]) < len(g[u]):
    max_idx = u
  if len(g[max_idx]) < len(g[v]):
    max_idx = v
m = len(g[max_idx])
stack = []
while len(g[1]) > 0:
  stack.append(g[1].pop())
while len(stack) > 0:
  u, v = stack.pop()
  if len(g[v]) > 0:
    count = m
    while len(g[v]) > 0:
      u2, v2 = g[v].pop()
      if count == l[d[(u, v)]]:
        count -= 1
      l[d[(u2, v2)]] = count
      count -= 1
      stack.append((u2, v2))
print(m)
for i in range(n-1):
  print(l[i])

Submission status: Runtime Error

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

res = [None] * N
def dfs(n, c=-1, p=-1):
  res[n] = c
  if c==-1 or c>1: 
    nc = 1
  else:
    nc = c+1
  for nei in adj[n]:
    if nei == p: continue
    dfs(nei, nc, n)
    nc += 1
    if nc==c: nc += 1

dfs(0)
res = res[1:]
print(len(set(res)))
for r in res: print(r)

Submission status: Runtime Error

Solution code:
N = int(input())
E = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split(' '))
    E[a].append((b,i))
    E[b].append((a,i))
K = max(len(e) for e in E)
print(K)
ans = [-1]*(N-1)
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
E = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split(' '))
    E[a].append((b,i))
    E[b].append((a,i))
K = max(len(e) for e in E)
print(K)
ans = [-1]*(N-1)
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
for i in ans[1:]:
    print(i)

Submission status: Runtime Error

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, id): self.to, self.id = to, id

def main():
    N = Z()
    col = [0] * (N-1)
    G = collections.defaultdict(list)
    for i in range(N-1):
        a, b = ZZ()
        G[a].append(edge(b, i))
        G[b].append(edge(a, i))
    numCol = 0
    for i in range(1, N+1): numCol = max(numCol, len(G[i]))

    def dfs(v):
        colSet = set()
        for ed in G[v]:
            if col[ed.id] != 0: colSet.add(col[ed.id])
        c = 1
        for ed in G[v]:
            if col[ed.id] != 0: continue
            while c in colSet: c += 1
            col[ed.id] = c
            c += 1
            dfs(ed.to)

    dfs(1)
    print(numCol)
    for i in range(N-1): print(col[i])

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)] # 隣接リスト
e=[ set() for _ in range(N)] #その頂点につながる辺に存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
    
for j in d:
    maxi=max(maxi,len(j))  #最大の色数が確定する

possible=set( i+1 for i in range(maxi) )

for i in range(N-1):
  tmp=set()
  tmp |= possible
  tmp -= e[a[i]-1]
  tmp -= e[b[i]-1]
  c[i]=tmp.pop()
  e[a[i]-1].add(c[i])
  e[b[i]-1].add(c[i])
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)] # 隣接リスト
e=[ set() for _ in range(N)] #その頂点につながる辺に存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
    
for j in d:
    maxi=max(maxi,len(j))  #最大の色数が確定する
pos=set([i+1 for i in range(maxi)])

for i in range(N-1):
    tmp= pos- e[a[i]-1] -e[b[i]-1]
    col=tmp.pop()
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)] # 隣接リスト
e=[ set() for _ in range(N)] #その頂点につながる辺に存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
    
for j in d:
    maxi=max(maxi,len(j))  #最大の色数が確定する
for i in range(N-1):
    pos=set([i+1 for i in range(maxi)])
    pos= pos- e[a[i]-1] -e[b[i]-1]
    col=pos.pop()
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)] # 接続
e=[ set() for _ in range(N)] #その頂点につながる辺に存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
    
for j in d:
    maxi=max(maxi,len(j))  #最大の色数が確定する
for i in range(N-1):
    pos=set([i+1 for i in range(maxi)])
    pos= pos- e[a[i]-1] -e[b[i]-1]
    col=min(pos)
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if vc[v1][v2] == -1:
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[v1][v2] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[v1][v2])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop as p
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
m=max(map(lambda x:len(x),T))
print(m)
def f(Q):
    R=[]
    for q in Q:
        H=list(range(1,m+1))
        for t in T[q[0]]:
            x=p(H)
            if x==q[1]:
                x=p(H)
            C[t[1]]=x
            if len(T[t[0]])!=0:
                R.append([t[0],x])
    if len(R)!=0:
        return f(R)
f([[0,0]])
for c in C:
    print(c)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop as p
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
m=max(map(lambda x:len(x),T))
print(m)
def f(Q):
    R=[]
    for q in Q:
        H=list(range(1,m+1))
        for t in T[q[0]]:
            x=p(H)
            if x==q[1]:
                x=p(H)
            C[t[1]]=x
            if len(T[t[0]])!=0:
            	R.append([t[0],x])
    if len(R)!=0:
    	return f(R)
f([[0,0]])
for c in C:
    print(c)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop as p
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
m=max(map(lambda x:lem(x),T))
def f(Q):
    R=[]
    for q in Q:
        H=list(range(1,m))
        for t in T[q[0]]:
            x=p(H)
            if x==q[1]:
                x=p(H)
            C[t[1]]=x
            if len(T[t[0]])!=0:
            	R.append([t[0],x])
    if len(R)!=0:
    	return f(R)
f([[0,0]])
print(max(C))
for c in C:
    print(c)

Submission status: Runtime Error

Solution code:
def f(u, i, d, t, vis):
    if vis[u]:
        return
    vis[u] = True
    z = t[u]

    c = 1
    for v in z:
        if vis[v]:
            continue
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t, vis)
        c += 1


def main():
    from collections import defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        t[j].append(i)
        m.append([i, j])
    d = defaultdict(dict)
    vis = [False for _ in range(n + 1)]
    f(1, len(t[1]) + 1, d, t, vis)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t)) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def f(u, i, d, t):
    z = t[u]
    c = 1
    for v in z:
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t)
        c += 1


def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        i, j = min(i, j), max(i, j)
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    f(1, len(t[1]) + 1, d, t)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        i, j = min(i, j), max(i, j)
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        c = 1
        for v in z:
            if c == i:
                c += 1
            d[u].update({v: c})
            f(v, c)
            c += 1

    f(1, len(t[1]) + 1)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        c = 1
        for v in z:
            if c == i:
                c += 1
            d[u].update({v: c})
            f(v, c)
            c += 1

    f(m[0][0], len(t[m[0][0]]) + 1)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        l = len(z)
        r = list(range(1, i)) + list(range(i + 1, l + 2))
        for v, j in zip(z, r):
            d[u].update({v: j})
            f(v, j)

    f(m[0][0], len(t[m[0][0]]) + 1)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        l = len(z)
        s = set(range(1, l + 2)) - {i}
        r = list(s)
        r.sort()
        for v, j in zip(z, r):
            d[u].update({v: j})
            f(v, j)

    f(m[0][0], len(t[m[0][0]]) + 1)

    if t.count([]) == n:
        print(n - 1)
    else:
        print(max(len(i) for i in t) + 1)

    for (u, v) in m:
        print(d[u][v])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    al = [[] for _ in range(n)]
    e = [(-1, -1) for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = [int(j) - 1 for j in read().split()]
        al[a].append(b)
        al[b].append(a)
        e[i] = (a, b)
    k = max(map(len, al))
    print(k)
    c = [{i + 1 for i in range(k)} for _ in range(n)]
    for i in range(n - 1):
        a, b = e[i]
        ci = min(c[a] & c[b])
        print(ci)
        c[a].remove(ci)
        c[b].remove(ci)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for _ in range(n)]
dic = {}

for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    dic[(a - 1, b - 1)] = 0
check = [False for _ in range(n)]

max_color = 0

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        if pos < next_pos:
            dic[(pos, next_pos)] = color
        else:
            dic[(next_pos, pos)] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

print(max_color)
for _, i in dic.items():
    print(i)

Submission status: Runtime Error

Solution code:
    #初期入力
    import sys
    input = sys.stdin.readline
    import heapq
    N = int(input())
    connection   ={i:set() for i in range(1,N+1)}
    A            =[i for i in range(N-1)]
    for i in range(N-1):
        a,b = (int(x) for x in input().split())
        connection[a].add(b) # つながりを逆向きも含めて入力
        connection[b].add(a) # 
        A[i] =a,b            #色を出力するため
     
    #色の数(各頂点の最大値)
    color_max =0
    root =0
    for i,v in connection.items():
        if color_max < len(v) :
            color_max =len(v)
            root =i         #枝が一番多い所を根 ⇒スタート
     
    #各頂点に色を準備⇒辺の色決定
    aa=[]
    color =0                                 #辺に塗る色の候補
    node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
    edge ={}
    for a,b in A:
        edge[(a,b)] =-1                   #辺の色 -1で初期化
    now_set =set() #=start
    now_set.add(root) #=start
    next =set()
    next_next =set()
    passed ={i:False for i in range(1,N+1)}
    count =0
    while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
        for now in now_set: #幅優先探索
            next =connection[now]
            for nex_2 in next:
                count =0
                if node[now] !=[]:
                    color =node[now][-1] +1
                while count < color_max:
                    q,color =divmod(color,color_max)
                    if color not in node[now] and color not in node[nex_2]:
                        n1,n2=0,0
                        if now > nex_2:
                            n1,n2 =nex_2,now
                        else:
                            n1,n2 =now,nex_2
                        edge[(n1,n2)] =color +1  #辺の色決定
                        node[now]   .append(color)
                        node[nex_2] .append(color)
                        passed[now] =True
                        #colored     =connection[nex_2] - passed
                        if passed[nex_2] ==False:
                            next_next.add(nex_2)  #つながっている頂点（次に探索する）
                        passed[nex_2] =nex_2
                        color   +=1
                        count   +=1
                        break
                    else:
                        color +=1
                        count +=1
        now_set     .clear()
        now_set     |=next_next
        next_next   .clear()
        
    #出力
    print(color_max)
    for i in A:
        print(edge[i])

Submission status: Runtime Error

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)

def bfs_graph(start, G):
    from collections import deque
    # 隣接リストを食わせる
    color_set = set(range(1, color_num + 1))
    color = [color_set for _ in range(N)]
    ans = {}
    dist = [-1] * N
    que = deque([start])
    dist[start] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
            c = (color[v]&color[w]).pop()
            # print(c, color[v], color[w])
            color[v].discard(c)
            color[w].discard(c)
            ans[(v, w)] = c
            ans[(w, v)] = c
    return ans
ans = bfs_graph(0, graph)

for ab in ablist:
    try:
        print(ans[tuple(ab)])
    except KeyError:
        print(ans[tuple(ab[::-1])])

Submission status: Runtime Error

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

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

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

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

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

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

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

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

Submission status: Runtime Error

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)
color_set = set(range(1, color_num + 1))
color = [set() for _ in range(N)]
for a, b in ablist:
    ac = color[a]
    bc = color[b]
    c = (color_set - (ac | bc)).pop()
    ac.add(c)
    bc.add(c)
    print(c)