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 operator import itemgetter
input = sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=[[] for i in range(n)]
d=[]
for i in range(n-1):
  c[l[i][0]-1].append(l[i][1]-1)
  c[l[i][1]-1].append(l[i][0]-1)
for i in range(n):
  d.append(len(c[i]))
print(max(d))
dmax=d.index(max(d))

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=c[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(c[next[i]])):
          if visited[c[next[i]][j]]==-1:
            next2.add(c[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

bfs=bfs(dmax)

color=[set() for i in range(n)]
l2=[]

for i in range(n-1):
  l2.append([min(bfs[l[i][0]-1],bfs[l[i][1]-1]),i,l[i][0],l[i][1]])

l2.sort()
ans=[]
for i in range(n-1):
  for j in range(1,n+1):
    if j not in color[l2[i][2]-1] and j not in color[l2[i][3]-1]:
      ans.append((l2[i][1],j))
      break
  color[l[i][0]-1].add(j)
  color[l[i][1]-1].add(j)
ans.sort()
for i in range(n-1):
  print(ans[i][1])

Submission status: Wrong Answer

Solution code:
N=int(input())
info=[list(map(int, input().split())) for _ in range(N-1)]
lst=[[] for i in range(N+1)]
K=max(len(l) for l in lst)
color_map=[[False for _ in range(K+1)] for _ in range(N+1)]
color_list=[0 for i in range(N-1)]
for i in range(N-1):
  a, b=info[i]
  for j in range(1, K+1):
    if not color_map[a][j] and not color_map[b][j]:
      color_map[a][j]=True
      color_map[b][j]=True
      color_list[i]=j
      break
print(K)
for i in range(N-1):
  print(color_list[i])

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)]
	while len(ss_stack)>0:
		st, parent = ss_stack.pop()
		pp_flag=0
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to==parent:
				pp_flag=1
				continue
			
			ret_ll[idx] = i + 2 - (1 if parent==-1 else 0)-pp_flag
			ss_stack.append([path_to, st])
			
	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:
n = int(input())
a = [0]*(n-1)
b = [0]*(n-1)
c = [0]*(n-1)
cnt = [0]*(n+1)
d = {}
d[n] = []
for i in range(n-1):
  a[i], b[i] = map(int, input().split())
  cnt[a[i]] += 1
  cnt[b[i]] += 1
  d[i+1] = []
m = max(cnt)
for i in range(n-1):
  la = d[a[i]]
  lb = d[b[i]]
  for j in range(1,m+1):
    if j not in la and j not in lb:
      c[i] = j
      la.append(j)
      lb.append(j)
      d[a[i]] = la
      d[b[i]] = lb
      break
print(m)
for i in range(n-1):
  print(c[i])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

sorted_ab = sorted(ab, key=lambda x: (x[0], x[1]))

v_edges = [set() for i in range(N)]

for a, b in ab:
    v_edges[a - 1].add(b - 1)
    v_edges[b - 1].add(a - 1)

# print(sorted_ab)
v_colors = [set() for i in range(N)]
n_colors = max([len(e) for e in v_edges])
e_colors = [[-1] * (N) for i in range(N - 1)]
print(n_colors)

for a, b in sorted_ab:
    for i in range(n_colors):
        if i not in v_colors[a - 1] and i not in v_colors[b - 1]:
            v_colors[a - 1].add(i)
            e_colors[a - 1][b - 1] = i
            break
    # print(e_colors[a - 1][b - 1] + 1)k

# print(e_colors)
for a, b in ab:
    print(e_colors[a - 1][b - 1] + 1)

Submission status: Wrong Answer

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

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

ans=[]
ans2=[]
for i in range(n-1):
  a=ab[i][0]-1
  b=ab[i][1]-1
  for j in range(1,10**5):
    if j not in c[a] and j not in c[b]:
      ans.append(j)
      c[a]+=[j]
      c[b]+=[j]
      break

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
sind = sorted(range(len(ab)),key=lambda k:ab[k])
ab.sort()

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
# anslist = [[0]*N for i in range(N)]
anslist = []
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			anslist.append(kk)
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

ans = []
for i in range(N-1):
	ans.append(anslist[sind[i]])

print(K,*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
L={}
for i in range(1,N+1):
    L[i]={}
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]:
            if 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:
n=int(input())
ab=[]
p=[-3 for i in range(n+1)]
edge=[[0 for i in range(n+1)] for j in range(n+1)]
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1

    for i in range(len(G[num])):

        if used[G[num][i]]==0:
            if p[num]==i+1:
                edge[num][G[num][i]]=max_n
                edge[G[num][i]][num]=max_n
                p[G[num][i]]=max_n
                queue.append(G[num][i])
            else:
                edge[num][G[num][i]]=i+1
                edge[G[num][i]][num]=i+1
                p[G[num][i]]=i+1
                queue.append(G[num][i])

print(max_n)
for i in range(n-1):

    print(edge[ab[i][0]][ab[i][1]])

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[]
ans=[0 for i in range(n)]
#print(ans)
for i in range(n-1):
  a,b=map(int,input().split())
  ab.append((a,b))
ab.sort()  
#print(ab)
for (c,d) in ab:
  ans[c-1]+=1
  ans[d-1]+=1
  
#print(ans)
print(max(ans))
for i in range(1,max(ans)+1):
  print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

N = int(stdin.readline().rstrip())
ab = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]
tree = [[] for _ in range(N)]

for i in range(N - 1):
    tree[ab[i][0] - 1].append(ab[i][1] - 1)
    tree[ab[i][1] - 1].append(ab[i][0] - 1)

q = deque([])
q.append(0)
colors = [[] for _ in range(N)]
ans = []
visited = [False] * N
cc = 0

while len(q) > 0:
    temp = q.popleft()
    visited[temp] = True
    cnt = 1
    for x in tree[temp]:
        if not visited[x]:
            q.append(x)
            while cnt in colors[temp]:
                cnt += 1
            colors[temp].append(cnt)
            colors[x].append(cnt)
            ans.append(cnt)


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

Submission status: Wrong Answer

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


AB = []

D = defaultdict(list)


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


ans = 0

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

print(ans)

E = defaultdict(set)


for a, b in AB:
    for m in range(1, ans+1):
        if m not in E[a]:
            print(m)
            E[a].add(m)
            E[b].add(m)
            break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
input=sys.stdin.readline
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    #g[b].append(a)

res=[[] for i in range(n)]
#print(g)
fin=[0 for i in range(n)]
def abc(i):
    global res,g
    cnt=1
    if g[i]==[]:
        pass
    else:
        for a in g[i]:
            while True:
                if cnt in res[i]:
                    cnt+=1
                else:
                    break
            res[a].append(cnt)
            res[i].append(cnt)
            fin[a]=cnt
            cnt+=1
            abc(a)
abc(0)
print(len(set(fin))-1)
for i in range(1,n):
    print(fin[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
mat = [list(map(int,input().split())) for i in range(N-1)]
dic = dict(zip(range(1,N+1),[0]*N))
for i in range(N-1):
    for j in range(2):
        dic[mat[i][j]] += 1
K = max(dic.values())
index = max(dic.items(),key = lambda x:x[1])[0]
save = [[] for i in range(N)]
tmp = [0]*(N-1)
num = 1
for i in range(N-1):
    if index in mat[i]:
        tmp[i] = num
        save[mat[i][0]-1].append(num)
        save[mat[i][1]-1].append(num)
        num += 1
if 0 not in tmp:
    print(K)
    for i in range(len(tmp)):
        print(tmp[i])
else:
    for i in range(len(tmp)):
        if tmp[i] == 0:
            for j in range(1,K+1):
                if j not in save[mat[i][0]-1] and j not in save[mat[i][1]-1]:
                    tmp[i] = j
                    save[mat[i][0]-1].append(j)
                    save[mat[i][1]-1].append(j)
    print(K)
    for k in range(len(tmp)):
        print(tmp[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-1)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        try:
            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
        except Exception as e:
            print(e)

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

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
ans = {}
V = [[] for _ in range(N)]
for e in E:
  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:
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
t = {i:{'done': set()} for i in range(1, N+1)}

maxv = 0
for a, b in ab:
    ans = 1
    while True:
        if ans not in t[a]['done'] and ans not in t[b]['done']:
            t[a]['done'].add(ans)
            t[b]['done'].add(ans)
            t[a][b] = ans
            t[b][a] = ans
            break
        else:
            ans += 1
    maxv = max(maxv, ans)

print(maxv)
for a, b in ab:
    print(t[a][b])

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    bl = []
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        bl.append((a,b))
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    m = 0
    for i in d:
        m = max(m, len(d[i]))
    print(m)
    d2 = {i:[0] for i in range(N+1)}
    for a, b in bl:
        for i in range(1, m + 1):
            if i not in d2[a] and i not in d2[b]:
                d2[a].append(i)
                d2[b].append(i)
                print(i)
                break

main()

Submission status: Wrong Answer

Solution code:
N=int(input())
arr=[[] for i in range(N+1)]
key=[[i for i in range(1,N+1)] for j in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    arr[a].append([a,b])
for i in range(1,N+1):
    k=0

    for ele in arr[i]:
        print(key[i][k])
        key[arr[i][0][1]].remove(key[i][k])
        k+=1

Submission status: Wrong Answer

Solution code:
from collections import deque
def f(x):
  return int(x) - 1

N = int(input())
ab = [tuple(map(f, input().split())) for _ in range(N-1)]

v =  deque([[] for _ in range(N)])
col = deque([])
K = 0
for a, b in ab:
    for k in range(1,K+1):
        if (not k in v[a]) and (not k in v[b]):
            v[a].append(k)
            v[b].append(k)
            col.append(k)
            break
    else:
        K += 1
        v[a].append(K)
        v[b].append(K)
        col.append(K)
        
print(K)
for c in col:
    print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[set([]) for i in range(n+1)]
ans=[]
for i in range(n-1):
    a,b=map(int,input().split())
    c=x[a]|x[b]
    for j in range(1,n+1):
        if j not in c:
            ans.append(j)
            x[a].add(j)
            x[b].add(j)
            break
#print(x)
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

tree = [set() for _ in range(n+1)]
parent_color = [0 for _ in range(n+1)]

need_color = 0
colors = []
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].add(b)
    color = len(tree[a])
    if parent_color[a] != 0 and parent_color[a] <= color:
        color += 1
    need_color = max(need_color, color)
    parent_color[b] = color
    colors.append(color)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append([b, i])
  else:
    edges[a] = [[b, i]]
  if b in edges.keys():
    edges[b].append([a, i])
  else:
    edges[b] = [[a, i]]
colors = [0 for i in range(n-1)]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  global edges
  flags[node] = True
  try:
    for edge in edges[node]:
      if flags[edge[0]] == False:
        if i != cannot:
          colors[edge[1]] += i
        else:
          i += 1
          colors[edge[1]] += i
        i += 1
        search(edge[0], i-1)
  except:
    print(0)
search(n, 0)
print(max(colors))
for i in range(n-1):
  print(colors[i])

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)
g2 = defaultdict(list)
for i in range(len(ab)):
    g[ab[i][0]].append(ab[i][1])
    g[ab[i][1]].append(ab[i][0])
    g2[ab[i][0]].append(ab[i][1])

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

used_all = dict()
for key in g.keys():
    used_all[key] = [0] * (k + 1)

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

    cand = 1
    for target in g2[key]:
        while True:
            if used_all[cand] == 1:
                cand += 1
            else:
                break

        ans_d[key][target] = cand
        used_all[target][cand] = 1
        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:
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 = [set([0]) for k in range(N+1)]
    ans = []
    for e in T:
        t = 0
        while t in C[e[0]] or t in C[e[1]]:
            t += 1
        ans.append(t)
        C[e[0]].add(t)
        C[e[1]].add(t)
    print(max(ans))
    print(*ans,sep="\n")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=[[] for i in range(n)]
d=[]
for i in range(n-1):
  c[l[i][0]-1].append(l[i][1]-1)
  c[l[i][1]-1].append(l[i][0]-1)
for i in range(n):
  d.append(len(c[i]))
print(max(d))
dmax=d.index(max(d))

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=c[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(c[next[i]])):
          if visited[c[next[i]][j]]==-1:
            next2.add(c[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

bfs=bfs(dmax)

color=[set() for i in range(n)]
l2=[]

for i in range(n-1):
  l2.append([min(bfs[l[i][0]-1],bfs[l[i][1]-1]),i,l[i][0],l[i][1]])

l2.sort()
ans=[]
for i in range(n-1):
  for j in range(1,n+1):
    if j not in color[l[i][0]-1] and j not in color[l[i][1]-1]:
      ans.append((l2[i][1],j))
      break
  color[l[i][0]-1].add(j)
  color[l[i][1]-1].add(j)
ans.sort()
for i in range(n-1):
  print(ans[i][1])

Submission status: Wrong Answer

Solution code:
N = int(input())

edges = []

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

colors = [-1] * (N - 1)

def func(a, p_i, p_color=-1):
    edge_index = []
    for i in range(p_i, N - 1):
        _a, _b = edges[i]
        if _a == a:
            edge_index.append(i)

    color = 1
    for e_i in edge_index:
        if color == p_color:
            color += 1
        __a, __b = edges[e_i]
        colors[e_i] = color
        func(__b, e_i, color)
        color += 1

func(1, 0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for i in range(N)]
lines = []
colors = [set() for i in range(N)]
ans = [-1] * N
for i in range(N - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    lines.append((a - 1, b - 1,))

max_color = 1
color = 1
for i in range(N - 1):
    for c in range(1, max_color + 2):
        if c in colors[lines[i][0] - 1] or c in colors[lines[i][1] - 1]:
            continue
        color = c
        break
    max_color = max(max_color, color)

    colors[lines[i][0] - 1].add(color)
    colors[lines[i][1] - 1].add(color)
    ans[i] = color

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

Submission status: Wrong Answer

Solution code:
N = int(input())
to = {i:set() for i in range(N)}
edges = [[int(x)-1 for x in input().split()] for _ in range(N-1)]
i = 1
for a, b in edges:
    to[a].add(b)
    to[b].add(a)
K = max(len(to[k]) for k in to)
print(K)
nodes = {i:set() for i in range(N)}
for a, b in edges:
    for i in range(1, K+1):
        if (i not in nodes[a]) and (i not in nodes[b]):
            print(i)
            nodes[a].add(i)
            nodes[b].add(i)
            break

Submission status: Wrong Answer

Solution code:
class Edge:
	def __init__(s, t, i):
		self.index = s
		self.e_index = i

N = int(input())

ve = [{'index': i, 'edges': []} for i in range(N)]
e = [0 for i in range(N)]

for i in range(N - 1):
	s, g = [int(x) - 1 for x in input().split()]
	
	ve[s]['edges'].append(i)
	ve[g]['edges'].append(i)
	
ve.sort(key=lambda x: len(x['edges']))
ve.reverse()

max = len(ve[0]['edges'])
for i in range(N):
	ed = ve[i]['edges']
	c = 1
	k = 0
	
	has_color = []
	for k in range(len(ed)):
		if e[ed[k]] != 0:
			has_color.append(e[ed[k]])
	
	c = 1
	k = 0
	while k < len(ed):
		if e[ed[k]] != 0:
			k += 1
			continue
		
		try:
			has_color.index(c)
			c += 1
			continue
		except:
			pass
		
		e[ed[k]] = c
		c += 1
		k += 1

for i in range(len(e)):
	if e[i] == 0:
		e[i] = 1
	
es = [str(x) for x in e]
print("\n".join(es))

Submission status: Wrong Answer

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


def main():
    N = int(input().strip())
    each_edge = [set() for i in range(N)]
    ans = []

    for _ in range(N-1):
        a, b = map(int, input().strip().split())
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        outlist = aset | bset
        for i in range(N-1):
            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 edges in each_edge:
        K = max(K, len(edges))
    print(K)
    print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline


class Node:
    def __init__(self, num):
        self.num = num
        self.edge_colors = []


N = int(input())

# treeの初期化
tree = []
tree.append(Node(0))
for i in range(1, N + 1):
    tree.append(Node(i))


colors = []

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

    # edgeの１本目
    if len(colors) == 0:
        edge_color = 1
        colors.append(edge_color)
        tree[a].edge_colors.append(edge_color)
        tree[b].edge_colors.append(edge_color)
    else:
        used_colors = tree[a].edge_colors + tree[b].edge_colors
        # if len(used_colors) == 0:
        #     # その視点、終点の頂点に初めて辺が入る時
        #     edge_color = colors[0]
        #     tree[a].edge_colors.append(edge_color)
        #     tree[b].edge_colors.append(edge_color)
        # else:
        unused_colors = list(set(colors) - set(used_colors))
        if len(unused_colors) == 0:
            # 新しい色の辺を使う
            edge_color = len(colors) + 1
            colors.append(edge_color)
            tree[a].edge_colors.append(edge_color)
            tree[b].edge_colors.append(edge_color)
        else:
            # 元々あった色の辺を使う
            edge_color = unused_colors[0]
            tree[a].edge_colors.append(edge_color)
            tree[b].edge_colors.append(edge_color)

    ans.append(edge_color)

print(len(colors))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
use = [[True] * (n-1) for _ in range(n)]
pcol = [0] * n
brcol = []
colors = -1

def decInt(v):
    return int(v) - 1

for _ in range(n-1):
    a, b = map(decInt, input().split())
    colo = pcol[a] if pcol[a] > pcol[b] else pcol[b]
    if use[a][colo] and use[b-1][colo]:
        use[a][colo] = False
        use[b][colo] = False
        brcol.append(colo+1)
        if pcol[a] == colo:
            for i in range(colo+1, n-1):
                if use[a][i]: 
                    pcol[a] = i
                    break
        if pcol[b] == colo:
            for i in range(colo+1, n-1):
                if use[b][i]: 
                    pcol[b] = i
                    break
        if colors < colo:
            colors = colo
print(colors+1)
for co in brcol:
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
inputs = sys.stdin.readlines()
n = int(inputs[0])
nodes = [tuple(map(int, x.split())) for x in inputs[1:]]

tree = defaultdict(tuple)
for i in range(1, n+1):
    tree[i] = tuple(n[1] for n in nodes if n[0] == i)
colors = list(range(1, max([len(x) for x in tree.values()])+2))

def travel(p, bros):
    use_colors = [p]
    for node in bros:
        for c in colors:
            if c not in use_colors:
                use_colors.append(c)
                break
        nodes[node] = c
        travel(c, tree[node])
    

nodes = [0]*(n+1)
node = 1
nodes[node] = 1
childs = tree[node]
travel(node, childs)

for node in nodes[1:]:
    print(node)

Submission status: Wrong Answer

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

color = [i+1 for i in range(max(si))]
cnt = [[] for i in range(n)]
for i in range(n-1):
	aa = min(set(color) - set(cnt[ab[i][0]-1]))
	bb = min(set(color) - set(cnt[ab[i][1]-1]))
	new = max(aa, bb)
	cnt[ab[i][0]-1].append(new)
	cnt[ab[i][1]-1].append(new)
	print(new)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

        nodes = defaultdict(int)

        K = 0
        for a, b in ab:
            nodes[a] += 1
            nodes[b] += 1
            K = max([K, nodes[a], nodes[b]])


        color = defaultdict(set)
        all = set(range(1, K + 1))
        ans = []
        for a, b in ab:
            nokori = all - (color[a] | color[b])
            if len(nokori) == 0:
                K += 1
                all.add(K)
                c = K
            else:
                c = list(nokori)[0]
            ans.append(c)
            color[a].add(c)
            color[b].add(c)
            
        print(K)
        for a in ans:
            print(a)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
ed = []
for i in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, i))
  e[v].append((u, i))
  if v < u: u, v = v, u
  ed.append((u, v))
de = dd(set)
d = [0] * (N + 1)
res = 0
for k in e.keys():
  res = max(len(e[k]), res)
print(res)
rr = [0] * (N - 1)
for i in range(1, N + 1):
  x = 1
  vis = set()
  for y in e[i]:
    j = y[1]
    if rr[j] > 0:
      vis.add(rr[j])
  for y in e[i]:
    j = y[1]
    if rr[j] > 0: continue
    if x in vis:
      for xx in range(1, res + 1):
        if xx in vis: continue
        else: 
          x = xx
          break
    rr[j] = x
    x += 1
for i in range(N - 1):
  print(rr[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [tuple(map(lambda v: int(v) - 1, input().strip().split())) for _ in range(n - 1)]

# {node: {(edge, target), ...}, ...}
nodes = {i: set() for i in range(n)}
for e, (a, b) in enumerate(edges):
    nodes[a].add((e, b))
    nodes[b].add((e, a))
degrees = sorted(enumerate(map(len, nodes.values())), key=lambda t: t[1], reverse=True)
# [(node_id, degree), ...]
max_deg = degrees[0][1]
print(max_deg)

all_colors = set(range(max_deg))
colors = [None for _ in range(n - 1)]
for node, _ in degrees:
    usables = all_colors - {colors[t[0]] for t in nodes[node]}
    for e, _ in nodes[node]:
        if colors[e] is None:
            colors[e] = usables.pop()

print("\n".join(map(lambda c: str(c + 1), colors)))

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

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        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 as e:
    print(0)

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

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

        if len(h[i]) == 1 and colorList[list(h[i])[0]] > 0:
            continue

        cur = [colorList[b] for b in h[i] if colorList[b]>0] ##塗ってある色リスト

        for hh in h[i]:
            if i == 0:
                colorList[hh] = color[color_index]
                color_index+=1
            if colorList[hh] > 0: ##塗って会ったらもういい
                continue
            else:            
                while color[color_index] in cur:
                    if color_index < max_color-1:
                        color_index+=1
                    else:
                        color_index = 0

                colorList[hh] = color[color_index]

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