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:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge = dd(list)
for i in range(n-1):
    a, b = map(int, input().split())
    edge[i] = [a, b]

color_record = [0] * (n - 1)
color_num = 1

node_color = dd(set)
for i in range(n-1):
    node1, node2 = edge[i]
    for color in range(1, color_num+1):
        if color not in node_color[node1] and color not in node_color[node2]:
            break
    else:
        color_num += 1
        color = color_num
    node_color[node1].add(color)
    node_color[node2].add(color)
    color_record[i] = color

print(color_num)
for color in color_record:
    print(color)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge = dd(list)
for i in range(n-1):
    a, b = map(int, input().split())
    edge[i] = [a, b]
    tree[a].add(b)
    tree[b].add(a)

color_record = [0] * (n - 1)
color_num = 1
colors = set(list(range(1, color_num+1)))

node_color = dd(set)
for i in range(n-1):
    node1, node2 = edge[i]
    for color in range(1, color_num+1):
        if color not in node_color[node1] and color not in node_color[node2]:
            break
    else:
        color_num += 1
        color = color_num
    node_color[node1].add(color)
    node_color[node2].add(color)
    color_record[i] = color

print(color_num)
print(*color_record, sep="\n")
print()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge = dd(list)
for i in range(n-1):
    a, b = map(int, input().split())
    edge[i] = [a, b]
    tree[a].add(b)
    tree[b].add(a)

color_record = [0] * (n - 1)
color_num = max([len(val) for val in tree.values()])
print(color_num)
colors = set(list(range(1, color_num+1)))

node_color = dd(set)
for i in range(n-1):
    node1, node2 = edge[i]
    for color in colors:
        if color not in node_color[node1] and color not in node_color[node2]:
            break
    node_color[node1].add(color)
    node_color[node2].add(color)
    color_record[i] = color

print(*color_record, sep="\n")
print()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
routings = [[] for _ in range(N+1)]
colors = [0 for _ in range(N+1)]

for _ in range(N-1):
  a, b = map(int, input().split())
  routings[a].append(b)
  routings[b].append(a)
  
edges = deque([1])
colors[1] = 0
answer = 0
while len(edges) > 0:
  edge = edges.pop()
  color = colors[edge]
  nc = 1
  answer = max(answer, len(routings[edge]))
  for ne in routings[edge]:
    if colors[ne] == 0 and ne != 1:
      if nc == color:
        nc += 1
      colors[ne] = nc
      edges.append(ne)
      nc += 1
print(answer)
for color in colors[2:]:
  print(color)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
routings = [[] for _ in range(N+1)]
colors = [0 for _ in range(N+1)]

for _ in range(N-1):
  a, b = map(int, input().split())
  routings[a].append(b)
  routings[b].append(a)
  
edges = deque([1])
colors[1] = 1
answer = 0
while len(edges) > 0:
  edge = edges.pop()
  color = colors[edge]
  nc = 1
  answer = max(answer, len(routings[edge]))
  for ne in routings[edge]:
    if colors[ne] == 0:
      if nc == color:
        nc += 1
      colors[ne] = nc
      edges.append(ne)
      nc += 1
print(answer)
for color in colors[1:N]:
  print(color)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True
        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = min(residual)
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)

    return edge_colors


edge_colors = bfs(tree, 0)

[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [set() for i in range(n)]
bc = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  bc.append([b,c])

edge = [0 for i in range(10**5+1)]
g = [set() for i in range(10**5+1)]
ans = []
z = 0
for i in range(n-1):
  x,y = bc[i][0],bc[i][1]
  edge[x] += 1
  if edge[x] in g[x]:
    edge[x] += 1
  if edge[x] in g[y]:
    edge[x] += 1
  ans.append(edge[x])
  z = max(z,edge[x])
  g[y].add(edge[x])
  g[x].add(edge[x])
print (z)
for i in ans:
  print (i)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [set() for i in range(n)]
bc = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  bc.append([b,c])

edge = [0 for i in range(10**5+1)]
g = [set() for i in range(10**5+1)]
ans = []
z = 0
for i in range(n-1):
  x,y = bc[i][0],bc[i][1]
  edge[x] += 1
  if edge[x] in g[x] or edge[x] in g[y]:
    edge[x] += 1
  ans.append(edge[x])
  z = max(z,edge[x])
  g[y].add(edge[x])
  g[x].add(edge[x])
print (z)
for i in ans:
  print (i)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [set() for i in range(n)]
bc = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  bc.append([b,c])

edge = [0 for i in range(10**5+1)]
g = [set() for i in range(10**5+1)]
ans = []
z = 0
for i in range(n-1):
  x,y = bc[i][0],bc[i][1]
  edge[x] += 1
  if edge[x] in g[x]:
    edge[x] += 1
  #print (edge[x])
  ans.append(edge[x])
  z = max(z,edge[x])
  g[y].add(edge[x])
print (z)
for i in ans:
  print (i)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

# ub = 0
# for point in path:
#     ub = max(len(point), ub)

def make_tree(tree):
    count = [1]*(N+1)
    for i in range(N-1):
        a = ab[i][0]
        b = ab[i][1]
        tree[i] = max(count[a], count[b])
        count[a] += 1
        count[b] += 1
    return max(count) - 1

# lb = 0 # 絶対不可能
# ub = N # 絶対可能

# while ub - lb > 1:
#     tree = list()
#     mid = (ub + lb) // 2
#     if make_tree(mid, tree):
#         ub = mid
#     else:
#         lb = mid

tree = [0]*(N-1)
print(make_tree(tree))

# print(ub)

for x in tree:
    print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
e=[]
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
    e.append(str(x-1)+str(y-1))
par=[-1]*n #自分の親と何番でつながっているか
visited=[0]*n
visited[0]=1
que=deque([0])
ans=dict()
m=0
while que:
    now=que.popleft()
    color=1
    for i in edge[now]:
        if visited[i]:
            continue
        visited[i]=1
        que.append(i)
        if color==par[now]:
            color+=1
        par[i]=color
        ans[str(min(i,now))+str(max(i,now))]=color
        color+=1
    m=max(m,color-1)
print(m)
for i in e:
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
e=[]
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
    e.append(str(x-1)+str(y-1))
par=[-1]*n #自分の親と何番でつながっているか
visited=[0]*n
visited[0]=1
que=deque([0])
ans=dict()
while que:
    now=que.popleft()
    color=1
    for i in edge[now]:
        if visited[i]:
            continue
        visited[i]=1
        que.append(i)
        if color==par[now]:
            color+=1
        par[i]=color
        ans[str(min(i,now))+str(max(i,now))]=color
        color+=1
print(max(ans.values()))
for i in e:
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N=intput()
c=[0]*(N+1)
for i in range(N):
    c[i+1]=set()
ans=[]
for _ in range(N-1):
    u,v=mint()
    for i in range(1,N+1):
        if i not in c[u] and i not in c[v]:
            c[u].add(i)
            c[v].add(i)
            ans.append(i)
            break
print(max(ans))
lprint(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-09-15 20:31:44 +0900
# LastModified: 2020-09-15 21:26:50 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    N = int(input())
    path = [[0] for _ in range(N+1)]
    ans = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        flag = 0
        path_max = max(max(path[a]), max(path[b]))
        for i in range(1, path_max):
            if i not in path[a] and i not in path[b]:
                color_num = i
                path[a].append(color_num)
                path[b].append(color_num)
                flag = 1
                break
        if flag == 0:
            color_num = path_max+1
            path[a].append(color_num)
            path[b].append(color_num)
        ans.append(color_num)
#        print(path)
    print(max(ans))
    for a in ans:
        print(a)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-09-15 20:31:44 +0900
# LastModified: 2020-09-15 21:22:51 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    N = int(input())
    path = [[0] for _ in range(N+1)]
    ans = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        flag = 0
        for i in range(1, max(max(path[a]), max(path[b]))+1):
            if i not in path[a] and i not in path[b]:
                color_num = i
                path[a].append(color_num)
                path[b].append(color_num)
                flag = 1
                break
        if flag == 0:
            color_num = max(max(path[a]), max(path[b]))+1
            path[a].append(color_num)
            path[b].append(color_num)
        ans.append(color_num)
#        print(path)
    print(max(ans))
    for a in ans:
        print(a)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, n, before, bcol, ans):
    col = 1
    if n==2:
        return
    for i, j in tree[n]:
        if i == before:
            continue
        if col == bcol:
            col += 1
        ans[j] = col
        dfs(t, i, n, col, ans)
        col += 1
            
n = int(input())
t = [[] for _ in range(n)]
line = [0]*n
for i in range(n-1):
    a, b = map(int,input().split())
    t[a-1].append((b-1,i))
    t[b-1].append((a-1,i))
    line[a-1] += 1
    line[b-1] += 1
num = max(line)
print(num)
ans = [0]*(n-1)
dfs(t,0,-10,-10,ans)
for i in range(n-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
ans = [-1] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  #graph[a - 1].append(b - 1)
  #graph[b - 1].append(a - 1) 
  A, B = a - 1, b - 1
  now = 1
  #print(A, B, graph)
  while (now in graph[A]) or (now in graph[B]):
    now += 1
  ans[i] = now
  graph[A].append(now)
  graph[B].append(now)
  #print(graph)
  
print(max(ans))
for i in range(N - 1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
E = [0] * (N - 1)
ans = [-1] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  #graph[a - 1].append(b - 1)
  #graph[b - 1].append(a - 1) 
  E[i] = [a - 1, b - 1]
#print(graph)

for i in range(N - 1):
  now = 1
  A, B = E[i][0], E[i][1]
  #print(A, B, graph)
  while (now in graph[A]) or (now in graph[B]):
    now += 1
  ans[i] = now
  graph[A].append(now)
  graph[B].append(now)
  #print(graph)
  
print(max(ans))
for i in range(N - 1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
E = [0] * (N - 1)
ans = [-1] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  #graph[a - 1].append(b - 1)
  #graph[b - 1].append(a - 1) 
  E[i] = [a - 1, b - 1]
#print(graph)

for i in range(N - 1):
  now = 1
  A, B = E[i][0], E[i][1]
  #print(A, B, graph)
  while (now in graph[A]) or (now in graph[B]):
    now += 1
  ans[i] = now
  graph[A].append(now)
  graph[B].append(now)
  #print(graph)
print(max(ans))
for i in range(N - 1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from sys import stdin

def getval():
    n = int(input())
    e = [[i] + list(map(int,stdin.readline().split())) for i in range(n-1)]
    return n,e

def main(n,e):
    tree = [[] for i in range(n)]
    ans = [0 for i in range(n-1)]
    for i in e:
        tree[i[1]-1].append([i[2]-1,i[0]])
        tree[i[2]-1].append([i[1]-1,i[0]])
    k = 0
    for i in tree:
        n = 1
        used = []
        for j in i:
            #print(j)
            if ans[j[1]]:
                used.append(ans[j[1]])
                continue
            while n in used:
                n += 1
            ans[j[1]] = n 
            n += 1
        k = max(n-1,k)

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

if __name__=="__main__":
    n,e = getval()
    main(n,e)

Submission status: Wrong Answer

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


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

for i in range(N):
    to[i].sort()


def solve():
    dist = [-1] * N
    # 頂点iに向かう辺をiとする
    color = [0] * N
    dist[0] = 0
    color[0] = 0
    que = deque([0])

    while que:
        v = que.popleft()
        used_color = [color[v]]
        next_color = 1
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                while next_color in used_color:
                    next_color += 1
                color[nv] = next_color
                used_color.append(next_color)
                que.append(nv)

    print(len(set(color[1:])))
    print(*color[1:], sep='\n')


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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


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


def solve():
    dist = [-1] * N
    # 頂点iに向かう辺をiとする
    color = [0] * N
    dist[0] = 0
    color[0] = 0
    que = deque([0])

    while que:
        v = que.popleft()
        used_color = [color[v]]
        next_color = 1
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                while next_color in used_color:
                    next_color += 1
                color[nv] = next_color
                used_color.append(next_color)
                que.append(nv)

    print(len(set(color[1:])))
    print(*color[1:], sep='\n')


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input=sys.stdin.readline
n=int(input())
vertices=defaultdict(list)
ans=[0]*(n-1)
Max=0
for aa in range(n-1):
    i,j=map(int,input().split())
    k=1
    while (k in vertices[i]) or (k in vertices[j]):
        k+=1
    vertices[i].append(k)
    vertices[j].append(k)
    Max=max(Max,k)
    ans[aa]=str(k)

print(Max)
print('\n'.join(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

w = [0] * n
c = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)
    w[a] += 1
    w[b] += 1

s = w.index(max(w))
d = dict()

e = [0] * n
l = [[0] * n for _ in range(n)]
q = deque()
q.append((s, 0))
while q:
    f, v = q.pop()
    e[f] = 1
    j = 1
    for i in c[f]:
        if e[i] == 0:
            if j == v:
                j += 1
            q.appendleft((i, j))
            d[str(min(f, i)+1) + str(max(f, i)+1)] = j
            j += 1

print(max(d.values()))
for i in ab:
    print(d[''.join(list(map(str, i)))])

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=[-1]*(N-1)
rootLine=[0]*N
numLine=[0]*N
l=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l.append([a,b,i])
l.sort()
print(l)

for a,b,i in l:
  numLine[a]+=1
  if numLine[a]==rootLine[a]:
    numLine[a]+=1
  ans[i]=numLine[a]
  rootLine[b]=numLine[a]

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

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=[-1]*(N-1)
rootLine=[0]*N
numLine=[0]*N

for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  numLine[a]+=1
  if numLine[a]==rootLine[a]:
    numLine[a]+=1
  ans[i]=numLine[a]
  rootLine[b]=numLine[a]
print(max(ans))
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
edge_colors = [0]*(N-1)
colors_used = [0]*(N)
for edge_idx, (a, b) in enumerate(ab):
    color_ab = colors_used[a - 1] | colors_used[b - 1]
    i = 1
    i2 = 1
    while color_ab & i2 != 0:
        i += 1
        i2 = i2 << 1
    colors_used[a - 1] += i2
    colors_used[b - 1] += i2
    edge_colors[edge_idx] = i
print(max(edge_colors))
for c in edge_colors:
    print(c)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
edge_colors = [0]*(N-1)
colors_used = [0]*(N)
for edge_idx, (a, b) in enumerate(ab):
    color_ab = colors_used[a - 1] | colors_used[b - 1]
    i = 1
    i2 = 1
    while color_ab & i2 != 0:
        i += 1
        i2 *= 2
    colors_used[a - 1] += i2
    colors_used[b - 1] += i2
    edge_colors[edge_idx] = i
print(max(edge_colors))
for c in edge_colors:
    print(c)

Submission status: Wrong Answer

Solution code:
# 木なので親から繋がっている1辺のみ色が塗られている状態(根に限っては何も塗られていない)

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

g = dict()
for i, (a, b) in enumerate(AB):
    a, b = a-1, b-1
    if a not in g:
        g[a] = set()
    if b not in g:
        g[b] = set()
    g[a].add((b, i))
    g[b].add((a, i))

col = [-1]*N
col[0] = 0
e_col = [-1]*(N-1)

q = [0]
while q:
    par = q.pop()
    par_col = col[par]

    c = 0
    for child, e_i in g[par]:
        if col[child] != -1:
            continue
        while c == par_col:
            c += 1
        e_col[e_i] = c
        col[child] = c
        c += 1
        q.append(child)

# print(e_col)

print(max(e_col)+1)
for e_col_i in e_col:
    print(e_col_i+1)

Submission status: Wrong Answer

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

from collections import deque

q = deque()
color = [0]*n
q.append(0)
while q:
    cur = q.popleft()
    c = 1
    for nx in G[cur]:
        if color[cur] == c:
            c += 1
        color[nx] = c
        c += 1
        q.append(nx)

print(max(color))
for i in range(1,len(color)):
    print(color[i])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)

class Tree():
    def __init__(self, n, root, connects):
        self.root = root
        self.connects = connects
        self.parents = [0] * n
        self.parents[root] = None
        self.children = [0] * n
        self.children[self.root] = connects[self.root]
        self.make_tree(self.root)

    def make_tree(self, node):
        for child in self.children[node]:
            self.parents[child] = node
            self.children[child] = [c for c in self.connects[child] if c != node]
            if self.children[child] != []:
                self.make_tree(child)


def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    t = Tree(n, root = 0, connects = G)
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = set()):
        color = list(set(range(m)) - pre)
        for b in t.children[a]:
            c = color.pop()
            ans[ID[a][b]] = c
            bfs(b, set([c]))
    bfs(0)
    [print(a) for a in ans]
      
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[[] for _ in range(n)]
kumi=[]
for _ in range(n-1):
  s=list(map(int,input().split()))
  kumi.append(s)
  r[s[0]-1].append(s[1]-1)
  r[s[1]-1].append(s[0]-1)
  
ans=0
for i in range(n):
  ans=max(len(r[i]),ans)
  
iro=[[0 for _ in range(ans)] for _ in range(n)]

print(ans)

for i in range(n-1):
  d=kumi[i][0]-1
  e=kumi[i][1]-1
  for j in range(1,ans+1):
    if iro[d][j-1]==0 and iro[e][j-1]==0:
      ans1=j
      iro[d][j-1]=1
      iro[e][j-1]=1
      break
  print(ans1)

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[[] for _ in range(n)]
kumi=[]
for _ in range(n-1):
  s=list(map(int,input().split()))
  kumi.append(s)
  r[s[0]-1].append(s[1]-1)
  r[s[1]-1].append(s[0]-1)
  
ans=0
for i in range(n):
  ans=max(len(r[i]),ans)
  
iro=[[0 for _ in range(ans)] for _ in range(n)]

print(ans)

for i in range(n-1):
  d=kumi[i][0]-1
  e=kumi[i][1]-1
  for j in range(1,ans+1):
    if iro[d][j-1]==0 and iro[e][j-1]==0:
      ans1=j
      iro[d][j-1]=1
      iro[e][j-1]=1
      break
  print(ans1)

Submission status: Wrong Answer

Solution code:

from collections import deque
def resolve():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)

    q = deque()
    q.append(0)
    color = [0] * N
    while q:
        v = q.popleft()
        parentC = color[v]
        c = 1
        for to in G[v]:
            if c == parentC:  # 親と同じ色だったら次の色を使用
                c += 1
            color[to] = c
            c += 1
            q.append(to)

    print(max(color))
    print(*color[1:], sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
iro=[[False]*(n+1) for i in range(n+1)]
next=[0]+[1]*(n)
ans=[]
for i in range(1,n):
    a,b=map(int, input().split())
    if next[a]==next[b]:
        ans.append(next[a])
        iro[a][next[a]]=True
        iro[b][next[b]]=True
        next[a]+=1
        next[b]+=1
    else:
        for j in range(max(next[a],next[b]),n+1):
            if iro[a][j]==False and iro[b][j]==False:
                ans.append(j)
                iro[a][j]=True
                iro[b][j]=True
                break

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])
k = max([len(i) for i in g])
print(k)
c = [set() for i in range(n)]
for a,b in ab:
    for i in range(1,k+1):
        if not i in c[a] and not i in c[b]:
            c[a].add(i)
            c[b].add(i)
            print(i)
            break

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])
k = max([len(i) for i in g])
print(k)
c = [[] for i in range(n)]
for a,b in ab:
    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

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
AB = inpll(n-1)

cnt = [0]*(n+1)
tmp = [[] for _ in range(n+1)]
ans = []
for a,b in AB:
    for i in range(1,n+1):
        if tmp[a].count(i) == 0 and tmp[b].count(i) == 0:
            color = i
            break
    ans.append(color)
    tmp[a].append(color)
    tmp[b].append(color)

print(max(map(len,tmp)))
for aa in ans:
    print(aa)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
AB = inpll(n-1)

cnt = [0]*(n+1)
ans = []
for a,b in AB:
    ans.append(max(cnt[a]+1,cnt[b]+1))
    cnt[a] += 1
    cnt[b] += 1

print(max(cnt))
for aa in ans:
    print(aa)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    n = int(input().strip())
    edges = [[int(i) for i in input().strip().split()] for _ in range(n - 1)]
    p_edge_color = [set() for _ in range(n + 1)]
    g = defaultdict(list)
    for a, b in edges:
        g[a].append(b)
    _max = 0
    for nodes in g.values():
        _max = max(len(nodes) + 1, _max)
    print(_max)
    for a, b in edges:
        for i in range(1, _max + 1):
            if i not in p_edge_color[a] and i not in p_edge_color[b]:
                p_edge_color[a].add(i)
                p_edge_color[b].add(i)
                print(i)
                break
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [[] for i in range(n)]
ans = []
cnt = 0

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for j in range(1, n + 1):
        if j not in dp[a] and j not in dp[b]:
            ans.append(j)
            if j > cnt:
                cnt = j
            dp[a].append(j)
            dp[b].append(j)
            break

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