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:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari = {}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え　最小の色数（根の辺の数）


color_list =[i for i in range(1,color_max+1)]
#頂点とつながり先をキー、色をValueの辞書
color_moto ={i:color_list for i in tunagari.keys()} 
color_ten_ten = {}
col =[] #　色の一時的な変数
for k,v in tunagari.items():
    color =[]
    color.extend(color_moto[k])
    for ii in v:
        #print(color,end=" ")
        if (k,ii) not in color_ten_ten.keys():
            xx = color.pop() # ポップだから速度のため末尾から消す  
            #print(xx,end="  ")
            color_ten_ten.setdefault((k,ii) ,xx)  
            color_ten_ten.setdefault((ii,k) ,xx)
            print(color_ten_ten[(k,ii)])       
        # 辞書から取り出す→消す→辞書に戻す(後の検索先)        
            col.extend(color_moto[ii]) 
            col.remove(xx)
            #print(col)
            color_moto[ii] = col
            col=[]

Submission status: Wrong Answer

Solution code:
n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append((b-1, i))
  adj[b-1].append((a-1, i))
max_degree = 0
for i in range(n):
  degree = len(adj[i])
  if degree > max_degree:
    root = i
    max_degree = degree
color = [[] for _ in range(n)]
edge = [0] * (n - 1)
queue = [root]
parent = [root] * n
while queue:
  vertex = queue.pop()
  c = 1
  for v, i in adj[vertex]:
    if parent[vertex] == v:
      continue
    while c in color[v]:
      c += 1
    color[v].append(c)
    edge[i] = c
    queue.append(v)
    parent[v] = vertex
    c += 1
print(max_degree)
for c in edge:
  print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = [0]*(n)
a = [0,0]
for i in range(n-1):
    b = list(map(int,input().split()))
    if b[0] in a or b[1] in a:
        ans[i+1] = ans[i] + 1
    else :
        ans[i+1] = 1
    a = b
    if ans[0] < ans[i+1]:
        ans[0] = ans[i+1]
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for i in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append((i, v-1))
    edge[v-1].append((i, u-1))

ans[0] = 1
check = [0]*n
check[0] = 1
for i in range(n):
    color = 1
    for j, k in edge[i]:
        if check[k]: continue
        if ans[j-1] == color: color += 1
        ans[j] = color
        check[k] = 1
        color += 1
        
print(max(ans))
for i in ans: print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
input_list = []
for _ in range(n-1):
    input_list.append(list(map(int, input().split())))
input_list.sort(key=lambda x:x[0])
for u, v  in input_list:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

ans[0] = 1
parents = [-1]*n
que = deque([[0, 0]])
while que:
    a, b = que.popleft()
    color = 1
    for i in edge[a]:
        if parents[a] == i:
            continue
        if color == b:
            color += 1
        ans[i-1] = color
        parents[i] = a
        que.append([i, color])
        color += 1
print(max(ans))
for i in ans: print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for _ in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

ans[0] = 1
parents = [-1]*(n+1)
que = deque([[0, 0]])
while que:
    a, b = que.popleft()
    color = 1
    for i in edge[a]:
        if parents[a] == i: continue
        if color == b:
            color += 1
        ans[i-1] = color
        parents[i] = a
        que.append([i, color])
        color += 1
        
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for _ in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

ans[0] = 1
check = [0]*n
check[0] = 1
for i in range(n):
    color = 1
    for j in edge[i]:
        if check[j]:
            continue
        if ans[i-1] == color:
            color += 1
        ans[j-1] = color
        check[j] = 1
        color += 1
        
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for _ in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)

ans = [0]*(n-1)
ans[0] = 1
for i in range(n):
    color = 1
    for j in edge[i]:
        if ans[i-1] == color:
            color += 1
        ans[j-1] = color
        color += 1
        
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
#tempt

n=int(input())
graph=[[]for _ in range(n)]
ans=[1]*(n-1)
for i in range(n-1):
    x,y=map(int,input().split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

count=0
for i in range(n):
    count=max(count,len(graph[i]))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = [0]*(n-1)
    next_node = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        node[i] = (a-1, b-1)
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [1]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = k
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[value]:
                continue
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            for sub in next_node[value]:
                if already[sub]:
                    continue
                not_yet.append(sub)
                already[sub] = True
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = []
    next_node = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        node.append((a-1, b-1))
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [0]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = 1
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[value]:
                continue
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            for sub in next_node[value]:
                if already[sub]:
                    continue
                not_yet.append(sub)
                already[sub] = True
    
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = []
    next_node = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        node.append((a-1, b-1))
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [0]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = 1
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if value == 0:
                continue
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            for sub in next_node[value]:
                if already[sub]:
                    continue
                not_yet.append(sub)
                already[sub] = True
    
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = []
    next_node = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        node.append((a-1, b-1))
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [[False]*n for _ in range(n)]
    parent = [0]*n
    ans_list = dict()
    k = 1
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        already[0][value] = True
        already[value][0] = True
        parent[value] = 1
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[key][value] or already[value][key]:
                continue
            already[key][value] = True
            already[value][key] = True
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            for sub in next_node[value]:
                if already[sub][value] or already[value][sub]:
                    continue
                not_yet.append(sub)
    
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_d
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[]*n for _ in range(n)]

  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)

  colors=[0]*n
  colors[0]=1
  q=collections.deque()
  q.append((0,1))

  cnt=1
  while q:
    a,c=q.popleft()

    color=1
    for b in edges[a]:
      if colors[b]!=0:
        continue

      if color==c:
        color+=1

      colors[b]=color
      cnt=max(cnt,color)
      q.append((b,color))

      color+=1

  print(cnt)
  for x in colors[1:]:
    print(x)

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[]*n for _ in range(n)]

  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)

  colors=[0]*n
  colors[0]=1
  q=collections.deque()
  q.append((0,1))

  while q:
    a,c=q.popleft()

    color=1
    for b in edges[a]:
      if color==c:
        color+=1

      if colors[b]!=0:
        continue

      colors[b]=color
      q.append((b,color))

      color+=1

  for x in colors:
    print(x)

main()
# print(main())

Submission status: Wrong Answer

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

vc=[0] * n
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        if vc[p] == c:
            color += 1
        vc[c] = color
        ec[i] = color
        color += 1
        

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
colors = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
    key = str(a) + '+' + str(b)
    colors[key] = 0
stack = deque([[edges[1], 0, 1]])
max_col = 1
while stack:
    nodes, used_color, idx = stack.pop()
    cur_color = 1
    for n in nodes:
        a, b = min(idx, n), max(idx, n)
        key = str(a) + '+' + str(b)
        if colors[key] != 0: continue
        if cur_color == used_color: cur_color += 1
        colors[key] = cur_color
        stack.append([edges[n], cur_color, n])
        max_col = max(max_col, cur_color)
        cur_color += 1
print(max_col)
for c in colors.values():
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
n=int(input())
E=[[] for _ in range(n)]
col=defaultdict(list)
l=[]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
  col[(a,b)]=-1
  col[(b,a)]=-1
  l.append((a,b))
s=-1
k=-1
for i in range(n):
  if len(E[i])>k:
    k=len(E[i])
    s=i
par=[-1]*n
stack=deque([s])
while stack:
  u=stack.pop()
  if u==s:
    cnt=1
  else:
    cnt=col[(par[u],u)]
  for v in E[u]:
    if col[(u,v)]==-1:
      par[v]=u
      if cnt<=k:
        col[(u,v)]=cnt
        cnt+=1
      else:
        col[(u,v)]=1
        cnt=2
      stack.append(v)
print(k)
for a,b in l:
  if col[(a,b)]==-1:
    print(col[(b,a)])
  else:
    print(col[(a,b)])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = []
mem = {}
for i in range(1,N):
  mem[i] = 0
for _ in range(N-1):
  a,b = map(int,input().split())
  graph.append((a,b))
e = [0]*(N-1)
color = 0
no_color = 0
pre_node = graph[0][0]

for i in range(N-1):
  node = graph[i][0]
  if node == pre_node:
    color += 1
  else:
    color = 1
    
  if color == mem[node]:
    color += 1
    
  e[i] = color
  mem[graph[i][1]]=color
  pre_node = node

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = [list(map(int, readline().split())) for i in range(n - 1)]
gragh = [[] for j in range(n + 1)]
for a, b in ab:
    gragh[a].append(b)
    gragh[b].append(a)
root = 1
parent = [0] * (n + 1)
stack = [root]
order = []

while stack:
    x = stack.pop()
    order.append(x)
    for y in gragh[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
color = [-1] * (n + 1)

for x in order:
    ng = color[x]
    cnt = 1
    for y in gragh[x]:
        if y == parent[x]:
            continue
        if cnt == ng:
            cnt += 1
        color[y] = cnt
        cnt += 1

ans = []
append = ans.append
for a, b in ab:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(ans))
print('/n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()

 
def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        pp = paths.popleft    # 定数倍高速化への道のり
        pa = paths.append    # 定数倍高速化への道のり
        while paths:
            # current_path = paths.popleft()
            current_path = pp()    # 定数倍高速化への道のり
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            current_color = 0
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                if v != previous:
                    # tmp = current_path[:]
                    tmp = current_path[-1:]    # 定数倍高速化への道のり
                    tmp.append(v)
                    pa(tmp)    # 定数倍高速化への道のり
                    current_color += 1
                    if current_color == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    # color[v][u] = current_color    # 定数倍高速化への道のり
            max_branch = max(max_branch, count)
        return max_branch
 
 
    n = ii()
    adj = [[] for _ in range(n)]
 
    # L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]    # 定数倍高速化への道のり
    L = [None] * (n-1)   # 定数倍高速化への道のり
    for i in range(n-1):
        L[i] = tuple(map(lambda x: int(x)-1, input().rstrip().split()))
 
    for pair in L:
        a, b = pair
        adj[a].append(b)
        # adj[b].append(a)
    
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        while paths:
            # print(paths)
            current_path = paths.popleft()
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                current_color = count
                if v != previous:
                    tmp = current_path[:]
                    tmp.append(v)
                    paths.append(tmp)
                    if current_path == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    color[v][u] = current_color
            max_branch = max(max_branch, count)
        return max_branch

    n = ii()
    adj = [[] for _ in range(n)]
    L = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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


color = [ [0]*N for _ in range(N)]
q = deque()
c = 1
for i in T[0]:
    color[0][i] = c
    c += 1
    q.append(i)
total = c
parent = 0

while(len(q) > 0):
    c = 1
    r = q.popleft()
    k = color[parent][r]
    for j in T[r]:
        if c != k:
            color[r][j] = c
            color[j][r] = c
        else:
            c += 1
            color[r][j] = c
            color[j][r] = c
        c += 1
        q.append(r)
        q.append(j)

    total = max(total,c-1)
    if len(q) != 0:
        parent = q.popleft()

print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    adj = [[] for _ in range(n)]
    order = []
    for a,b in ab:
        adj[a-1].append(b-1)
        order.append(b-1)

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)

    c = [0]*n
    d = deque([0])
    while d:
        v = d.popleft()
        cnt = 1
        for nv in adj[v]:
            if c[v] == cnt:
                cnt += 1
            c[nv] = cnt
            cnt += 1
            d.append(nv)

    for i in order:
        print(c[i])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

color = [ [0]*N for _ in range(N)]
total = 0
for i in range(N):
    for j in T[i]:
        if color[j][i] == 0:
            k = []
            c = 0
            for s in T[i]:
                k.append(color[i][s])
            while(True):
                if c not in k:
                    break
                c += 1
            color[i][j] = c
            color[j][i] = c
            total = max(total,c)
print(c)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    adj = [[] for _ in range(n)]
    for a,b in ab:
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)


    # c = [[0]*n for _ in range(n)]
    # visited = [0]*n
    # def dfs(node):
    #     visited[node] = 1
    #     color = 1
    #     for nextnode in adj[node]:
    #         if visited[nextnode]:
    #             continue
    #         c[node][nextnode] = color
    #         dfs(nextnode)
    #         color += 1


    c = [[] for _ in range(n)]
    for a,b in ab:
        a -= 1
        b -= 1
        for i in range(1, k+1):
            if not i in c[a] and not i in c[b]:
                c[a].append(i)
                c[b].append(i)
                print(i)
                break





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    adj = [[] for _ in range(n)]
    for a,b in ab:
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)

    c = [1]*n
    for a,b in ab:
        a -= 1
        b -= 1
        print(max(c[a], c[b]))
        c[a] += 1
        c[b] += 1
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)]
AB = [lr() for _ in range(N-1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [(root, 0)]
color = [0] * (N+1)
# 頂点と、親方向の辺を対応させる
while stack:
    cur, ng = stack.pop()
    c = 1
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        if c == ng:
            c += 1
        parent[next] = cur
        color[next] = c
        c += 1
        stack.append((next, c))

answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])

print(max(answer))
print(*answer, sep='\n')
# 02

Submission status: Wrong Answer

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1
"""
dfs(0,-1,-1)
print(max(L))
for l in L:
  print(l)
"""

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c in color_used[i]:
            c += 1
        color_used[i].add(c)
        color_used[j].add(c)
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
g = []

def A(v,u):
    for i in range(1, n):
        if l2[v].count(i) == 0 and l2[u].count(i) == 0:
            l2[v].append(i)
            l2[u].append(i)
            return i



l2 = [[] for _ in range(n)]

ans = []

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

print(max(ans))

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [ [] for _ in range(N) ]

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

S = [ [0] for _ in range(N) ]
for i in range(N):
    P = []
    for k in A[i]:
        P.append(S[k][0])
    j = 1
    while(True):
        if j not in P:
            S[i].remove(0)
            S[i].append(j)
            print(j)
            break
        j += 1