Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def main():
    N = int(input())
    tree = []
    colors = []
    [tree.append([]) for x in range(N)]

    for _ in range(N-1):
        a, b = map(int, input().split())
        for i in range(1, 10**5+1):
            if i in tree[a-1] or i in tree[b-1]:
                continue

            tree[a-1].append(i)
            tree[b-1].append(i)
            colors.append(i)
            break

    print(len(set(colors)))

    for c in colors:
        print(c)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

colors = [0]*(N-1)

d = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    d[a-1].append((b-1, i))
    d[b-1].append((a-1, i))

visited = [0]*N
visited[0] = 1
q = [0]
while q:
    t = q.pop()

    ad = 0
    for i, (x, index) in enumerate(d[t]):
        if visited[x]:
            continue
        if colors[t] == i+1:
            ad += 1
        colors[index] = i+1 + ad 
        q.append(x)
        visited[x] = 1

print(max(colors))
for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
vertexes = []
number_list = [0]*100000

for i in range(n-1):
    a, b = map(int, input().split())
    number_list[a-1] += 1
    number_list[b-1] += 1
    vertexes.append(max(number_list[a-1], number_list[b-1]))

print(max(vertexes))

for vertex in vertexes:
    print(vertex)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
#print(l)
aa=[[] for _ in range(n)]
#aa[l[0][0]-1].append(1)
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    #print(d,q)
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    for k in range(1,n):
                        if k not in aa[i] and k not in aa[j]:
                            aa[j].append(k)
                            aa[i].append(k)
                            break
        q=q1
        c+=1
        #print(aa,d,q)
    return d


pt=[[] for _ in range(n)]
for i in range(n-1):
    pt[l[i][0]-1].append(l[i][1]-1)
    pt[l[i][1]-1].append(l[i][0]-1)
#print(pt)
ans=bfs(l[0][0]-1)
#print(aa)
A=0
for i in range(n):
    A=max(A,max(aa[i]))
print(A)
for i in range(n-1):
    print(aa[l[i][0]-1][0])
    aa[l[i][0]-1]=aa[l[i][0]-1][1:]
    aa[l[i][1]-1]=aa[l[i][1]-1][1:]

Submission status: Wrong Answer

Solution code:
# TLE? 
N = int(input())
T = [[]for i in range(N)]
Eo = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    Eo.append((a-1,b-1))
Eo = tuple(Eo)
K = 0
for i in range(N):
    K = max(len(T[i]),K)

P = [-1 for i in range(N)]
for i in range(N):
    for j in T[i]:
        if P[j] == -1:
            P[j] = i

from collections import deque
q = deque(T[0])
E = []
flag = []
num = 0
while q:
    i = q.popleft()
    if i != P[i] and not (tuple(sorted([i,P[i]])) in tuple(flag)):
        flag.append(tuple(sorted([i,P[i]])))
        E.append((tuple(sorted([i,P[i]])),num))
        num =(num+1)%K
        for j in T[i]:
            q.append(j)
ans = [-1 for i in range(N-1)]
for i,j in E:
    ans[Eo.index(i)] = j
print(K)
for i in ans:
    print(i+1)

Submission status: Wrong Answer

Solution code:
# TLE? 
N = int(input())
T = [[]for i in range(N)]
Eo = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    Eo.append((a-1,b-1))
Eo = tuple(Eo)
K = 0
for i in range(N):
    K = max(len(T[i]),K)

P = [-1 for i in range(N)]
for i in range(N):
    for j in T[i]:
        if P[j] == -1:
            P[j] = i

from collections import deque
q = deque(T[0])
E = []
flag = []
num = 0
while q:
    i = q.popleft()
    if i != P[i] and not (tuple(sorted([i,P[i]])) in tuple(flag)):
        flag.append(tuple(sorted([i,P[i]])))
        E.append((tuple(sorted([i,P[i]])),num))
        num =(num+1)%K
        for j in T[i]:
            q.append(j)
ans = [-1 for i in range(N-1)]
for i,j in E:
    print(i,j)
    ans[Eo.index(i)] = j
print(K)
for i in ans:
    print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import  deque
import time
N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]

ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1], 1))
dicans = {}

while len(q) > 0:
    i, l, c= q.popleft()
    num = c
    for k in l:
        if k < i:
            continue
        num += 1
        if num > ans1:
            num = 1
        dicans[(i, k)] = num
        q.append((k, dic[k], num))
        num += 1

print(ans1)

for a, b in A:
    print(dicans[(a, b)])

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [{0} for i in range(n)]

ans = [0] * n
a = 0
b = 0

for i in range(1,n):
    a,b = list(map(int,input().split()))
    for j in range(n):
        if not j in (s[a-1]|s[b-1]):
            break
    ans[i] = j
    s[a-1].add(ans[i])
    s[b-1].add(ans[i])
print(max(ans))
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [{0} for i in range(n)]

ans = [0] * n
a = 0
b = 0
sp = {i for i in range(1000)}
for i in range(1,n):
    a,b = list(map(int,input().split()))
    for j in range(n):
        if not j in (s[a-1]|s[b-1]):
            break
    ans[i] = j
    s[a-1].add(ans[i])
    s[b-1].add(ans[i])
print(max(ans))
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
s=int(input())
P=[]
Q=[]
for _ in range(s-1):
  t,u=map(int,input().split())
  P.append(int(t))
  Q.append(int(u))
R=[0 for j in range(s)]
R[0]-=1
for i in range(s-1):
  R[P[i]-1]+=1
a=max(R)+1
print(a)
R=[0 for l in range(s)]
for i in range(s-1):
  if R[P[i]-1]==a:
    print(1)
    R[P[i]-1]=1
    R[Q[i]-1]=1
    continue
  else:
    print(R[P[i]-1]+1)
    R[P[i]-1]+=1
    R[Q[i]-1]=R[P[i]-1]

Submission status: Wrong Answer

Solution code:
N = int(input())

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])

max_color = -1

# print(adj_dict)


result = []

# Create a queue for BFS
queue = [1]

# Mark the source node as
# visited and enqueue it

painted = {}

while queue:

    # Dequeue a vertex from
    # queue and print it
    s = queue.pop(0)

    # Get all adjacent vertices of the
    # dequeued vertex s. If a adjacent
    # has not been visited, then mark it
    # visited and enqueue it
    if s not in adj_dict:
        continue

    for i in range(len(adj_dict[s])):
        color = 1 + i
        if painted.get(s) is not None:
            if 0 < painted[s] <= color:
                color += 1
        result.append(color)
        # print(s, i)
        painted[adj_dict[s][i]] = color
        queue.append(adj_dict[s][i])

maxres = max(result)
result.insert(0, maxres)

for res in result:
    print(res)

'''
6
1 2
1 3
2 4
3 6
4 5
'''

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    hhh=[1]*(n+1)
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        j=max(hhh[a],hhh[b])
        #for j in range(q,n+1):
        #    if j not in c:
        ans[p]+=j
        x[a].add(j)
        x[b].add(j)
        #if hhh[a]+1==j: hhh[a]=j
        #if hhh[b]+1==j: hhh[b]=j
        if hhh[a]==j: hhh[a]=j+1
        if hhh[b]==j: hhh[b]=j+1
        #break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=set([i for i in range(1,n+1)])
    hhh=[1]*(n+1)
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        #j=min(np.setdiff1d(z,c))
        q=max(hhh[a],hhh[b])
        #print(q)
        for j in range(q,n+1):
        #for j in q:
            if j not in c:
                ans[p]+=j
                x[a].add(j)
                x[b].add(j)
                if hhh[a]+1==j: hhh[a]=j
                if hhh[b]+1==j: hhh[b]=j
                break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])

max_color = -1

# print(adj_dict)


result = []

# Create a queue for BFS
queue = [1]

# Mark the source node as
# visited and enqueue it

painted = [0]*(N+1)

while queue:

    # Dequeue a vertex from
    # queue and print it
    s = queue.pop(0)

    # Get all adjacent vertices of the
    # dequeued vertex s. If a adjacent
    # has not been visited, then mark it
    # visited and enqueue it
    if s not in adj_dict:
        continue

    for i in range(len(adj_dict[s])):
        color = 1 + i
        if 0 < painted[s] <= color:
            color += 1
        result.append(color)
        # print(s, i)
        painted[adj_dict[s][i]] = color
        queue.append(adj_dict[s][i])

maxres = max(result)
result.insert(0, maxres)

for res in result:
    print(res)

'''
6
1 2
1 3
2 4
3 6
4 5
'''

Submission status: Wrong Answer

Solution code:
N = int(input())

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])

max_color = -1

# print(adj_dict)

for key in adj_dict:
    temp_num = 0
    # print('key')
    for item in adj_dict[key]:
        # print(item)
        temp_num += 1
    # print(temp_num)
    if temp_num > max_color:
        # print(temp_num, max_color)
        max_color = temp_num


print(max_color)

result = -1

# Mark all the vertices as not visited
visited = [[] for x in range(N)]

# print(len(edge_list))

# Create a queue for BFS
queue = []

# Mark the source node as
# visited and enqueue it
queue.append(1)

painted = [[None] for y in range(N+1)]

while queue:

    # Dequeue a vertex from
    # queue and print it
    s = queue.pop(0)

    # Get all adjacent vertices of the
    # dequeued vertex s. If a adjacent
    # has not been visited, then mark it
    # visited and enqueue it
    if s not in adj_dict:
        continue

    for i in range(len(adj_dict[s])):
        color = 1 + i
        if painted[s] == color:
            color += 1
        print(color)
        # print(s, i)
        painted[adj_dict[s][i]] = color
        queue.append(adj_dict[s][i])

'''
6
1 2
1 3
2 4
3 6
4 5
'''

Submission status: Wrong Answer

Solution code:

N = int(raw_input())
edge = [map(int, raw_input().split()) for _ in xrange(N-1)]

v_color = [[] for i in xrange(N)]
e_color = []

Max = 0
for e in edge:
    used_color = v_color[e[0]-1] + v_color[e[1]-1]
    new_color = True
    for i in xrange(1, Max+1):
        if i not in used_color:
            e_color += [i]
            new_color = False
            break
    if new_color:
        e_color += [Max+1]
        Max += 1
    v_color[e[0]-1] += [e_color[-1]]
    v_color[e[1]-1] += [e_color[-1]]

print Max
for c in e_color:
    print c

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b),i))
    #w.sort()
    for a,b,p in w:
        c=x[a]|x[b]
        for j in range(1,n+1):
            if j not in c:
                ans[p]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N=int(input())
val=[list(map(int, input().split())) for i in range(N-1)]

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[0]*(N-1)
alen=[0]*N
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    alen[i]=len(arr[i])
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=set(colall)
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp.pop()
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            coltemp=1
            que[i+1] |= arrtemp
            for f in arrtemp:
                while(1):
                    if coltemp not in col[t]:
                        break
                    coltemp+=1
                p=coltemp
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])

Submission status: Wrong Answer

Solution code:
def func(iro,tree,num,max_color):
  if num not in tree:
    return
  
  my_color = iro[num]
  arr = tree[num]
  
  for i in arr:
    my_color += 1
    iro[i] = my_color % max_color
    func(iro,tree,i,max_color)
    

n = int(input())
tree = {}

b_arr = []
for i in range(n-1):
  a,b = map(int,input().split())
  
  b_arr.append(b)
  if a not in tree:
    tree[a] = []
    
  tree[a].append(b)
  
color = len(tree[1])
for key,arr in sorted(tree.items()):
  if key == 1:
    continue
    
  arr = tree[key]
  color = max(len(arr)+1, color)

print(color)

iro = [-1] * (n+1)

for key in tree.keys():
  my_color = iro[key]
  arr = tree[key]
  for i in arr:
    my_color += 1
    iro[i] = my_color % color

for i in b_arr:
  print(iro[i]+1)

Submission status: Wrong Answer

Solution code:
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
k = max(map(len, con))
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex % k==0)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
print(k)
for a, b in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k + 1 if t > k else t)

Submission status: Wrong Answer

Solution code:
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
k = max(map(len, con))
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex==0)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
print(k)
for a, b in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k + 1 if t > k else t)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[0]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]==0:
            if j==visited[v]:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.appendleft(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

N=int(input())
n=[0 for i in range(N+1)]
L=[]
for i in range(N-1):
    a,b=map(int,input().split())
    L.append([a,b])
    n[a]+=1
    n[b]+=1
    
M=max(n)
D=[{}for i in range(N+1)]
ans=[]

cnt=0

for j in L:
    for i in range(10**6):
        if cnt%M not in D[j[0]] and cnt%M not in D[j[1]]:
            ans.append(cnt%M+1)
            D[j[0]][cnt%M]=1
            D[j[1]][cnt%M]=1
            break
        else:
            cnt+=1
print(M)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
#d
def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = collections.deque([(1,0)])
    #while q:
    for _ in range(n):
        x,parent = q.popleft()
        if parent!=0:
            for j in range(k):
                if not k in used_colors[parent-1]:
                    current_color=k
                    break
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))   
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N=int(input())
val=[list(map(int, input().split())) for i in range(N-1)]

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[0]*(N-1)
alen=[0]*N
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    alen[i]=len(arr[i])
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=set(colall)
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp.pop()
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            coltemp=set(range(1,alen[t]+1))^col[t]
            que[i+1]=que[i+1] | arrtemp
            for f in arrtemp:
                p=coltemp.pop()
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a , b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
visited = [0] * N
visited[0] = 0
#print(tree)
def bfs(now):
    tmp = tree[now]
    tmp.extend([now])
    q = deque([tmp])
    #print(q)
    now_color = visited[now]
    while q:
        next_nodes = q.popleft()
        #print(next_nodes)
        now = next_nodes.pop()
        #print(visited)
        next_color = 0
        for next_node in next_nodes:
            if visited[next_node] == 0 and next_node != 0:
                if next_color + 1 == visited[now]:
                    next_color += 2
                else:
                    next_color += 1
                visited[next_node] = next_color
                tmp = tree[next_node]
                tmp.extend([next_node])
                q.appendleft(tmp)

bfs(0)
print(max(visited))
for i in range(1,len(visited)):
    print(visited[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
def used_col(N):
    col = set()
    # 子供の色
    for child in tree_children[N]:
        col.add(ans[child-2])
    # 親の色
    col.add(ans[tree_parent[N]-2])
    # 兄弟の色
    for child in tree_children[tree_parent[N]]:
        col.add(ans[child-2])
    return col
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    parent_bool = 1 if tree_parent[key] != 0 else 0
    max_col = max(len(tree_children[key])+parent_bool , max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = set(range(1,max_col+1))
    NG_col = used_col(i)
    for NG in NG_col:
        if NG == 0:
            pass
        else:
            available.remove(NG)
    ans[i-2] = min(available)
print(max_col)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
def used_col(N):
    col = set()
    # 子供の色
    for child in tree_children[N]:
        col.add(ans[child-2])
    # 親の色
    col.add(ans[tree_parent[N]-2])
    # 兄弟の色
    for child in tree_children[tree_parent[N]]:
        col.add(ans[child-2])
    return col
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    parent_bool = 1 if tree_parent[key] != 0 else 0
    max_col = max(len(tree_children[key])+parent_bool , max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = list(range(1,max_col+1))
    NG_col = used_col(i)
    for NG in NG_col:
        if NG == 0:
            pass
        else:
            available.remove(NG)
    ans[i-2] = available[0]
print(max_col)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
def solve():
  from collections import deque
  from sys import stdin
  
  f_i = stdin
  N = int(f_i.readline())
  
  e_color = {}
  adj = [[] for i in range(N)]
  for i in range(N - 1):
    a, b = map(int, f_i.readline().split())
    a -= 1
    b -= 1
    e_color[frozenset((a, b))] = None
    adj[a].append(b)
    adj[b].append(a)
  
  color_to_parent = [0] * N # color of edge between a vertex and its parent
  q = deque([0])
  notVisited = [True] * N
  notVisited[0] = False
  
  # BFS
  while q:
    v = q.popleft()
    color = 1
    for child in adj[v]:
      if notVisited[child]:
        if color == color_to_parent[v]:
          color += 1
        color_to_parent[child] = color
        e_color[frozenset((v, child))] = color
        color += 1
        notVisited[child] = False
        q.append(child)
  
  print(len(max(adj, key=len)))
  print('\n'.join(map(str, e_color.values())))

solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
def used_col(N):
    col = set()
    # 子供の色
    for child in tree_children[N]:
        col.add(ans[child-2])
    # 親の色
    col.add(ans[tree_parent[N]-2])
    # 兄弟の色
    for child in tree_children[tree_parent[N]]:
        col.add(ans[child-2])
    return col
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    max_col = max(len(tree_children[key])+1,max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = list(range(1,max_col+1))
    NG_col = used_col(i)
    for NG in NG_col:
        if NG == 0:
            pass
        else:
            available.remove(NG)
    ans[i-2] = available[0]
print(max_col)
for a in ans:
    print(a)

Submission status: Wrong Answer

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


N=int(input())
L=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(N-1)]

E=[[] for _ in range(N)]
for a,b in L:
    E[a].append(b)
    E[b].append(a)
dic={(min(a,b),(max(a,b))):-1 for a,b in L}
q=deque([0])
Ec=[set() for _ in range(N)]
while q:
    v=q.popleft()
    for to in E[v]:
        min_v,max_v=min(v,to),max(v,to)
        if dic[(min_v,max_v)]!=-1:
            continue
        c_i=1
        while c_i in Ec[v]:c_i+=1
        Ec[v].add(c_i);Ec[to].add(c_i)
        dic[(min_v,max_v)]=c_i
        q.append(to)

print(max(dic.values()))
for i in dic.values():
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    max_col = max(len(tree_children[key])+1,max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = list(range(1,max_col+1))
    children = tree_children[i]
    parent = tree_parent[i]
    if parent != 1 and ans[parent-2] != 0:
        available.remove(ans[parent-2])
        p_children = tree_children[parent]
        if p_children != set():
            for p_child in p_children:
                if ans[p_child-2] != 0:
                    available.remove(ans[p_child-2])
    if children != set():
        for child in children:
            if ans[child-2] != 0:
                available.remove(ans[child-2])
    ans[i-2] = available[0]
print(max_col)
for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
tree_children = ddict(set)
tree_parent = ddict(int)
for ab in AB:
    tree_children[ab[0]].add(ab[1])
    tree_parent[ab[1]] = ab[0]
max_col = 0
for key in tree_children.keys():
    max_col = max(len(tree_children[key])+1,max_col)
ans = [0] * (N-1)
for i in range(2,N+1):
    available = list(range(1,max_col+1))
    children = tree_children[i]
    parent = tree_parent[i]
    if parent != 1 and ans[parent-2] != 0:
        available.remove(ans[parent-2])
        p_children = tree_children[parent]
        if p_children != set():
            for p_child in p_children:
                if ans[p_child-2] != 0:
                    available.remove(ans[p_child-2])
    if children != set():
        for child in children:
            if ans[child-2] != 0:
                available.remove(ans[child-2])
    ans[i-2] = available[0]

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, id, max_node_num):
        self.parent_id = 0
        self.id = id
        self.color_id_flag = [0]*max_node_num

    def get_next_color_id(self):
        for num, i in enumerate(self.color_id_flag):
            if i == 0:
                return num+1

    def set_color_id(self, color_id):
        self.color_id_flag[color_id-1] = 1

    def set_parent_id(self, parent_id):
        self.parent_id = parent_id


def main():
    N = int(input())
    a_b_list = [list(map(int, input().split())) for _ in range(N-1)]

    node_dict = {}

    ans = []

    for i in range(N):
        node_dict[i+1] = Node(i+1, N)

    for a_b in a_b_list:
        a = a_b[0]
        b = a_b[1]

        node_dict[b].parent_id = a

        color_id = node_dict[a].get_next_color_id()
        node_dict[a].set_color_id(color_id)
        node_dict[b].set_color_id(color_id)

        ans.append(color_id)

    print(max(ans))
    print(*ans, sep="\n", end="")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, id, max_node_num):
        self.parent_id = 0
        self.id = id
        self.color_id_flag = [0]*max_node_num

    def get_next_color_id(self):
        for num, i in enumerate(self.color_id_flag):
            if i == 0:
                return num+1

    def set_color_id(self, color_id):
        self.color_id_flag[color_id-1] = 1

    def set_parent_id(self, parent_id):
        self.parent_id = parent_id


def main():
    N = int(input())
    a_b_list = [list(map(int, input().split())) for _ in range(N-1)]

    node_dict = {}

    ans = []

    for i in range(N):
        node_dict[i+1] = Node(i+1, N)

    for a_b in a_b_list:
        a = a_b[0]
        b = a_b[1]

        node_dict[b].parent_id = a

        color_id = node_dict[a].get_next_color_id()
        node_dict[a].set_color_id(color_id)
        node_dict[b].set_color_id(color_id)

        ans.append(color_id)

    print(max(ans))
    print(*ans, sep="\n")






if __name__ == '__main__':
    main()