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

n=[ [0] for _ in range(N+1)]
m=[]

def set_pairs(a,b):
    n[a].append(b)
    n[b].append(a)

def set_color(a,b):
    for i in range(N):
        if not (i in n[a] or i in n[b]):
            n[a].append(i)
            n[b].append(i)
            return i
            break
        
for i in range(N-1):
    a,b=map(int,input().split())
    m.append(set_color(a,b))

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

Submission status: Wrong Answer

Solution code:
n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
import queue
q = queue.Queue()
q.put(0)
ma = 0
while not q.empty():
    nord = q.get()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.put(value)
        ma = idx+offset+1
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

Submission status: Wrong Answer

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

first_ans=max(node)
print(first_ans)
for i in range(n-1):
    temp=memo[i]
    a=int(temp[0])
    b=int(temp[1])
    print(max(node[a],node[b]))
    node[a]-=1
    node[b]-=1

Submission status: Wrong Answer

Solution code:

from collections import deque, defaultdict

N = int(input())

connect_dic = defaultdict(list)

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

    connect_dic[a].append(b)
    connect_dic[b].append(a)


dq = deque([])
dq.append(a)

color_dic = defaultdict(set)
used_set = set()

comp = defaultdict(int)
max_ = 0

while dq:
    n = dq.popleft()
    can = connect_dic[n]
    l = len(can)
    max_ = max(max_, l)

    a_color = color_dic[n]
    for c in can:

        b_color = color_dic[c]
        for i in range(l):
            if i not in a_color and i not in b_color:
                color_dic[n].add(i)
                color_dic[c].add(i)

                comp[(n, c)] = i
                comp[(c, n)] = i

                break

        if c not in used_set:
            dq.append(c)

    used_set.add(n)


print(max_)
for a, b in edge:
    print(comp[(a, b)] + 1)

Submission status: Wrong Answer

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

#辺の定義
#辺E(u,v)の重みがw
l = []
for i in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [0]
color[0] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      i += 1
#各頂点の色を出力
print(max(color))
for i in range(1,N):
  print(color[i])

Submission status: Wrong Answer

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

#辺の定義
#辺E(u,v)の重みがw
l = []
for i in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  if i == 0:
  	start = u
  if v == start:
  	l.append(u)
  else:
  	l.append(v)
  E[u].append(v)
  E[v].append(u)

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [start]
color[start] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      i += 1
#各頂点の色を出力
print(max(color))
for i in range(N-1):
  print(color[l[i]])

Submission status: Wrong Answer

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

#辺の定義
#辺E(u,v)の重みがw
for i in range(N-1):
  u,v = map(int,input().split())
  if i == 0:
  	start = u
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [start-1]
color[start-1] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      i += 1
#各頂点の色を出力
print(max(color))
for i in range(1,N):
  print(color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    g = [[] for _ in range(N)]
    # edge_order = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append((i, b))
        # edge_order.append(b)
    # print(edge_order)
    # 頂点1からBFS
    queue = deque([0])
    color = [0] * N
    while queue:
        v = queue.popleft()
        c = 1  # 色の初期値は一からスタート
        for i, u in g[v]:
            if c == color[v]:  # 親と色が同じ時
                c += 1
            color[u] = c
            c += 1
            queue.append(u)
    print(max(color))
    # print('####')
    for i in color:
        if i ==0: continue
        print(i)
    # print('####')
    # for i in edge_order:
    #     print(color[i])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

#辺の定義
#辺E(u,v)の重みがw
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [0]
bad = 0
color[0] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      i += 1
#各頂点の色を出力
print(max(color))
for i in range(1,N):
  print(color[i])

Submission status: Wrong Answer

Solution code:
N=int(input())
edges=[]
for i in range(0,N-1):
  a,b=map(int,input().split())
  edges.append([a,b])
list=[]
for i in range(0,N):
  list.append(0)
for i in range(0,N-1):
  list[edges[i][0]-1]=list[edges[i][0]-1]+1
  list[edges[i][1]-1]=list[edges[i][1]-1]+1
K=max(list)
print(K)
allowedcolour=[]
for i in range(0,N):
  allowedcolour.append([])
  for j in range(0,K):
    allowedcolour[i].append(0)
for i in range(0,N-1):
  for j in range(0,K):
    if allowedcolour[edges[i][0]-1][j]==0 and allowedcolour[edges[i][1]-1][j]==0:
      allowedcolour[edges[i][0]-1][j]=1
      allowedcolour[edges[i][1]-1][j]=1
      print(j+1)
      break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ 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
            print(p_col)
            dfs(u, v, col) #u;調べる頂点 v;直前に調べた辺で、調べる頂点と結ばれている頂点　col;直前に調べた辺の色番号
            col += 1 #最深部まで調べたら デフォルトの色=最後に調べた辺の色+1とする
            #最深部に繋がった辺の色+1してやれば、次の辺の色は必ず条件を満たしてくれる

dfs()
print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n)]

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

q = deque([0])
par = [0] * n
color = [-1] * n

while q:
    x = q.pop()
    ng = color[x]
    c = 1
    for y in g[x]:
        if y == par[x]:
            continue
        if c == ng:
            c += 1
        par[y] = x
        color[y] = c
        c += 1
        q.append(y)

print(max(color))
print("\n".join(map(str, color[1:])))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
n=int(input())
edge=np.array(list(list(map(int,input().split())) for _ in range(n-1)))
color=np.zeros(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=[]
  seen=[]
  for i in range(n-1):
    if s in edge[i]:
      e=edge[i][edge[i]!=s]
      if color[i]==0:
        d.append(e[0])
        check.append(i)
      else:
        seen.append(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(x), color))))

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappush, heappop
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

graph = [[] for _ in range(n)]
edge = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edge[(a, b)] = i
    edge[(b, a)] = i

def bfs(graph, start, n):
    visited = [-1] * n
    que = deque()
    color = [0] * (n - 1)
    visited[start] = 0
    que.append(start)
    while que:
        node = que.popleft()
        c = 1
        for e in graph[node]:
            if visited[e] < 0:
                if visited[node] == c:
                    c += 1
                visited[e] = c
                color[edge[(e, node)]] = c
                que.append(e)
                c += 1
    return color

r = bfs(graph, 0, n)
ans = max(r)
for k in r:
    print(k)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = mylistinput(n-1)

g = [ [] for _ in range(n) ]
for i in range(n-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

color = [-1] * n

def bfs(g):
    used_color = [ [-1] ]*n
    q = deque()
    q.append([0,0])
    while q:
        tmp = q.popleft()
        v = tmp[0]
        c = tmp[1]
        color[v] = c
        ls_nc = list(reversed(list(range(1,len(g[v])+1))))
        if c==0:
            pass
        elif c in ls_nc:
            ls_nc.remove(c)
        else:
            pass
        for nv in g[v]:
            if color[nv]!=-1:
                pass
            else:
                nc = ls_nc.pop()
                q.append([nv,nc])
    return True

if bfs(g):
    for i in range(n):
        if i==0:
            print(max(color))
        else:
            print(color[i])
else:
    print("Error")

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = mylistinput(n-1)

g = [ [] for _ in range(n) ]
for i in range(n-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
print(g)

color = [-1] * n

def bfs(g):
    used_color = [ [-1] ]*n
    q = deque()
    q.append([0,0])
    while q:
        tmp = q.popleft()
        v = tmp[0]
        c = tmp[1]
        color[v] = c
        ls_nc = list(reversed(list(range(1,len(g[v])+1))))
        if c==0:
            pass
        elif c in ls_nc:
            ls_nc.remove(c)
        else:
            pass
        for nv in g[v]:
            if color[nv]!=-1:
                pass
            else:
                nc = ls_nc.pop()
                q.append([nv,nc])
    return True

if bfs(g):
    for i in range(n):
        if i==0:
            print(max(color))
        else:
            print(color[i])
else:
    print("Error")

Submission status: Wrong Answer

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

m=max(vertex)
print(m)

color=list(range(1,m+1))
Color=[-1 for i in range(n)]
for [A,B] in edges:
  idx=(Color[A]+1)%m
  Color[A]=idx
  Color[B]=idx
  print(color[idx])

Submission status: Wrong Answer

Solution code:
n=int(input())
tree=[[] for i in range(n)]
vertex=[0]*n
edges=[]
for i in range(n-1):
  a,b=map(int,input().split())
  tree[a-1].append(b-1)
  edges.append(a-1)
  vertex[a-1]+=1
  vertex[b-1]+=1

edges=list(set(edges))  

m=max(vertex)
print(m)

color=list(range(1,m+1))
Color=[-1 for i in range(n)]
for i in edges:
  idx=(Color[i]+1)%m
  l=len(tree[i])
  for j in range(l):
    print(color[idx])
    Color[tree[i][j]]=idx
    idx+=1
    idx%=m

Submission status: Wrong Answer

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

color=list(range(1,m+1))
Color=[-1 for i in range(n)]
for i in range(n-1):
  idx=(Color[i]+1)%m
  l=len(tree[i])
  for j in range(l):
    print(color[idx])
    Color[tree[i][j]]=idx
    idx+=1
    idx%=m

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    # ab = []
    # ans = {}
    ans = []
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        # ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for node in path[pre]:
            if visited[node]:
                continue
            
            if c == k:
                k += 1
            visited[node] = True
            # ans[(pre, node)] = k
            ans.append(k)
            que.append((node, k))
            k += 1
            

    # print(max(ans.values()))
    print(max(ans))
    print('\n'.join(list(map(str, ans))))
    """for key in ab:
        print(ans[key])"""

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
        ab.append(str(a-1)+str(b-1))
    
    que = deque([(0, 0)])
    while que:
        # k = 1
        k = 0
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            k += 1
            if c == k:
                k += 1
            visited[next_node] = True
            ans[str(pre)+str(next_node)] = k
            que.append((next_node, k))
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
        ab.append(str(a-1)+str(b-1))
    
    K = max([len(g) for g in path])
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            visited[next_node] = True
            if c == k:
                k += 1
            ans[str(pre)+str(next_node)] = k
            que.append((next_node, k))
            k += 1

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
        ab.append(str(a-1)+str(b-1))
    
    K = max([len(g) for g in path])
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            visited[next_node] = True
            if c == k:
                k += 1
            ans[str(pre)+str(next_node)] = k
            que.append((next_node, k))
            k += 1

    print(K)
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    ans = [i for _, _, i in init]
    while que:
        c = 1
        p, node, color = que.popleft()
        next_nodes = edges[node]        
        for next_node in next_nodes:
            if next_node == p:
                continue
            if c == color:
                c += 1
            ans.append(c)
            que.append([node, next_node, c])
            c += 1

    print(K)
    for v in ans:
      print(v)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    ans = [i for _, _, i in init]
    while que:
        c = 1
        p, node, color = que.popleft()
        next_nodes = edges[node]        
        for next_node in next_nodes:
            if next_node == p:
                continue
            if c == color:
                c += 1
            ans.append(c)
            que.append([node, next_node, c])
            c += 1

    print(K)
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    ans = [i for _, _, i in init]
    while que:
        c = 1
        p, node, color = que.popleft()

        next_nodes = edges[node]
        next_nodes.remove(p)
        
        for i in range(len(next_nodes)):
            if c == color:
                c += 1
            ans.append(c)
            que.append([node, next_nodes[i], c])
            c += 1

    print(K)
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    ans = [i for _, _, i in init]
    while que:
        c = 1
        p, node, color = que.popleft()
        if c == color:
            c += 1

        next_nodes = edges[node]
        next_nodes.remove(p)
        
        for i in range(len(next_nodes)):
            ans.append(c)
            que.append([node, next_nodes[i], c])
            c += 1

    print(K)
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    colors = set([i for i in range(1, K+1)])
    ans = [i for _, _, i in init]
    while que:
        p, node, color = que.popleft()
        next_nodes = edges[node]
        next_nodes.remove(p)
        next_colors = list(colors - set([color]))
        
        for i in range(len(next_nodes)):
            ans.append(next_colors[i])
            que.append([node, next_nodes[i], next_colors[i]])

    print(K)
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
    
    init = [[node, i+1] for i, node in enumerate(sorted(edges[0]))]
    que = deque(init)
    colors = set([i for n, i in init])
    ans = [i for n, i in init]
    while que:
        node, color = que.popleft()
        if node >= N-1:
            continue
        colors.add(color)

        next_nodes = edges[node]
        next_nodes.sort()
        next_colors = list(colors - set([color]))
        while len(next_colors) < len(next_nodes):
            color += 1
            next_colors.append(color)
                
        for i in range(len(next_nodes)):
            ans.append(next_colors[i])
            que.append([next_nodes[i], next_colors[i]])

    print(max(ans))
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
    
    init = [[node, i+1] for i, node in enumerate(edges[0])]
    que = deque(init)
    ans = [i for n, i in init]
    colors = set(ans)
    while que:
        node, color = que.popleft()
        if node >= N-1:
            continue
        colors.add(color)
        next_nodes = edges[node]
        next_colors = list(colors - set([color]))
        while len(next_colors) < len(next_nodes):
            color += 1
            next_colors.append(color)
                
        for i in range(len(next_nodes)):
            ans.append(next_colors[i])
            que.append([next_nodes[i], next_colors[i]])

    print(max(ans))
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
used = [[0] for i in range(n)]
k = 1
ans = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tmp = 0
  for tmp in range(1,k+2):
    if not tmp in used[a] and not tmp in used[b]:
      break
  ans[i] = tmp
  k = max(k, tmp)
  used[a].append(tmp)
  used[b].append(tmp)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
used = [[0] for i in range(n)]
k = 1
ans = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tmp = 0
  for tmp in range(1,k+1):
    if not tmp in used[a] and not tmp in used[b]:
      break
  ans[i] = tmp
  k = max(k, tmp)
  used[a].append(tmp)
  used[b].append(tmp)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
used = [[0] for i in range(n)]
k = 0
ans = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tmp = 0
  for tmp in range(1,max(a,b)+2):
    if not tmp in used[a] and not tmp in used[b]:
      break
  ans[i] = tmp
  k = max(k, tmp)
  used[a].append(tmp)
  used[b].append(tmp)

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

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])
    #tunagari.setdefault(ab[0], []).append(ab[1])


# 　最小の色数（根の辺の数）
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 =[] #　色の一時的な変数
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_list =[i for i in range(1,color_max+1) ]
    for ii in v:
        #if (ii,k) not in color_ten_ten.keys():
        if col_sumi[k] & set(color_list) :
            set(color_list).discard(col_sumi[k]) # 覚えていた色を消す
        elif col_sumi[ii] & set(color_list):    
            set(color_list).discard(col_sumi[ii]) # 覚えていた色を消す
        xx = color_list.pop() # ポップだから速度のため末尾から消す  
        if k < ii:
            color_ten_ten.setdefault((k,ii) ,xx)  
        else:
            color_ten_ten.setdefault((ii,k) ,xx)  
        col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
        col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    ba =tuple(i[::-1])
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

Submission status: Wrong Answer

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari = {}
tunagari_kazoeyou ={}
for ab in AB:
    tunagari_kazoeyou.setdefault(ab[0], []).append(ab[1])
    tunagari_kazoeyou.setdefault(ab[1], []).append(ab[0])
    tunagari.setdefault(ab[0], []).append(ab[1])


# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari_kazoeyou.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 =[] #　色の一時的な変数
from collections import defaultdict
col_sumi= defaultdict(int)

for k,v in tunagari.items():
    color_list =[i for i in range(1,color_max+1) ]
    for ii in v:
        #if (k,ii) not in color_ten_ten.keys():
        if col_sumi[k] in color_list:
            color_list.remove(col_sumi[k])
            #print(color_list,col_sumi[k])
        xx = color_list.pop() # ポップだから速度のため末尾から消す  
        color_ten_ten.setdefault((k,ii) ,xx)  
        col_sumi[ii] =xx # 頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    ba =tuple(i[::-1])
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])
    elif ba in color_ten_ten.keys():
        print(color_ten_ten[ba])

Submission status: Wrong Answer

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari = {}
tunagari_kazoeyou ={}
for ab in AB:
    tunagari_kazoeyou.setdefault(ab[0], []).append(ab[1])
    tunagari_kazoeyou.setdefault(ab[1], []).append(ab[0])
    tunagari.setdefault(ab[0], []).append(ab[1])


# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari_kazoeyou.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 =[] #　色の一時的な変数
from collections import defaultdict
col_sumi= defaultdict(int)

for k,v in tunagari.items():
    color_list =[i for i in range(1,color_max+1) ]
    for ii in v:
        #if (k,ii) not in color_ten_ten.keys():
        if col_sumi[k] in color_list:
            color_list.remove(col_sumi[k])
            #print(color_list,col_sumi[k])
        xx = color_list.pop() # ポップだから速度のため末尾から消す  
        color_ten_ten.setdefault((k,ii) ,xx)  
        col_sumi[ii] =xx # 頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys():
        print(color_ten_ten[ab])