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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def colorize(current_node, adjacents, colors, from_color, k):
    
    print(current_node)
    # そのノードから繋がるエッジを辿っていく
    count = 0
    for edge, node in adjacents[current_node]:

        # 既に塗られていたら無視
        if colors[edge]!=None:
            continue
        
        count += 1
        colors[edge] = (from_color+count)%k
        colorize(node, adjacents, colors, colors[edge], k)
     
N = int(input())
adjacents = {i+1:[] for i in range(N)}

for i in range(N-1):
    a,b = [int(e) for e in input().split(" ")]
    
    adjacents[a].append( [i+1,b] )
    adjacents[b].append( [i+1,a] )

# 一番隣接エッジ数が多いノード
most_edge =sorted(adjacents, key=lambda d:len(adjacents[d]))[-1]
k = len(adjacents[most_edge])

colors = {i+1:None for i in range(N-1)}
colorize(1, adjacents, colors, -1, k)

print(k)
for color in colors.values():
    print(color+1)

Submission status: Wrong Answer

Solution code:
print("Hello")

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    ab = [LI() for _ in range(n-1)]
    d = collections.defaultdict(set)
    r = []
    for a,b in ab:
        i = 1
        while i in d[a] or i in d[b]:
            i += 1
        d[a].add(i)
        d[b].add(i)
        r.append(i)

    return JA([max(r)] + r, "\n")


print(main())

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = len(edge[0])
    for i in range(1, N): K = max(K, len(edge[i]))
    
    par = [-1] * N
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        par[nowNode] = parentNode
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                while colPointer == col[parentNode] or colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

cols = {i:[] for i in range(N)}
ABcol = []
col_max = -float('inf')
for a,b in AB:
  for i in range(1,N-1+1):
    if i not in cols[a] and i not in cols[b]:
      ABcol.append(i)
      cols[a].append(i)
      cols[b].append(i)
      col_max = max(col_max,i)
      break

print(col_max)
[print(col) for col in ABcol]

Submission status: Wrong Answer

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

col_num = max([num for num in cnt_e.values()])
print(col_num)
cols = {i:[] for i in range(N)}
for a,b in AB:
  for i in range(1,col_num+1):
    if i not in cols[a] and i not in cols[b]:
      print(i)
      cols[a].append(i)
      cols[b].append(i)
      break

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    # G = [[0] * (n-1) for i in range(2)]
    cnt = [0] * n
    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))
        cnt[a-1] += 1
        cnt[b-1] += 1


    # for i in range(n-1):
    #     a,b = map(int, input().split())
    #     G[0][i] = a-1
    #     G[1][i] = b-1
    #     cnt[a-1] += 1
    #     cnt[b-1] += 1
    num = 0
    # print(G)
    print(max(cnt))

    tmp_clr = [0] * (n-1)
    tmp_edge = [0] * n

    # print(G)
    for frm, child in enumerate(G):
        clr = 1
        for j, to  in enumerate(child):

            if tmp_edge[frm] == clr or tmp_edge[to[0]] == clr:
                clr += 1
            tmp_clr[to[1]] = clr
            tmp_edge[frm] = clr
            tmp_edge[to[0]] = clr

    # print(tmp_edge)
    # print(tmp_clr)
    print('\n'.join(map(str, tmp_clr)))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
 
N, *AB = map(int, open(0).read().split())
B = AB[1::2]
 
E = [[] for _ in range(N)]
for a, b in zip(*[iter(AB)] * 2):
    E[a-1].append(b-1)

Q = deque([0])
C = [0] * (N)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += c == C[v]
        C[u] = c
        Q.append(u)

print(max(C)+1)
for b in B:
    print(C[b-1]+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict({0:-1})
for x, y in edges:
    tree[x-1].append(y-1)
    colors[y-1] = -1

queue = deque([0])
while queue:
    v0 = queue.popleft()
    c0, c1 = colors[v0], 0
    for v1 in tree[v0]:
        c1 += c0 == c1
        colors[v1] = c0 = c1
        queue.append(v1)

colors = list(colors.values())[1:]
print(max(colors)+1)
for c in colors:
    print(c+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append((x-1, y-1))
    colors[(x-1, y-1)] = -1

queue, c0 = deque([(-1, 0)]), -1
while queue:
    c1, e0 = 0, queue.popleft()
    for e1 in tree[e0[1]]:
        c1 += c1 == c0
        colors[e1] = c0 = c1
        queue.append(e1)

print(max(colors.values())+1)
for c in colors.values():
    print(c+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append((x-1, y-1))
    colors[(x-1, y-1)] = -1

queue, colors[(0, 1)] = deque(tree[0]), 0
while queue:
    c, e0 = 0, queue.popleft()
    for e1 in tree[e0[1]]:
        c += c == colors[e0]
        colors[e1] = c
        queue.append(e1)
        e0 = e1

print(max(colors.values())+1)
for c in colors.values():
    print(c+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append((x-1, y-1))
    colors[(x-1, y-1)] = -1

queue, colors[(0, 1)] = deque([(0, 1)]), 0
while queue:
    c, e0 = 0, queue.popleft()
    for e1 in tree[e0[1]]:
        c += c == colors[e0]
        colors[e1] = c
        queue.append(e1)
        e0 = e1

print(max(colors.values())+1)
for c in colors.values():
    print(c+1)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    G = [[0] * (n-1) for i in range(2)]
    cnt = [0] * n
    for i in range(n-1):
        a,b = map(int, input().split())
        G[0][i] = a-1
        G[1][i] = b-1
        cnt[a-1] += 1
        cnt[b-1] += 1
    num = 0
    # print(G)
    print(max(cnt))

    tmp_clr = [0] * (n-1)

    for i in range(n-1):
        clr = 1
        for j in range(i):
            if G[0][j] == G[0][i] or G[1][j] == G[0][i] or G[0][j] == G[1][i] or G[1][j] == G[1][i]:
                if tmp_clr[j] == clr:
                    clr += 1
        tmp_clr[i] = clr
    print('\n'.join(map(str, tmp_clr)))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    G = [[0] * (n-1) for i in range(2)]
    cnt = [0] * n
    for i in range(n-1):
        a,b = map(int, input().split())
        G[0][i] = a-1
        G[1][i] = b-1
        cnt[a-1] += 1
        cnt[b-1] += 1
    num = 0
    print(G)
    print(max(cnt))

    tmp_clr = [0] * (n-1)

    for i in range(n-1):
        clr = 1
        for j in range(i):
            if G[0][j] == G[0][i] or G[1][j] == G[0][i] or G[0][j] == G[1][i] or G[1][j] == G[1][i]:
                if tmp_clr[j] == clr:
                    clr += 1
        tmp_clr[i] = clr
    print('\n'.join(map(str, tmp_clr)))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
print(max([len(i) for i in graph]))
cnt = [0 for i in range(n+1)]
ng = [0 for i in range(n+1)]
for a,b in ab:
    if parent[a] == b:
        p = b
        c = a
    else:
        p = a
        c = b
    cnt[p] += 1
    if parent[p] == 1:
        ng[1] += 1
    if cnt[p] == ng[p]:
        cnt[p] += 1
    if p == 1:
        x = ng[1]+1
        ng[1] = x
    else:
        x = cnt[p]
    ng[c] = x
    print(x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
print(max([len(i) for i in graph]))
cnt = [0 for i in range(n+1)]
ng = [0 for i in range(n+1)]
for a,b in ab:
    if parent[a] == b:
        p = b
        c = a
    else:
        p = a
        c = b
    cnt[p] += 1
    if parent[p] == 1:
        ng[1] += 1
    if cnt[p] == ng[p]:
        cnt[p] += 1
    if p == 1:
        x = ng[1]+1
    else:
        x = cnt[p]
    ng[c] = x
    print(x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
print(max([len(i) for i in graph]))
cnt = [0 for i in range(n+1)]
ng = [0 for i in range(n+1)]
for a,b in ab:
    if parent[a] == b:
        p = b
        c = a
    else:
        p = a
        c = b
    cnt[p] += 1
    if cnt[p] == ng[p]:
        cnt[p] += 1
    ng[c] = cnt[p]
    print(cnt[p])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

P=[-1 for i in range(N+1)]
P[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(N):
    if len(Q)==i:
        break
    P[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if P[j]==-1:
            Q.append([j,Q[i][0]])
#print(P)
C=[-1 for i in range(N+1)]
C[1]=1
#print(Q[1][0])
#print(P[3])
cnt=1
p=0
for i in range(N-1):
   if p!=Q[i][1]:
       p=Q[i][1]
       cnt=1
       for j in range(cnt,10**9):
           if j!= C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt=j+1
               break
   else:
       for j in range(cnt,10**9):
           if j!=C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt = j+1
               break
print(max(C))
for i in range(2,N+1):
    print(C[i])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

P=[-1 for i in range(N+1)]
P[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(N):
    if len(Q)==i:
        break
    P[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if P[j]==-1:
            Q.append([j,Q[i][0]])
#print(P)
C=[-1 for i in range(N+1)]
C[1]=1
#print(Q[1][0])
#print(P[3])
cnt=1
p=0
for i in range(N-1):
   if p!=Q[i][1]:
       p=Q[i][1]
       cnt=1
       for j in range(cnt,10**9):
           if j!= C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt=j+1
               break
   else:
       for j in range(cnt,10**9):
           if j!=C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt = j+1
               break
print(max(C))
for i in range(1,N+1):
    print(C[i])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

P=[-1 for i in range(N+1)]
P[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(N):
    if len(Q)==i:
        break
    P[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if P[j]==-1:
            Q.append([j,Q[i][0]])
#print(P)
C=[-1 for i in range(N+1)]
C[1]=1
#print(Q[1][0])
#print(P[3])
cnt=1
p=0
for i in range(N-1):
   if p!=Q[i][1]:
       p=Q[i][1]
       cnt=1
       for j in range(cnt,10**9):
           if j!= C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt=j+1
               break
   else:
       for j in range(cnt,10**9):
           if j!=C[Q[i][1]]:
               C[Q[i][0]]=j
               cnt = j+1
               break
#print(C)
for i in range(1,N+1):
    print(C[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [0] * n
x = list()
for i in range(n - 1):
    a, b = map(int, input().split())
    for j in range(n):
        if a == j + 1:
            l[j] = l[j] + 1
            c = l[j]
        elif b == j + 1:
            l[j] = l[j] + 1
            d = l[j]
    x.append(max(c, d))
print(max(l))
for i in range(n - 1):
    print(x[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for j, (u, i) in enumerate(next_v):
        # 親と色がかぶったら+1
        if j+1 == c_p:
            cnt += 1
        # すでに彩色されている辺はダメ
        if ans[i] > 0:
            # print("aaa")
            continue
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for j, (u, i) in enumerate(next_v):
        # 親と色がかぶったら+1
        if j+1 == c_p:
            cnt += 1
        # すでに彩色されている辺はダメ
        if ans[i] > 0:
            # print("aaa")
            continue
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納

import sys
sys.setrecursionlimit(1000000)
from collections import deque


#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        self.edge.sort()
        checkedge=deque()
        for edge in self.edge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
                
        while checkedge:
            edge=checkedge.popleft()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Submission status: Wrong Answer

Solution code:
#%%
def dfs_deep_measure(st, n, reach, color):
    ans_list = [[0, 0, 0, 0] for i in range(n)]
    # check, color, last_point, this_point
    stack = [st]
    ans_list[st][0] = 1
    ans_list[st][1] = -1
    ans_list[st][2] = -1
    ans_list[st][3] = st
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        c = ans_list[tmp][1]
        for i in tmp_list:
            if ans_list[i][0] != 1:
                stack.append(i)
                ans_list[i][0] = 1
                c += 1
                ans_list[i][1] = c % color
                ans_list[i][2] = tmp
                ans_list[i][3] = i
    return ans_list

n = int(input())
a, b = [0] * n, [0] * n
reach = [[] for _ in range(n)]
for i in range(n-1):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())
    reach[a[i]].append(b[i])
    reach[b[i]].append(a[i])

st = -1
color = -1
for i in range(n):
    if len(reach[i]) > color:
        color = len(reach[i])
        st = i

#print(st, n, reach, color)
#print(dfs_deep_measure(st, n, reach, color))

ans_list = dfs_deep_measure(st, n, reach, color)

ans = [[0, 0] for _ in range(n)]
for i in range(len(ans_list)):
    if ans_list[i][2] == -1: continue
    tmp = ans_list[i][2] * 10 + ans_list[i][3]
    tmp2 = ans_list[i][1] + 1
    ans[i] = [tmp, tmp2]
ans.sort()

#print(ans)

print(color)
for i in range(n):
    if i == 0:
        pass
    else:
        print(ans[i][1])

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(1000000)



#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.edge=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
collist=[i.color for i in tre]
n=tree.node_n
for i in range(1,n):
    print(collist[i])

Submission status: Wrong Answer

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納



import sys
sys.setrecursionlimit(1000000)

#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self):
        self.tree=[]
        self.edge=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.tree
collist=[i.color for i in tre]
n=tree.node_n
for i in range(1,n):
    print(collist[i])

Submission status: Wrong Answer

Solution code:
#辺の順に処理．各nodeがどの色の辺と隣接しているかの情報をlistに持っておく
N = int(input())
A = [None]*(N-1)
B = [None]*(N-1)
c_list = [[None] for _ in range(N)]
ans=[]
K=0

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

for i  in range(N-1):
    for j in range(N-1):
        if j in c_list[A[i]-1] or j in c_list[B[i]-1]:
            continue
        else:
            ans.append(j)
            c_list[A[i]-1].append(j)
            c_list[B[i]-1].append(j)
            if j>K:
                K=j
            break

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

Submission status: Wrong Answer

Solution code:
n = int(input())
col = [[] for _ in range(n+1)] # 隣接する辺の持つ色を記録

k = 1
max_k = 1
ans = []
for i in range(n-1):
    a, b = map(int, input().split())
    k = 1
    while True:
        if k in col[a] or k in col[b]:
            k += 1
        else:
            col[a].append(k)
            col[b].append(k)
            ans.append(k)
            if k > max_k:
                max_k = k
            break
print(max_k)
for i in range(n-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
col = [[] for _ in range(n+1)] # 隣接する辺の持つ色を記録

k = 1
max_k = 1
ans = []
for i in range(n-1):
    a, b = map(int, input().split())
    k = 1
    while True:
        if k in col[a] or k in col[b]:
            k += 1
        else:
            col[a].append(k)
            col[b].append(k)
            ans.append(k)
            if k > max_k:
                max_k = k
            break
print(k)
for i in range(n-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]  # N頂点
for _ in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree[a].append(b)
    # tree[b].append(a)

colors = [-1] * N

q = deque([0])

while len(q) != 0:
    v = q.popleft()
    color = 1
    for e in tree[v]:
        if colors[e] != -1:
            continue
        if color == colors[v]:
            color += 1
        colors[e] = color
        color += 1
        q.append(e)
print(max(colors))
for c in colors[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]  # N頂点
for _ in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree[a].append(b)
    # tree[b].append(a)

colors = [-1] * N

q = deque([0])

while len(q) != 0:
    v = q.popleft()
    color = 1
    for e in tree[v]:
        if color == colors[v]:
            color += 1
        colors[e] = color
        color += 1
        q.append(e)
print(max(colors))
for c in colors[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]  # N頂点
for _ in range(N-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree[a].append(b)
    # tree[b].append(a)

colors = [-1] * N

q = deque([0])

while len(q) != 0:
    v = q.pop()
    color = 1
    for e in tree[v]:
        if color == colors[v]:
            color += 1
        colors[e] = color
        color += 1
        q.append(e)
print(max(colors))
for c in colors[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(pow(10, 7))


N = int(input())
G = [[] for _ in range(N)]
e = []
ans = []
# bとして振られる番号
d_col = [0] * N
# b先に振り分ける番号
e_col = [1] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    if d_col[a-1] == e_col[a-1]:
        ans.append(e_col[a-1]+1)
        e_col[a-1] += 1
    else:
        ans.append(e_col[a-1])
    d_col[b-1] = e_col[a-1]
    e_col[a-1] += 1
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
class node:
    def __init__(self):
        self.p = 9999999
        self.c = 0

N = int(input())
nodeList = [node() for _ in range(N + 2)]
ansList = [0 for _ in range(N-1)] 

for i in range(N-1):
    a, b = map(int, input().split(" "))
    nodeList[a-1].c += 1
    if nodeList[a-1].c < nodeList[a-1].p:
        ansList[i] = nodeList[a-1].c
    else:
        ansList[i] = nodeList[a-1].c + 1
    nodeList[b-1].p = ansList[i]

print(max(ansList))
for a in ansList:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
C = [[i for i in range(1,K+1)] for j in range(N+1)]
import copy 
w = copy.deepcopy(W)
d = [[0 for i in range(N+1)] for j in range(N+1)]
w.sort()
for i in range(N-1):
    a,b = W[i]
    print(d[a][b])