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

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

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


    edges.append((a, b))


e_buf = [{} for _ in range(N)]
color = [-1 for _ in range(N)]
buf = [(0, 0)]
K = 1

while len(buf) != 0:
    i, c = buf.pop()

    next_c = 0
    for next in graph[i]:
        if color[next] == -1:
            next_c += 1
            if next_c == c:
                next_c += 1
            buf.append((next, next_c))
            color[next] = next_c
            K = max(K, next_c)

ans = []
for a, b in edges:
    if color[a] == -1:
        ans.append(color[b])
        color[b] = -1
    else:
        ans.append(color[a])
        # print(color[a])
        color[a] = -1

k = 0
i_j_dict = {}
for a in ans:
    if a not in i_j_dict:
        k += 1
        i_j_dict[a] = k


print(k)
for a in ans:
    print(i_j_dict[a])

Submission status: Wrong Answer

Solution code:
N = int(input())

s = [[] for _ in range(N)]
r = []
for _ in range(N-1):
  a, b = map(int, input().split())
  if s[a-1] + s[b-1] == []:
    s[a-1] = [1]
    s[b-1] = [1]
    r += [1]
  else:
    ss = set(s[a-1] + s[b-1])
    m = max(ss)
    n = len(ss)
    if m == n:
      s[a-1] += [n+1]
      s[b-1] += [n+1]
      r += [n+1]
    
    else:
      nn = list(set([i for i in range(1, m+1)]) - ss)[0]
      s[a-1] += [nn]
      s[b-1] += [nn]
      r += [nn]

print(max(r))
print(*r, sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
df = [[] for _ in range(n)]
r = [0 for _ in range(n)]
ab = []
for i in range(n-1):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
    df[a-1].append(b-1)
    df[b-1].append(a-1)
    r[a-1] += 1
    r[b-1] += 1
k = max(r)
print(k)
c = [[0 for _ in range(k)] for _ in range(n)]
for i in range(n-1):
    a, b = ab[i]
    for j in range(k):
        if c[a][j] == 0 and c[b][j] == 0:
            c[a][j] = 1
            c[b][j] = 1
            print(j+1)
            break

Submission status: Wrong Answer

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

from collections import defaultdict
g = defaultdict(list)
for i in range(len(ab)):
    g[ab[i][0]].append(ab[i][1])
    g[ab[i][1]].append(ab[i][0])

k = 0
for key in g.keys():
    k = max(k, len(g[key]))
print(k)

ans_d = dict()
for key in g.keys():
    ans_d[key] = dict()
    for v in g[key]:
        ans_d[key][v] = 0

used_all = dict()
for key in g.keys():
    used_all[key] = []

from bisect import bisect_left
for key in g.keys():
    used = used_all[key]

    targets = list(range(1, k+1))

    cand = 1
    for target in g[key]:
        if ans_d[key][target] == 0:
            while True:
                idx = bisect_left(used, cand)
                if idx < len(used) and used[idx] == cand:
                    cand += 1
                else:
                    break

            ans_d[key][target] = cand
            ans_d[target][key] = cand
            used_all[key].append(cand)
            used_all[target].append(cand)
            cand += 1

# print(ans_d)

for i in range(len(ab)):
    print(ans_d[ab[i][0]][ab[i][1]])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0 for _ in range(n - 1)]
b = [0 for _ in range(n - 1)]
colors = [[] for _ in range(n + 1)]
leaf = []
max = 0
for i in range(n - 1):
    a[i], b[i] = map(int, input().split())
    for j in range(1, 1000000):
        if j not in colors[a[i]] and j not in colors[b[i]]:
            leaf.append(j)
            colors[a[i]].append(j)
            colors[b[i]].append(j)
            if max < j:
                max = j
            break

print(max)
for l in leaf:
    print(l)

Submission status: Wrong Answer

Solution code:
n=int(input())
subs=[]
anslist=[]
counter=1
for i in range(n-1):
    a,b=map(int,input().split())
    if subs==[]:
        subs.append(a)
        subs.append(b)
        anslist.append(1)
    elif subs!=[]:
        if (a in subs) or (b in subs):
            counter+=1
            anslist.append(counter)
            subs=[]
            subs.append(a)
            subs.append(b)
        else:
            counter=1
            anslist.append(counter)
            subs=[]
            subs.append(a)
            subs.append(b)
M=max(anslist)
print(M)
for s in anslist:
    print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
each_edge = [set() for i in range(N)]
ans = []
kouho = set([i+1 for i in range(N)])
for i in range(N-1):
    a, b = map(int, input().split())
    if len(each_edge[a-1]) == 0 and len(each_edge[b-1]) == 0:
        tmp = 1
    else:
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        outlist = aset | bset
        #print(outlist)
        for i in range(N):
            if i+1 in outlist:
                continue
            else:
                tmp = i+1
                break
    each_edge[a-1].add(tmp)
    each_edge[b-1].add(tmp)
    ans.append(tmp)

K = -1
for i in each_edge:
    K = max(K, len(i))
print(K)
for line in ans:
    print(line)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

all = {1}
ans = []
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1

    used = set(lst[a] + lst[b])
    not_used = all - used

    if len(not_used) == 0:
        x = len(all) + 1
        all.add(x)
    else:
        x = min(not_used)

    ans.append(x)

    lst[a].append(x)
    lst[b].append(x)


print(len(all))
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())

import sys
input = sys.stdin.readline

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


ans = [[0 for _ in range(n)] for __ in range(n)]
visited = [False]*n

q = [(0,0)]
visited[0] = True

mx = 0
while q:
    key,v = q.pop()
    i = 1
    for x in edges[v]:
        if not visited[x]:
            if key != i:
                visited[x] = True
                ans[v][x] = i
                ans[x][v] = i
                q.append((i,x))
                mx = max(mx,i)
                i += 1
            else:
                visited[x] = True
                i += 1
                ans[v][x] = i
                ans[x][v] = i
                mx = max(mx,i)
                i += 1
                q.append((i,x))

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

Submission status: Wrong Answer

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

K = 0
for g in graph:
    K = max(K,len(g))
print(K)

color = [[] for i in range(N)]

for e in edge:
    for i in range(K):
        if i not in color[e[0]-1] and i not in color[e[0]-1]:
            print(i+1)
            color[e[0]-1].append(i)
            color[e[1]-1].append(i)
            break

Submission status: Wrong Answer

Solution code:
n = int(input())
graf = [[] for _ in range(n)]
colorU = [0 for _ in range(n)]
colorD = [0 for _ in range(n)]
ab = []
ans = []
n -= 1
for i in range(n):
    # print(i)
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # print(i)
    if colorD[a] == 0:
        if colorU[a] == 1:
            thiscolor = 2
        else:
            thiscolor = 1
    else:
        thiscolor = max(colorD[a], colorU[a]) + 1 #1本目以外
    colorU[b] = thiscolor
    colorD[a] = thiscolor
    ans.append(thiscolor)
    # print(i)
    # print(thiscolor, i)

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

# i = 0
# j = 0
# lasta = 0
#
# for l in range(n):
#     a, b = map(int, input().split())
#     if a != lasta:
#         i = a - 1
#         j = 0
#
#     if j == 0:
#         thiscolor = color[i] + 1
#     else:
#         thiscolor = graf[a][j - 1] + 1
#
#     graf[i].append()

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
for i in range(N-1):
    AB[i][0] = AB[i][0]-1
    AB[i][1] = AB[i][1]-1
Edges =[[] for _ in range(N)]
for i in range(N-1):
    Edges[AB[i][0]].append(AB[i][1])
    Edges[AB[i][1]].append(AB[i][0])
c = 0
for i in range(N):
    if c < len(Edges[i]):
        c = len(Edges[i])
usedColors = [1 for _ in range(N)]
print(c)
for i in range(N-1):
    a,b = AB[i][0],AB[i][1]
    m = max(a,b)
    if m%c == 0:
        print(c)
    else:
        print(m%c)
    usedColors[a] = m+1
    usedColors[b] = m+1

Submission status: Wrong Answer

Solution code:
N = int(input())


dict_list = [{} for i in range(N)]

color_list = []

color_num = 0

for i in range(N-1):
    a, b = map(int, input().split())
    for j in range(color_num):
        if str(j+1) not in dict_list[a-1] and str(j+1) not in dict_list[b-1]:
            color_edge = j+1
            dict_list[a-1][str(j+1)] = 1
            dict_list[b-1][str(j+1)] = 1
            break
    else:
        color_edge = color_num + 1
        color_num += 1
        dict_list[a-1][str(color_num)] = 1
        dict_list[b-1][str(color_num)] = 1

    color_list.append(color_edge)

print(color_num)

for i in range(N-1):
    print(color_list[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
graf = [[] for _ in range(n)]
colorU = [0 for _ in range(n)]
colorD = [0 for _ in range(n)]
ab = []
ans = []
n -= 1
for i in range(n):
    # print(i)
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # print(i)
    if colorD[a] == 0:
        if colorU[a] == 1:
            thiscolor = 2
        else:
            thiscolor = 1
    else:
        thiscolor = max(colorD[a], colorU[a]) + 1 #1本目以外
    colorU[b] = thiscolor
    colorD[a] = thiscolor
    ans.append(thiscolor)
    # print(i)
    # print(thiscolor, i)

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

# i = 0
# j = 0
# lasta = 0
#
# for l in range(n):
#     a, b = map(int, input().split())
#     if a != lasta:
#         i = a - 1
#         j = 0
#
#     if j == 0:
#         thiscolor = color[i] + 1
#     else:
#         thiscolor = graf[a][j - 1] + 1
#
#     graf[i].append()

Submission status: Wrong Answer

Solution code:
def p_d():
    n = int(input())
    t = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
    num = 0
    t_size = []
    for i in range(n):
        num = max(num, len(t[i]))
        t_size.append((len(t[i]), i))
    t_size.sort(reverse=True)
    # print(num)
    # print(t_size)
    # print(t)
    color = [-1] * n
    for size, i in t_size:
        if size == 1:
            continue
        li = []
        for j in t[i]:
            if color[j] != -1:
                li.append(color[j])
                continue
            for k in range(1, num + 1):
                if k not in li:
                    color[j] = k
                    li.append(k)
                    break
    print("\n".join(map(str, color)))
    
p_d()

Submission status: Wrong Answer

Solution code:
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())


d = [0]*n

for i in range(n-1):
    d[a[i]-1]+=1
    d[b[i]-1]+=1

k = max(d)
print(k)


knode = []
for i in range(n):
    knode.append(list(range(1,k+1)))

c = [0]*(n-1)
for i in range(n-1):
    for j in knode[a[i]-1]:
        if j in knode[b[i]-1]:
            c[i] = j
            knode[a[i]-1].remove(j)
            knode[b[i]-1].remove(j)
            break

for i in c:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(tree, idx, mx_color, n):
    queue = deque([])
    queue.append([idx, color+1])
    edge_color = {}
    visit = [False] * (n)
    visit[idx] = True

    while queue:
        parent,cc = queue.popleft()
#         print(parent, cc, '-', tree[parent])
        for i, child in enumerate(tree[parent]):
            if visit[child]:
                continue
            child_color = mx_color if i+1 == cc else (i+1)
            edge_color[str(min(parent,child))+','+str(max(parent,child))] = child_color
#             print([child, child_color])
            queue.append([child, child_color])
            visit[child] = True
    return edge_color

n = int(input())
tree = [[] for _ in range(n)]
edge = []
for _ in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    edge.append(str(min(a,b))+','+str(max(a,b)))
color = max(len(i) for i in tree)

edge_color = bfs(tree, 0, color, n)
print(color)
#print(edge_color)
[print(edge_color[c]) for c in edge]

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N-1)]
E = sorted(A, key = lambda x:x[1])
E.sort()
t = 0

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


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

t = 0
cnt = 0
ans_a = 0
for i in range(N-1):
	a,b = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans[a][b] = cnt
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1
	

print(ans_a)
for aa,bb in E:
	print(ans[aa][bb])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
basho = {}
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    s = str(a) + '-' + str(b)
    basho[s] = i
#print(basho)
#print(graph)
maxi = 0
for i in range(N):
    leni = len(graph[i])
    maxi = max(leni, maxi)
K = maxi
color = [0 for i in range(N-1)]
for i in range(N):
    v = graph[i]
    colk = [False for i in range(K)]
    for j in v:
        if i < j:
            n = str(i) + '-' + str(j)
        else:
            n = str(j) + '-' + str(i)
        if color[basho[n]] == 0:
            ind = colk.index(False)
            color[basho[n]] = ind + 1
            colk[ind] = True
        else:
            colk[color[basho[n]]-1] = True
print(K)
for i in range(N-1):
    print(color[i])

Submission status: Wrong Answer

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


AB = []

D = defaultdict(int)

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

ans = 0
for i in range(N):
    if ans < D[i]:
        ans = D[i]

print(ans)

E = defaultdict(int)

for a, b in AB:
    E[a] += 1
    E[b] += 1
    print(E[a])

Submission status: Wrong Answer

Solution code:

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

d = {}
p = []
for n in range(N-1):
    a,b = AB[n]

    if a in d:
        d[a] += 1
    else:
        d[a] = 1

    if b in d:
        d[b] += 1
    else:
        d[b] = 1

    p.append(max(d[a] , d[b]))

print (max(list(d.values())))
for ii in range(N - 1):
    print (p[ii])

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    colors = [1]*(n+1)
    edges = {}
    for i in range(1,n+1):
        edges[i] = []
    k = 0
    order = []
    for i in range(n-1):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)
        order.append((a,b))

    for i in edges.keys():
        k = max(k,len(edges[i]))

    #print(colors,order)
    print(k)
    for i in order:
        print(max(colors[i[0]],colors[i[1]]))
        colors[i[0]] += 1
        colors[i[1]] += 1
        if colors[i[0]] > k:
            colors[i[0]] = 1
        if colors[i[1]] > k:
            colors[i[1]] = 1
    
        

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
tree=[[] for i in range(n)]
for i in l:
  tree[i[0]-1].append(i[1])
  tree[i[1]-1].append(i[0])
ans=0
for i in tree:
    ans=max(ans,len(i))
print(ans)
c=[[] for i in range(n+1)]
for i in l:
    x=i[0]
    y=i[1]
    for j in range(1,ans+1):
        if j not in c[x] and j not in c[y]:
            print(j)
            c[x].append(j)
            c[y].append(j)
            break

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [[] for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  for i in range(1, K+1):
    if not (i in V[a]):
      c = i
      req_K = False
      break
  if req_K:
    K += 1
    c = K
    V[a].append(c)
  V[b].append(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])

Submission status: Wrong Answer

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


def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [set() for _ in range(N+1)]

    for i in range(N-1):
        h[a[i]].add(i)
        h[b[i]].add(i)


    max_color = 0
    for hh in h:
        max_color = max(len(hh),max_color)
    color = list(range(1,max_color+1))
    # colorList[i]が辺iのいろ
    colorList = [0]*(N-1)

    h.sort(key=lambda x: -len(x))
    for i in range(0,N):
        color_index = 0

        for hh in h[i]:
            if colorList[hh] > 0:
                while colorList[hh] == color[color_index]:
                    if color_index < max_color-1:
                        color_index += 1 
                    else:
                        color_index = 0
                continue
            else:
                colorList[hh] = color[color_index]
                color_index+=1
     
    print(max_color)
    for c in colorList:
        print(c)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import statistics
import math
import collections
n = int(input())
a =[0,0]
for i in range(n-1):
	a+=list(map(int,input().split()))

k = collections.Counter(a).most_common()[0][1]



print(k)
c =1

for i in range(2,2*n,2):
	if a[i] is not a[i-1] and a[i] is not a[i-2] and a[i+1]is not a[i-1] and a[i+1] is not a[i-2]:
		c = 1
		print("1")
	else:
		c+=1
		print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] * N
B = [0] * N
C = [0] * N
for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    C[A[i]-1] += 1
    C[B[i]-1] += 1
print(max(C))
D = [0] * N
for i in range(N):
    D[i] = list(range(1,max(C)+1))

for i in range(N-1):
    a = A[i]-1
    b = B[i]-1
    for i in D[a]:
        if i in D[b]:
            print(i)
            D[a].remove(i)
            D[b].remove(i)
            break

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    tree = {}
    edge = []
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        if a not in tree:
            tree[a] = {}
        if b not in tree:
            tree[b] = {}
        tree[a][b] = None
        tree[b][a] = None
        edge.append([a, b])
    colors = max(len(b) for b in tree.itervalues())
    print colors
    nodes = {i: set() for i in xrange(1, n + 1)}
    for a, b in edge:
        aa = nodes[a]
        bb = nodes[b]
        for c in xrange(1, colors + 1):
            if c not in aa and c not in bb:
                print c
                aa.add(c)
                bb.add(c)
                break


main()

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [0]*(N-1)
cho = [0]*(N+1) #cho[i]にi番目の頂点の根元の色
res = [0]*(N-1)
for i in range(0,N-1):
    data[i] = list(map(int, input().split()))
    if i != 0 and data[i][0] == data[i-1][0]:
        cur += 1
    else:
        cur = 1
    if cur == cho[data[i][0]]: cur += 1
    res[i] = cur
    cho[data[i][1]] = cur

print(max(cho))
for item in res:
    print(item)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
watch = [0]*N
watch[0] = 1
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([N//2])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if watch[next] == 0:
                queue.append(next)
                watch[next] = 1

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
col = [[] for _ in range(N+1)]
ans = []
AB = [list(map(int,input().split())) for _ in range(N-1)]
AB.sort()
for ab in AB:
    left = ab[0]
    right = ab[1]
    for i in range(1,N):
        if not i in col[left]:
            ans.append(i)
            col[left].append(i)
            col[right].append(i)
            break
K = len(set(ans))
print(K)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return "".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(a,b,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2
        if ll == mid:
            return ll
        co = mid * a
        mm = mid
        while mm != 0:
            co += b
            mm //= 10 
        if co >= r:
            rr = mid-1
        else:
            ll = mid


n = onem()

kkk = [[] for i in range(n)]

for i in range(n-1):
    a,b = m()
    kkk[a-1].append([b-1,i+1])
    kkk[b-1].append([a-1,i+1])
de = cl.deque([[0,0,0]])
kk= []
while de:
    j,k,p = de.popleft()
    co = 1
    for i in range(len(kkk[j])):
        if not kkk[j][i][0] == k:
            if co == p:
                co += 1
            de.append([kkk[j][i][0],j,co])
            kk.append([co,kkk[j][i][1]])
            co += 1

kk.sort()

print(max(kk,key = lambda x:x[0])[0])

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])
color_v = [[] for _ in range(N + 1)]

while queue:
    V = queue.popleft()
    for v in graph[V]:
        number = 1
        if number in color_v[V]:
            number += max(color_v[V])
        color[v] = number
        color_v[V].append(number)
        color_v[v].append(number)
        queue.append(v)

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    a -= 1
    b -= 1
    query[a].append((b,i))
    query[b].append((a,i))
  ans = 0
  for i in range(n):
    ans = max(ans,len(query[i]))
  print(ans)
  node = deque([])
  stack = [[] for _ in range(n)]
  for i in range(n):
    if len(query[i]) == ans:
      node.append((i,ans,100000))
      break
  for i in range(n):
    stack[i] = (len(query[i]))
  #print(stack)
  tmp = [-1]*(n-1)
  visit = [False]*n
  while node:
    #print(node)
    place,maxnode,last = node.popleft()
    for j,i in query[place]:
        if tmp[i] == -1:
          if not last == maxnode:
            tmp[i] = maxnode
          else:
            tmp[i] = maxnode-1
          maxnode -= 1
        
        if visit[j]:
          continue
        else:
          node.append((j,stack[j],tmp[i]))
    visit[place] = True
    
    
  for i in tmp:
    print(i)
solve()

Submission status: Wrong Answer

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

color = [0]*(n-1)
count = [0]*n
for i in range(n-1):
    count[a[i]-1] += 1
    count[b[i]-1] += 1
    color[i] = max(count[a[i]-1], count[b[i]-1])
print(max(count))
for c in color:
    print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = []
B = []
for _ in range(N-1):
    i = list(map(int, input().split()))
    A.append(i[0])
    B.append(i[1])

ans = []

for i in range(N-1):
    if not i == 0:
        if A[i] == A[i-1]:
            ans.append(ans[i-1]+1)
        else:
            x = i
            while x >= 0:
                if B[x] == A[i]:
                    break
                x -= 1
            if ans[x] != 1:
                ans.append(1)
            else:
                ans.append(2)
    else:
        ans.append(1)
    
print(max(ans))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
def examD():
    N = I()
    cur = [0]*(N-1)
    super = [0]*(N+1)
    d = defaultdict(int)
    AB = [[0]*2 for _ in range(N-1)]
    for i in range(N-1):
        AB[i] = LI()
    AB.sort()
    for i in range(N-1):
        a, b = AB[i][0],AB[i][1]
        d[a] +=1
        if d[a]!=super[a]:
            cur[i] = d[a]
        else:
            d[a] +=1
            cur[i] = d[a]
        super[b] = cur[i]
    ans = max(cur)
    print(ans)
    for i,v in enumerate(cur):
        print(v)

def examE():
    N, K = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
def input() -> str:
    return sys.stdin.readline().rstrip()
n = int(input())
edges = [input().split() for _ in range(n - 1)]
edges.sort()
colors = defaultdict(list)
answer = []
for a, b in edges:
  c = 1
  while True:
    if c not in colors[a] and c not in colors[b]:
      colors[a].append(c)
      colors[b].append(c)
      answer.append(c)
      break
    c += 1
print(max(answer), *answer, sep="\n")

Submission status: Wrong Answer

Solution code:
n = int(input())

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


ans = [[0 for _ in range(n)] for __ in range(n)]
visited = [False]*n

q = [(0,0)]
visited[0] = True

mx = 0
while q:
    key,v = q.pop()
    i = 1
    for x in edges[v]:
        if not visited[x[1]]:
            if key != i:
                visited[x[1]] = True
                ans[v][x[1]] = i
                ans[x[1]][v] = i
                q.append((i,x[1]))
                mx = max(mx,i)
                i += 1
            else:
                visited[x[1]] = True
                i += 1
                ans[v][x[1]] = i
                ans[x[1]][v] = i
                mx = max(mx,i)
                i += 1
                q.append((i,x[1]))

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

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
L=[{}for i in range(N+1)]
ans=[]
for i in range(N-1):
    a,b=map(int,input().split())
    for j in range(1,N):
        if j not in L[a] and j not in L[b]:
            L[a][j]=1
            L[b][j]=1
            ans.append(j)
            break
print(max(ans))
for i in range(N-1):
    print(ans[i])
#print(L)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

cnt = 0
for i in range(n):
    cnt = max(cnt,len(edge[i]))
#print(cnt)

ans = [None]*n

que = deque()
que.append(0)
tmp = 1
while que:
    v = que.popleft()
    if ans[v] == None:
        ans[v] = tmp
        tmp += 1
    if tmp > cnt:
        tmp -= cnt
    for u in edge[v]:
        if ans[u] == None:
            que.append(u)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())

mylist = [[] for n in range(N+1)]

#print(mylist)

for i in range(N-1):
    a,b = map(int, input().split())
    mylist[a] += [b]
    mylist[b] += [a]
#print(mylist)    
myans = 0
for i in range(len(mylist)):
    if len(mylist[i]) > myans: 
        myans = len(mylist[i])
    
print(myans)
color = 0
for i in range(1, len(mylist)):
    for j in mylist[i]:
        if j > i:
            print(color%(myans)+1)
            color += 1