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 sys
from collections import deque

N = int(input())
E = [tuple(int(j) for j in i.split()) for i in sys.stdin.readlines()]

ADJ = {}
visited = {}
colored = {}
deg = {}
mn = 0
for e in E:
    if not ADJ.get(e[0]):
        ADJ[e[0]] = []
    ADJ[e[0]].append(e[1])
    if not deg.get(e[0]):
        deg[e[0]] = 0
    if not deg.get(e[1]):
        deg[e[1]] = 0
    deg[e[0]] += 1
    deg[e[1]] += 1
    if deg[e[0]] > mn:
        mn = deg[e[0]]
    if deg[e[1]] > mn:
        mn = deg[e[1]]

print(mn)
Q = deque([(1, 0)])
while len(Q) > 0:
    n, parent = Q.popleft()
    ptr = 1
    e = (parent, n) if parent < n else (n, parent)
    target = colored.get(e, 0)
    visited[n] = True
    for v in ADJ.get(n, []):
        e = (n, v) if n < v else (v, n)
        if not visited.get(v):
            Q.append((v, n))
        if not colored.get(e):
            if ptr == target:
                ptr += 1
            colored[e] = ptr
            print(ptr)
            ptr += 1

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    ab=[tuple(map(int,input().split())) for _ in [0]*(n-1)]
    d={ab[i]:i for i in range(n-1)}
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    g2=[set() for _ in [0]*(n-1)]
    for i in range(n):
        for j in g[i]:
            for k in g[j]:
                p=min(i,j)
                q=max(i,j)
                r=min(j,k)
                s=max(j,k)
                x=d[(p+1,q+1)]
                y=d[(r+1,s+1)]
                g2[x].add(y)
                g2[y].add(x)
    for i in range(n-1):
        g2[i].remove(i)
    color=[-1]*(n-1)
    color[0]=1
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g2[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    print(max(color))
    print(*color)
main()

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    ab=[tuple(map(int,input().split())) for _ in [0]*(n-1)]
    d={ab[i]:i for i in range(n-1)}
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    g2=[set() for _ in [0]*(n-1)]
    for i in range(n):
        for j in g[i]:
            for k in g[j]:
                p=min(i,j)
                q=max(i,j)
                r=min(j,k)
                s=max(j,k)
                x=d[(p+1,q+1)]
                y=d[(r+1,s+1)]
                g2[x].add(y)
                g2[y].add(x)
    for i in range(n-1):
        g2[i].remove(i)
    color=[-1]*(n-1)
    color[0]=1
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g2[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    print(*color)
main()

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	for i in range(n-1):
		a, b = map(int, input().split())
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
	
	bb=max([len(t) for t in ttt])	
	print(bb)
	
	ret_ll=[0]*(n-1)
	ss_stack=[(0,-1, bb+100)]
	#state, parent, parent_path_color
	
	while len(ss_stack) > 0:
		st, parent, pp_color = ss_stack.pop()
		
		pp_flag=0
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to == parent:
				pp_flag=1
				continue
			
			c_color = i + 1 + (1 if i >= pp_color else 0) - pp_flag
			
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())


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

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0] - 1].append(row[1] - 1)
    link_list[row[1] - 1].append(row[0] - 1)
edge_color = dict()
marker = [0] * N


def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
#DFS_color(0, 0)
"""
print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1 - 1, node2 - 1])
"""

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())


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

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0] - 1].append(row[1] - 1)
    link_list[row[1] - 1].append(row[0] - 1)
edge_color = dict()
marker = [0] * N

"""
def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1 - 1, node2 - 1])
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            vv = str(s)+str(t)
            edgedata[vv] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    sss = (str(i[0]) + str(i[1]))
    print(edgedata[sss])
#output k

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    q = deque()
    q.append((1, 0))
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx, color = q.popleft()
        nxt = graph[idx]
        cnt = 1
        # print('visiting', nxt)
        for e in nxt:
            if colors[e] == -1 and not visited[e]:
                if cnt == color:
                    cnt += 1
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1
                else:
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1

    print(max(colors))
    print(*colors[2:])
    # for i in range(2, len(colors)):
    #     print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

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


def dfs(v, pc):
    colors = [True] * (N - 1)
    colors[pc] = False

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for idx_c, c in enumerate(colors):
                if c:
                    ec[idx] = idx_c + 1
                    colors[idx_c] = False
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

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


def dfs(v, pc):
    colors = [True] * (N - 1)
    colors[pc] = False

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for idx_c, c in enumerate(colors):
                if c:
                    ec[idx] = c
                    colors[idx_c] = False
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    q = deque()
    q.append((1, 0))
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx, color = q.popleft()
        nxt = graph[idx]
        cnt = 1
        # print('visiting', nxt)
        for e in nxt:
            if colors[e] == -1 and not visited[e]:
                if cnt == color:
                    cnt += 1
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1
                else:
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1

    print(max(colors))
    for i in range(2, len(colors)):
        print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    q = deque()
    q.append((1, 0))
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx, color = q.popleft()
        nxt = graph[idx]
        cnt = 1
        # print('visiting', nxt)
        for e in nxt:
            if colors[e] == -1 and not visited[e]:
                if cnt == color:
                    cnt += 1
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1
                else:
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1

    print(len(set(colors[2:])))
    for i in range(2, len(colors)):
        print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
counts = [[] for _ in range(N+1)]
ab = []
for _ in range(N-1):
  t = tuple(map(int, input().split()))
  ab.append(t)
  counts[t[0]].append(t[1])
  counts[t[1]].append(t[0])

m = max(map(len, counts))
print(m)
# print(ab)
# print(counts)

result = [set() for _ in range(N+1)]
for a, b in ab:
  if len(result[a]) == 0:
    r = 1
  else:
    for i in range(1, 1+m):
      if not (i in result[a] or i in result[b]):
        r = i
        break

  # print(result)
  print(r)
  result[a].add(r)
  result[b].add(r)

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 1
cm = []
SSS=[]
N = int(input())
for i in range(N-1):
  SSS.append(input())
  
for i in range(N+1):
  cm.append([])

for i in SSS:
  a,b= i.split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r)
    r+=1

print(r-1)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    q = deque()
    q.append(1)
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx = q.popleft()
        nxt = graph[idx]
        available = [i for i in range(1, len(nxt) * 2)]

        for e in nxt:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                if colors[e] == -1:
                    while len(available) != 0:
                        color = available.pop(0)
                        if color != colors[idx]:
                            colors[e] = color
                            break

    print(len(set(colors[2:])))
    for i in range(2, len(colors)):
        print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 1
cm = []
SSS=[]
N = int(input())
for i in range(N-1):
  SSS.append(input())
  
for i in range(N+1):
  cm.append([])

for i in SSS:
  a,b= i.split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r)
    r+=1

print(r)
for i in res:
  print(i)

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 = [0] * (N + 1)

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

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

Submission status: Wrong Answer

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    for k in range(N-1):
        a, b = map(int,input().split())
        T.append([a,b])
    C = [[0] for k in range(N+1)]
    ans = []
    for e in T:
        t = min(C[e[1]][0],C[e[0]][0])
        while (t in C[e[0]]) or (t in C[e[1]]):
            t += 1
        ans.append(t)
        C[e[0]].append(t)
        C[e[1]].append(t)
    print(max(ans))
    print(*ans,sep="\n")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 1
cm = []

N = int(input())
for i in range(N+1):
  cm.append([])
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r)
    r+=1

print(r-1)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 1
cm = []

N = int(input())
for i in range(N+1):
  cm.append([])
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r)
    r+=1

print(r)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
counts = [[] for _ in range(N+1)]
ab = []
for _ in range(N-1):
  t = tuple(map(int, input().split()))
  ab.append(t)
  counts[t[0]].append(t[1])
  counts[t[1]].append(t[0])

m = max(map(len, counts))
print(m)
# print(ab)
# print(counts)

result = [[] for _ in range(N+1)]
for a, b in ab:
  if len(result[a]) == 0:
    r = 1
  else:
    r = result[a][-1] + 1
    r = r if r <= m else 1

  print(r)
  result[a].append(r)
  result[b].append(r)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    tmp_color = 1
    for edge in n_list[node]:
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            try:
                paint(edge[0], edge[1])
            except Exception:
                print(0)
            tmp_color += 1

    
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num    a
for i in range(N-1):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 0
cm = []

N = int(input())
for i in range(N+1):
  cm.append([])
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr+1)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r+1)
    r+=1
print(r)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    tmp_color = 1
    for edge in n_list[node]:
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
try:
    paint(tmp[0][0], -1)
except Exception:
    print(0)
print(tmp[0][1]) # color num    a
for i in range(N-1):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
adj = defaultdict(list)
save = []
m = -1
target = - 1
tab = [0] * (n - 1)
for i in range(n - 1):
	x, y = map(int, input().split())
	save.append([x, y])
	adj[x].append(y)
	adj[y].append(x)
	x1, x2 = len(adj[x]), len(adj[y])
	if x1 > m:
		m = x1
		target = x
	if x2 > m:
		m = x2
		target = y
print(m)
for p in adj[target]:
	k = [min(p, target), max(p, target)]
	i = save.index(k)
	tab[i] = m
	m -= 1
for i in range(1, n + 1):
	if i != target:
		s = set()
		h = []
		for p in adj[i]:
			k = [min(p, i), max(p, i)]
			j = save.index(k)
			if tab[j]:
				s.add(tab[j])
			else:
				h.append(j)
		start = 1
		for v in h:
			while start in s:
				start += 1
			tab[v] = start
for i in range(n - 1):
	print(tab[i])

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 0
cm = []

N = int(input())
for i in range(N+1):
  cm.append([])
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = set(iro_i) - set(cm[a] + cm[b])
  
  if len(cr):
    cr = list(cr)[0]
    res.append(cr+1)
    cm[a].append(cr)
    cm[b].append(cr)
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r+1)
    r+=1
print(r+1)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
iro = []
iro_i = []
res = []
r = 0
cm = []

N = int(input())
for i in range(N+1):
  cm.append([])
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  for cr in set(iro_i) - set(cm[a] + cm[b]):
    res.append(cr+1)
    cm[a].append(cr)
    cm[b].append(cr)
    break
  else:
    iro_i.append(r)
    cm[a].append(r)
    cm[b].append(r)
    res.append(r+1)
    r+=1
print(r+1)
for i in res:
  print(i)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from collections import Counter
 
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
 
 
n = int(input())
 
arr = []
idx = 0
max = 0
for i in range(n - 1):
    arr.append([])
    arr[i] = [int(x) for x in input().split()]
    idx = 1
    for j in range(len(arr) - 1):
        if ((arr[i][0] == arr[j][0]) or (arr[i][0] == arr[j][1]) or (arr[i][1] == arr[j][0]) or (arr[i][1] == arr[j][1])) and idx == arr[j][2]:
            idx += 1
    arr[i].append(idx)
    if max < idx:
        max = idx

 
print(max)
for i in range(len(arr)):
    print(arr[i][2])

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)
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
k = max(map(len, con))
print(k)
for a, b in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k if t > k else t)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

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

memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].append(b)
    E[b].append(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

K = max(len(e) for e in E)

A = [0] * (N - 1)

visited = [False] * (N + 1)

Q = deque([(-1, 1)])
visited[1] = True
while Q:
    c, v = Q.popleft()
    C = (i for i in range(1, K + 1) if i != c)
    for u in E[v]:
        if visited[u]:
            continue
        visited[u] = True
        c = next(C)
        Q.append((c, u))
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from collections import Counter
 
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
 
 
n = int(input())
 
arr = []
idx = 0
max = 0
for i in range(n - 1):
    arr.append([])
    arr[i] = [int(x) for x in input().split()]
    idx = 1
    for j in range(len(arr) - 1):
        if ((arr[i][0] == arr[j][0]) or (arr[i][0] == arr[j][1])) and idx == arr[j][2]:
            idx += 1
    arr[i].append(idx)
    if max < idx:
        max = idx

 
print(max)
for i in range(len(arr)):
    print(arr[i][2])

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	pp_list=[]
	for i in range(n-1):
		a, b = map(int, input().split())
		if b < a:
			a,b = b,a
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
		pp_list.append([a,b,i])
	
	bb=max([len(t) for t in ttt])
	
	print(bb)
	
	ret_ll=[0]*(n-1)
	count_st=[0]*n
	ss_stack=[(0,-1, bb+100)]
	#state, parent, parent_path_color
	
	while len(ss_stack) > 0:
		st, parent, pp_color = ss_stack.pop()
		
		pp_flag=0
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to == parent:
				pp_flag=1
				continue
			
			c_color = i + 1 + (1 if i >= pp_color else 0) - pp_flag
			
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

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

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

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

queue = deque()
queue.append(0)

color = [-1 for _ in range(N)]

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        c += 1
        queue.append(adj)
        k = max(k,c+1)
print(k)

for e in edge:
    print(color[e[1]-1]+1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)