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:
#Coloring Edges on Tree
import sys
import collections
input = sys.stdin.readline

n = int(input())
a,b = [0]*n,[0]*n

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

c = collections.Counter(a+b)

print(a+b)
cnt = c.most_common()[0][1]
print(cnt)

res = [1]*n
clr = [0]*n

for i in range(n-1):
  if(b.count(a[i])>0):
    res[i] += res[b.index(a[i])]
  if(a.count(a[i])>1):
    res[i] += clr[a[i]]
    clr[a[i]] += 1
  print(res[i]%(cnt)+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [deque([]) for _ in range(n)]
for a, b in ab:
    graph[a-1].append((b-1, -1))
    # graph[b-1].append((a-1, -1))
 
k = 0
for i in graph:
    if k < len(i)+1:
        k = len(i)+1

stack = deque([(0, -1)])

while stack:
    node, color = stack.pop()
    # visited[node] = 1

    tmp = 1
    i = 0
    for child, child_color in graph[node]:
        if tmp == color:
            tmp += 1
        graph[node][i] = (child, tmp)
        stack.append((child, tmp))
        tmp +=1
        i += 1
 
print(k)
for a, b in ab:
    print(graph[a-1].popleft()[1])

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
E_n = {k: 0 for k in ab}
for i in range(1,N+1):
    items = {k:v for k,v in E_n.items() if i in k}
    c = 1
    for k in items.keys():
      if items[k] != 0: continue
      while True:
        if c not in items.values():
          items[k] = c
          break
        else: c += 1

    for k,v in items.items(): E_n[k] = v
    if reduce(mul, E_n.values()) != 0: break

print(len(set(E_n.values())))
for k in sorted(E_n.keys()): print(E_n[k])

Submission status: Wrong Answer

Solution code:
import sys
from pprint import pprint

n = int(sys.stdin.readline().strip())
edges = []
for _ in range(n-1):
    edges.append(list(map(int, sys.stdin.readline().strip().split(" "))))

count = [0] * (n+1)
# pprint(edges)
pre_color = -1
colors = []

point_used = {}
for edge in edges:
    count[edge[0]] += 1
    count[edge[1]] += 1
max_deg = max(count)

for edge in edges:
    if edge[0] not in point_used:
        point_used[edge[0]] = [1]
        point_used[edge[1]] = [1]
        colors.append(1)
        continue
    
    for i in range(1, max_deg + 1): 
        if i not in point_used[edge[0]]:
            point_used[edge[0]].append(i)
            if edge[1] not in point_used:
                point_used[edge[1]] = []
            point_used[edge[1]].append(i)
            colors.append(i)
            break

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
print(N, ab)
E_n = {k: 0 for k in ab}
for i in range(1,N+1):
    items = {k:v for k,v in E_n.items() if i in k}
    c = 1
    for k in items.keys():
      if items[k] != 0: continue
      while True:
        if c not in items.values():
          items[k] = c
          break
        else: c+=1
    for k,v in items.items(): E_n[k] = v
    if reduce(mul, E_n.values()) != 0: break

print(len(set(E_n.values())))
for k in sorted(E_n.keys()): print(E_n[k])

Submission status: Wrong Answer

Solution code:
from collections import deque
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)

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

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

queue = deque([])
queue.append(0)

while queue:
    node = queue.popleft()
    j = 0
    for i in range(len(graph[node])):
        if color[graph[node][i]] == -1:
            color[graph[node][i]] = (color[node]+j+1)%K
            queue.append(graph[node][i])
            j += 1


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N=input()

al=[ [] for i in range(N+1) ]
Q=[]    #初期の質問（クエリー）
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
    Q.append((a,b))

K=0
start=None
for i,t in enumerate(al):
    K=max(K,len(t))
    if start is None and len(t)==1:
        start=i

edge={} #辺集合 (fro,to):色

#BFS
Visit=[ 0 for _ in range(N+1) ] #訪問した頂点
q=deque()
q.append(start)
Visit[start]=1
prev=[ 0 for _ in range(N+1) ] #前の頂点との間で使用済みのカラー

color=1
while q:
    fro=q.popleft()
    #print "fro ::",fro
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	#ここで訪問済みVisitに1をセットする。4行上のpopleftの直後でVisitをセットすると同じ頂点がqに入り、TLEする
            q.append(to)
            if prev[fro]==color:    #使おうとしてた色が前の頂点との間で使用済みであれば、１ずらす
                edge[(fro,to)]=color+1    #色をセット
                edge[(to,fro)]=color+1    #色をセット               
            else:
                edge[(fro,to)]=color    #色をセット
                edge[(to,fro)]=color    #色をセット
            prev[to]=color
            color+=1
            if K<color: color%=K    #色が最大のK色を超えた場合は1に戻る


print K
for a,b in Q:
    print edge[(a,b)]

Submission status: Wrong Answer

Solution code:
N = int(input())
sides = []  # 各辺
side_colors = [0] * (N - 1)  # 各辺に使う色
point_sides = [0] * N  # 各頂点が持つ辺の数
point_colors = [set() for i in range(N)]

for i in range(N - 1):
    s, e = map(int, input().split())
    sides.append([s - 1, e - 1])
    point_sides[s - 1] += 1
    point_sides[e - 1] += 1

max_color_num = max(point_sides)
point_of_max_side_num = point_sides.index(max_color_num)
color_id = 1
for i in range(N - 1):
    s = sides[i][0]
    e = sides[i][1]
    if s == point_of_max_side_num or e == point_of_max_side_num:
        point_colors[s].add(color_id)
        point_colors[e].add(color_id)
        side_colors[i] = color_id
        color_id += 1

for i in range(N - 1):
    s = sides[i][0]
    e = sides[i][1]
    if s != point_of_max_side_num and e != point_of_max_side_num:
        for j in range(1, max_color_num + 1):
            if (j not in point_colors[s]) and (j not in point_colors[e]):
                point_colors[s].add(j)
                point_colors[e].add(j)
                side_colors[i] = j
                break

print(max_color_num)
for side_color in side_colors:
    print(side_color)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
print(N, ab)
E_n = {k: 0 for k in ab}
for i in range(1,N+1):
    items = {k:v for k,v in E_n.items() if i in k}
    c = 0
    for k in items.keys():
      if items[k] != 0: continue
      while True:
        c += 1
        if c not in items.values():
          items[k] = c
          break
    for k,v in items.items(): E_n[k] = v
    if reduce(mul, E_n.values()) != 0: break

print(len(set(E_n.values())))
for k in sorted(E_n.keys()): print(E_n[k])

Submission status: Wrong Answer

Solution code:
n = int(input())
d = {}
l=[]
g=[[] for _ in range(n)]
dg = [0]*n
c = [[] for i in range(n)]
for _ in range(n-1):
  x,y = map(int,input().split())
  g[x-1]+=[y-1]
  g[y-1]+=[x-1]
  l.append((x-1,y-1))
  d[(x-1,y-1)]=-1
  dg[x-1]+=1
  dg[y-1]+=1
k = max(dg)
x = set(i+1 for i in range(k))
col = [set() for i in range(n)]
p=1
for i in l:
  if p not in col[i[0]] and p not in col[i[0]]:
    d[i]=p
    col[i[0]].add(p)
    col[i[1]].add(p)
  else:
    p = min(list(x-(col[i[0]].union(col[i[1]]))))
    d[i]=p
    col[i[0]].add(p)
    col[i[1]].add(p)
    p=1
print(k)
for i in l:
  print(d[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[list(map(int,input().split())) for i in range(n-1)]
tree={}
for a,b in AB:
    if a not in tree:
        tree[a]=[b]
    else:
        tree[a] +=[b]

ans=[0]*(n+1)
for i in tree.keys():
    flag=0
    for j,k in enumerate(tree[i]):
        if j+1==ans[i]:flag=1
        if flag:
            ans[k]=j+2
            continue
        ans[k]=j+1

print(max(ans))
for i in range(2,n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import copy

def main():
    N = int(input())
    v_count = [0] * N
    e = []
    for _ in range(N-1):
        e.append(list(map(int, input().split())))
    
    color_count = {}
    ans = []
    for i in range(1,N+1):
        color_count[i] = []
    
    for (a, b) in e:
        v_count[a-1] += 1
        v_count[b-1] += 1

        res = True
        color_id = 1
        while(res):
            if color_id not in color_count[a] and color_id not in color_count[b]:
                ans.append(color_id)
                color_count[a].append(color_id)
                color_count[b].append(color_id)
                res = False
            else:
                color_id += 1
    print(max(v_count))
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
#隣接点数、インデックス、色、隣接点
g=[[0,i,-1,[]] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    ga=g[a-1]
    ga[0]+=1
    ga[3].append(b-1)
    g[a-1]=ga

    gb=g[b-1]
    gb[0]+=1
    gb[3].append(a-1)
    g[b-1]=gb
g.sort()

c=1
ans=[-1 for _ in range(n)]
for i in range(n):
    nextto=g[i][3]
    while(True):
        nextc=[]
        for j in nextto:
            nextc.append(g[j][2])
        nextc=list(set(nextc))
        if(c not in nextc):
            g[i][2]=c
            ans[g[i][1]]=c
            break
        else:
            c+=1

for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
rec = []
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
  rec.append([a,b])
can = []
for i in range(n):
  can.append(len(peer[i]))
#print(peer)
#print(can)
ans = max(can)
now = [0]
clr = [0 for _ in range(n)]
ok = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
clr[0] = 1
ok[0] = 2
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y] == 0:
        now.append(y)
        clr[y] = ok[x]
        rank[y] = rank[x] + 1
        ok[x] = ok[x] % ans + 1
        ok[y] = clr[y] % ans + 1
print(ans)
#print(clr)
for w in rec:
  a,b = w
  if rank[a] > rank[b]:
    m = a
  else:
    m = b
  print(clr[m])
#print(rank)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    v_color = [[0] for _ in range(N)]
    color = 1
    ans_l = [color]

    a, b = map(lambda x:int(x)-1, input().split())
    v_color[a].append(color)
    v_color[b].append(color)

    for i in range(N-2):
        flag = False
        a, b = map(lambda x:int(x)-1, input().split())
        for j in range(1, color+1):
            if j not in v_color[a] and j not in v_color[b]:
                v_color[a].append(j)
                v_color[b].append(j)
                ans_l.append(j)
                flag = True
                break
        if not flag:
            color += 1
            v_color[a].append(color)
            v_color[b].append(color)
            ans_l.append(color)

    print(color)
    for ans in ans_l:
        print(ans)



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=sorted([list(map(int,input().split())) for i in range(n-1)])
tree={}
for a,b in AB:
    if a not in tree:
        tree[a]=[b]
    else:
        tree[a] +=[b]

ans=[0]*(n+1)
for i in tree.keys():
    flag=0
    for j,k in enumerate(tree[i]):
        if j+1==ans[i]:flag=1
        if flag:
            ans[k]=j+2
            continue
        ans[k]=j+1

print(max(ans))
for i in range(2,n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())

a = [0] * (N-1)
b = [0] * (N-1)

max_edge = 0
tmp = 0
edge_num = 0
color = 1

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

for i in range(1, N+1):
  tmp = a.count(i) + b.count(i)
  if max_edge < tmp:
    max_edge = tmp
    edge_num = i

print(max_edge)

for i in range(0, N-1):
  print(color)
  if a[i] ==  edge_num or b[i] == edge_num:
    color += 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 = []
    color = 1
    for i in range(p_i + 1, N - 1):
        _a, _b = edges[i]
        if _a == a:
            if color == p_color:
                color += 1
            colors[i] = color
            func(_b, i, color)
            color += 1


func(1, -1)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
from collections import defaultdict
d=defaultdict(int)
l=[[] for i in range(n+1)]
l1=[]
for i in range(n-1):
  a,b=map(int,input().split())
  l1.append([a,b])
  l[a].append(b)
  l[b].append(a)
max1=0
for i in range(1,n+1):
  if max1<len(l[i]):
    max1=len(l[i])
print(max1)
for i in range(n-1):
  l2=l1[i]
  d[l2[0]]+=1
  d[l2[1]]+=1
  print(max(d[l2[1]],d[l2[0]]))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    lines = [list(map(int, input().split())) for i in range(N-1)]

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

    for l in lines:

        nodes[l[0]-1].append(l[1])
        nodes[l[1]-1].append(l[0])

    max = 0
    for n in nodes:
        if max < len(n):
            max = len(n)

    #色の数
    print(max)

    #関係の数字
    count = [0 for i in range(N)]

    for l in lines:

        count[l[0]-1]+=1
        count[l[1]-1]+=1

        print(count[l[0]-1])





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
 
for a, b in ab:
    graph[a-1].append((b-1, -1))
    graph[b-1].append((a-1, -1))
 
k = 0
for i in graph:
    if k< len(i)+1:
        k = len(i)+1

stack = [(0, -1)]
visited = [-1]*n

ce = [-1]*(n-1)

while stack:
    node, color = stack.pop()
    visited[node] = 1

    tmp = 1
    i = 0
    for child, child_color in graph[node]:
        if visited[child] == 1:
            continue
        if tmp == color:
            tmp += 1
        graph[node][i] = (child, tmp)
        stack.append((child, tmp))
        tmp +=1
        i += 1
 
print(k)
for a, b in ab:
   for node, color in graph[a-1]:
       if node == b-1:
           print(color)

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])
m=[]
maxk=1
for i in range(1,N+1):
    k=0

    for ele in arr[i]:
        m.append(key[i][k])
        key[arr[i][0][1]].remove(key[i][k])
        k+=1
        maxk=max(maxk,m[-1])
print(maxk)
for ele in m:
    print(ele)

Submission status: Wrong Answer

Solution code:
n = int(input())
print(2)
for i in range(n-1):
  print(i%2+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
gg = [[] for _ in range(N)]
c = [[0]*N for _ in range(N)]
ab = [list(map(int, input().split())) for _ in range(N-1)]
for a,b in ab:
    gg[a-1].append(b)
    gg[b-1].append(a)

i = 0
for g in gg:
    m = 1
    for gi in g:
        if c[i][gi-1] == 0:
            c[i][gi-1] = m
            m += 1
    i += 1
mx = 0
for ci in c:
    for cii in ci:
        mx = max(mx,cii)
print(mx)
for abi in ab:
    print(c[abi[0]-1][abi[1]-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
ans = []
sub = [0 for i in range(n+1)]
k = 0
for i in range(n+1):
    color = 0
    for j in range(len(tree[i])):
        color += 1
        if color == sub[i]:
            color += 1
        ans.append(color)
        sub[tree[i][j]] = color
        if k < color:
            k = color
print(k)
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)

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 = 0
for i in range(n-1):
  la = d[a[i]]
  lb = d[b[i]]
  j = 1
  while(True):
    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
    j += 1
    if m < j:
      m = j
print(m)
for i in range(n-1):
  print(c[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(input())
E = [tuple(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', None)])
while len(Q) > 0:
    n, parent = Q.popleft()
    ptr = 1
    target = colored.get((parent, n), 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())
    colors = [1]*(n+1)
    all_edges = {}
    nodes = {}
    order = []
    edges = []
 
    for i in range(1,n+1):
        nodes[i] = []
        
    for i in range(n-1):
        a,b = map(int,input().split())
        nodes[a].append(b)
        nodes[b].append(a)
        all_edges[(a,b)] = 0
        order.append((a,b))
        edges.append((a,b))

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

    visited = set()
    for i in range(1,n):
        if i not in visited:
            visited.add(i)
            avail = []
            if i == 1:
                limit = colors[i]+1
            else:
                limit = colors[i]
            for j in range(1,limit):
                avail.append(j)
            for j in range(colors[i]+1,k+1):
                avail.append(j)
            #print(i,avail)
            if len(nodes[i]) > 1:
                for kid in nodes[i]:
                    if kid not in visited:
                        #print(i,kid)
                        all_edges[(i,kid)] = avail.pop()
                        colors[kid] = all_edges[(i,kid)]

    print(k)
    for i in order:
        print(all_edges[i])
    
    
 
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import copy

def main():
    N = int(input())
    v_count = [0] * N
    e = []
    for _ in range(N-1):
        e.append(list(map(int, input().split())))
    
    for (a, b) in e:
        v_count[a-1] += 1
        v_count[b-1] += 1
    
    print(max(v_count))
    color_count = {}
    for i in range(1,N+1):
        color_count[i] = []

    for (a, b) in e:
        res = True
        color_id = 1
        while(res):
            if color_id not in color_count[a] and color_id not in color_count[b]:
                print(color_id)
                color_count[a].append(color_id)
                color_count[b].append(color_id)
                res = False
            else:
                color_id += 1


if __name__ == '__main__':
    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])
m=[]
maxk=1
for i in range(1,N+1):
    k=0

    for ele in arr[i]:
        m.append(key[i][k])
        key[arr[i][0][1]].remove(key[i][k])
        k+=1
        maxk=max(maxk,k+1)
print(maxk)
for ele in m:
    print(ele)

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

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

c = 1
	
es = [str(x) for x in e]
print(max)
print("\n".join(es))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
edges=list(list(map(int,input().split())) for _ in range(n-1))
data=list([] for _ in range(n))
for i in range(n-1):
  data[edges[i][0]-1].append(i)
  data[edges[i][1]-1].append(i)
colors=max(map(len,data))
print(colors)
sets=list({0} for _ in range(n))
result=[0 for _ in range(n-1)]
for i in range(n-1):
  s=sets[edges[i][0]-1].union(sets[edges[i][1]-1])
  for j in range(colors):
    if j + 1 in s:
      continue
    result[i]=j+1
    sets[edges[i][0]-1].add(j+1)
    sets[edges[i][1]-1].add(j+1)
    break
for r in result:
  print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
pairs = {}
for i in range(N):
    pairs[i + 1] = []
    
for _ in range(N-1):
    a, b = map(int, input().split())
    edges.append([a, b])
    pairs[a].append(b)
    pairs[b].append(a)

k = 0
for v in pairs.values():
    k = max(k, len(v))

pairs_list = list(pairs.items())
# pairs_list.sort(key=lambda x: len(x[1]), reverse=True)
# print(pairs_list)

colors = [0] * (N-1)

memo = []

for pl in pairs_list:
    a, v = pl
    c = 1
    for b in v:
        i = edges.index([min(a, b), max(a,b)])
        if colors[i]==0:
            colors[i] = c
        else:
            c = colors[i]
        c = c%k+1

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

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge_num = [0] * N
    edge = dict()
    max_edge = 0
    
    for i in range(N - 1):
        a, b = map(int, input().split())
        edge[i] = (a-1, b-1)
        edge_num[a-1] += 1
        edge_num[b-1] += 1
        max_edge = max(max_edge, edge_num[a-1], edge_num[b-1])

    edge_used = [set() for _ in range(N)]
    all_num = set([int(i) for i in range(1, max_edge + 1)])
    print(max_edge)
    for i in range(N - 1):
        a, b = edge[i]
        can_use = all_num - edge_used[a]
        can_use -= edge_used[b]
        for key in can_use:
            print(key)
            edge_used[a] |= {key}
            edge_used[b] |= {key}
            break
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
 
for a, b in ab:
    graph[a-1].append((b-1, -1))
    graph[b-1].append((a-1, -1))
 
# print(graph)
k = 0
for i in graph:
    if k< len(i)+1:
        k = len(i)+1

stack = [(0, -1)]
visited = [-1]*n
 
# k = 0
stack = deque([(0, -1)])
while stack:
    node, color = stack.pop()
    visited[node] = 1
 
    # if k < len(graph[node]):
    #     k = len(graph[node])
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):
        if visited[child] == 1:
            continue
        if tmp == color:
            tmp += 1
        graph[node][i] = (child, tmp)
        stack.append((child, tmp))
        tmp +=1
 
print(k)
for a, b in ab:
   for node, color in graph[a-1]:
       if node == b-1:
           print(color)

Submission status: Wrong Answer

Solution code:
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[]
    w=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        w.append((min(a,b),max(a,b)))
    w.sort()
    for a,b in w:
        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)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

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

used = dict([[i, []] for i in range(1, max([max(a, b) for a, b in ab]) + 1)])

ans = []
for a, b in ab:
    used_2 = set(used[a] + used[b])
    if len(used_2):
        col = min(used_2) - 1
        col = col if col > 0 else max(used_2) + 1
    
    else:
        col = 1
    
    used[a].append(col)
    used[b].append(col)
    ans.append(col)

print(max(ans))
[print(a) for a in ans]

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] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1

L = []
b_color = [1]*N
use_1 = [False]*N
use_1[0] = True
use_1[1] = True
for i in range(N-1):
    L.append(b_color[a[i]])
    b_color[a[i]] += 1
    if i > 0 and use_1[a[i]] == False:
        use_1[b[i]] = True
    if use_1[b[i]]:
        b_color[b[i]] += 1

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

Submission status: Wrong Answer

Solution code:

import heapq
import collections
N =  int(input())
tree = [list(map(int,input().split(" "))) for _ in range(N -1 )]
di = collections.defaultdict(lambda  :[])
node ={}
colors = [0 for _ in range(N + 1)]

for i,temp in enumerate(tree):

    a,b = temp
    node[i] = (a, b)
    di[a].append(b)
    di[b].append(a)
    colors[a]  += 1
    colors[b] += 1


edges = [1 for i in range(N)]
print(*colors[1:])
# for i in range(N):




# for k,v in di:
#     color = max(colors,len(v))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
G = []
for _ in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    G.append(temp)
 
ans = [0] * (N-1)
P = [[0] for _ in range(N)]
j = []
for i in range(N-1):
    temp = G[i]
    for k in range(1,N):
        if k not in P[temp[0]] and k not in P[temp[1]]:
            ans[i] = k
            P[temp[0]].append(k)
            P[temp[1]].append(k)
            if k not in j:
                j.append(k)
            break
print(len(j))
for l in ans:
    print(l)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[a[i]].append(b[i])
        g[b[i]].append(a[i])


    gcc = [len(i) for i in g]
    k = max(gcc)
    gc = [[j for j in range(1,k+1)] for i in g]
    
    ans = []

    for i in range(N-1):
        idx = 0
        if gc[a[i]][0] == gc[b[i]][0]:
            idx = 0
        else:
            idx = -1 
        x = gc[a[i]][idx]
        # print(x, gc[a[i]], gc[b[i]])
        ans.append(x)
        if idx == -1:
            gc[a[i]].pop(-1)
            gc[b[i]].pop(-1)
        else:
            gc[a[i]].pop(0)
            gc[b[i]].pop(0)


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

    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 sys
input = sys.stdin.readline

N = int(input())
tree = [0]*N
ape = [set() for _ in range(N)]
hen = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    tmp = 0
    #hen[i] = max(tree[a-1], tree[b-1])
    while True:
        if tmp in (ape[a-1]|ape[b-1]):
            tmp += 1
            continue
        else:
            hen[i] = tmp
            break
    ape[a-1].add(hen[i])
    ape[b-1].add(hen[i])
    tree[a-1] += 1
    tree[b-1] += 1
print(max(tree))
for i in range(N-1):
    print(hen[i]+1)

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 = 0
for i in range(n-1):
  la = d[a[i]]
  lb = d[b[i]]
  j = 1
  while():
    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
    j += 1
    if m < j:
      m = j
print(m)
for i in range(n-1):
  print(c[i])