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:
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[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=v[col]
                dc[(c,i)]=col
                dc[(i,c)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+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[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=v[col]
                dc[(c,i)]=col
                dc[(i,c)]=col
            col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+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==1:
        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
                dc[(i,c)]=col
#                show(i,c,col)
                col+=1
    return

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [[] for _ in range(n+1)] #0は空になる
edge = {} #辞書
for i in range(n-1):
    a,b = map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
    edge[(a,b)] = i
    
from collections import deque
que = deque()
que.append(1)
seen = [-1] * (n+1) #0は空になる 見たことあるか 
ans = [0]*(n-1) #辺の色
while que:
    p = que.pop()
    color = 1
    for i in ab[p]: #接している点を得る
        if seen[i] == 0:#その点から周辺を見た場合は無視
            color += 1
        else:
            ans[edge[(p,i)]] = color
            que.append(i)
            color += 1
    seen[p] = 0

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

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==1:
        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
#                show(i,c,col)
                col+=1
    return

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    # {node: {target: chain_index}}
    node_relation = {i: {} for i in range(NODE_N)}
    # {index: color}
    chain_color = {i: None for i in range(CHAIN_N)}
    # {node : set(color)}
    node_has_color = {i: set() for i in range(NODE_N)}

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1

        node_relation[node][target] = i
        node_relation[target][node] = i

    list_node_relation = list(node_relation.items())
    list_node_relation.sort(key=lambda x: len(x[1]))

    for node, targets_index in list_node_relation:
        for target, index in targets_index.items():
            if chain_color[index] is not None:
                continue

            color = 1
            # search color
            while color in node_has_color[node] or color in node_has_color[target]:
                color += 1

            chain_color[index] = color
            node_has_color[node].add(color)
            node_has_color[target].add(color)

    ret = [0]
    color_set = set()
    for i in range(CHAIN_N):
        color = chain_color[i]
        ret.append(color)
        if color not in color_set:
            ret[0] += 1
            color_set.add(color)

    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)

Submission status: Wrong Answer

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

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

print(max(ans)[0])
ans=sorted(ans, key=lambda x:x[1])
for i in range(2,n+1):
    print(ans[i][0])

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==1:
        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(max(v)+1)
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==1:
        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:
# -*- coding: utf-8 -*-

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

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[[0]*N for i in range(N)]
for i in range(N-1):
    arr[val[i][0]-1].add(val[i][1]-1)
    arr[val[i][1]-1].add(val[i][0]-1)
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=set(colall)
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp.pop()
    colarr[min(flag,f)][max(flag,f)]=p
    col[f].add(p)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]
reach={flag}

for i in range(N-1):
    for t in que[i]:
        coltemp=colall^(colall&col[t])
        arrtemp=arr[t]^(reach&arr[t])
        que[i+1]=que[i+1] | arrtemp
        reach.add(t)
        for f in arrtemp:
            p=coltemp.pop()
            col[f].add(t)
            colarr[min(t,f)][max(t,f)]=p
print(colmax)
for i in range(N-1):
    print(colarr[val[i][0]-1][val[i][1]-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import copy
def main():
    N = int(input())
    sides = [[int(s) for s in input().split()] for i in range(N-1)]

    # まず最大次数を探す
    sides = sorted(sides)
    max_degree = 0
    current = 1
    current_degree = 0
    for side in sides:
        if side[0]==current:
            current_degree += 1
        else:
            current = side[0]
            current_degree = 2 #見ている頂点が変わるということは、1つ前の頂点から必ず1つ辺が出ているため
        max_degree = max(current_degree,max_degree)
    
    # 上から順番見ていくと、既に使われている色はひとつだけなので、それを除いて塗っていくだけでいい
    # 使用可能な色リスト
    color_list = [i for i in range(1,max_degree+1)]
    color_lists = []
    for i in range(N):
        color_lists.append(copy.copy(color_list))

    sides_color = []
    current = 0
    for side in sides:
        choose_color = color_lists[side[0]-1].pop(0)
        sides_color.append(choose_color)
        color_lists[side[1]-1].remove(choose_color) #次の頂点が使用可能な色から使用済の色を除く

    print(max_degree)
    for color in sides_color:
        print(color)    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
l.sort()
r=[0]*n
for i in range(n-1):
    r[l[i][0]-1]+=1
    r[l[i][1]-1]+=1
aa=0
c=0

for i in range(n):
    if aa<=r[i]:
        aa=r[i]
        c=i+1

A=1;print(max(r))
p=[0]*(n-1)
w=[[] for _ in range(n)]
for i in range(n-1):
    if l[i][0]==c or l[i][1]==c:
        p[i]=A
        w[l[i][0]-1].append(A)
        w[l[i][1]-1].append(A)
        A+=1

box=set([i for i in range(1,max(r)+1)])
for i in range(n-1):
    if l[i][0]!=c and l[i][1]!=c:
        B=box-set(w[l[i][0]-1]+w[l[i][1]-1])
        print(B)
        w[l[i][0]-1].append(list(B)[0])
        w[l[i][1]-1].append(list(B)[0])
        p[i]=list(B)[0]

#print(r,c,w)
#print(p)

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

Submission status: Wrong Answer

Solution code:
from collections import  deque

N = int(input())
dic = {}

for i in range(N - 1):
    a, b = map(int, input().split())
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]
ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
print(ans1)
no = 0
ans2 = [[] for i in range(N + 1)]
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1]))

while len(q) > 0:
    i, l = q.popleft()
    num = 1
    #print(f'頂点{i}に関しての色使い情報{Used[i]}')
    while True:
        if num in Used[i]:
            num += 1
        else:
            break

    for k in l:
        if k < i:
            continue
        #print(f'頂点{i}から{k}に色{num}を割り当て')
        ans2[i].append(num)
        Used[i].append(num)
        Used[k].append(num)

        while True:
            if num in Used[i]:
                num += 1
            else:
                break
        q.append((k, dic[k]))

for l in ans2:
    for k in l:
        print(k)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
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
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{}{}".format(num,G[num][i])]=color
                edge["{}{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{}{}".format(num,G[num][i])]=color
                edge["{}{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

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

    print(edge["{}{}".format(ab[i][0],ab[i][1])])

Submission status: Wrong Answer

Solution code:
from collections import  deque

N = int(input())
dic = {}

for i in range(N - 1):
    a, b = map(int, input().split())
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]
ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
print(ans1)
no = 0
ans2 = [[] for i in range(N + 1)]
Used = [[] for i in range(N + 1)] #頂点において使った番号を記録
q = deque()

q.append((1, dic[1]))

while len(q) > 0:
    i, l = q.popleft()
    num = 1
    while True:
        if num in Used[i]:
            num += 1
        else:
            break

    for k in l:
        if k < i:
            continue
        ans2[i].append(num)
        Used[i].append(num)
        Used[k].append(num)

        while True:
            if num in Used[i]:
                num += 1
            else:
                break
        q.append((k, dic[k]))

for l in ans2:
    for k in l:
        print(k)

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:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
e = []
queue = deque([])
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(temp)
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
ans = [[0] * N for _ in range(N)]
def bfs(x):
    for i in G[x]:
        if ans[x][i] ==0 and ans[i][x] == 0:
            queue.append(i)
            for k in range(N):
                if k not in nuc[x] and k not in nuc[i]:
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    auc.append(k)
                    break
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m[0]][m[1]])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

n = int(input())

tree = defaultdict(list)

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

def bfs(src, p):
	que = deque([(src, p)])
	color = [None]*(n+1)
	color[src] = 0
	max_val = 0
	while que:
		u, p = que.popleft()
		next_color = 1
		for i, v in enumerate(tree[u]):
			if v != p:
				if color[u] == next_color:
					next_color += 1
				color[v] = next_color
				max_val = max(max_val, next_color)
				que.append((v, u))
				next_color += 1
	return max_val, color

max_color, color = bfs(1, -1)
print(max_color)
for ele in color[2:]:
	print(ele )

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

n = int(input())

tree = defaultdict(list)

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

def bfs(src, p):
	que = deque([(src, p)])
	color = [None]*(n+1)
	color[src] = 0
	max_val = 1
	while que:
		u, p = que.popleft()
		next_color = 1
		for i, v in enumerate(tree[u]):
			if v != p:
				if color[u] == next_color:
					next_color += 1
				color[v] = next_color
				max_val = max(max_val, next_color)
				que.append((v, u))
				next_color += 1
	return max_val, color

max_color, color = bfs(1, -1)
print(max_color)
for ele in color[2:]:
	print(ele )

Submission status: Wrong Answer

Solution code:
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.adj = []
        self.edges = []
        #self.pec = None
        self.pec = 0
    # def __init__(self):
    #     self.adj = []

n = int(input())
ab = []
nodes = [None] * n

cntMap = {}

def addCount(v1, v2):
    if v1 not in cntMap:
        cntMap[v1] = 1
    else:
        cntMap[v1] += 1
    if v2 not in cntMap:
        cntMap[v2] = 1
    else:
        cntMap[v2] += 1

for i in range(n-1):
    v1, v2 = map(int, input().split())
    addCount(v1, v2)
    ab.append([v1, v2])
    nodeAidx = v1-1
    nodeBidx = v2-1
    nodeA = None
    nodeB = None
    if nodes[nodeAidx] is None:
        nodeA = Node(v1)
        nodes[nodeAidx] = nodeA
    else:
        nodeA = nodes[nodeAidx]
    if nodes[nodeBidx] is None:
        nodeB = Node(v2)
        nodes[nodeBidx] = nodeB
    else:
        nodeB = nodes[nodeBidx]
    nodeA.adj.append(nodeB)

#print(ab)
#print(nodes)
root = nodes[0]
nodes[1].pec = 1
q = deque()
q.append(root)

temp = list(cntMap.values())
temp.sort()
maxV = temp[-1]
print(maxV)
# eNums = []
# for i in range(1, maxV+1):
#     eNums.append(i)
used = set()
#used.add(1)

while q:
    used.clear()
    node = q.popleft()
    #print(node.val)
    pec = node.pec
    used.add(pec)

    for i in range(len(node.adj)):
        a = node.adj[i]
        for j in range(1, maxV+1):
            if j not in used:
                a.pec = j
                used.add(j)
                break

        # if pec < maxV:
        #     a.pec = pec + i + 1
        # else:
        #     a.pec = pec - i - 1
        print(a.pec)
        q.append(a)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())

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

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

def dfs(start,now):
    new_col = 1
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            if new_col in ten_col[now-1]:
                new_col += 1
            ten_col[now-1].append(new_col)
            ten_col[future-1].append(new_col)
            ans[i] = new_col

            dfs(now,future)
            
dfs(-1,1)

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

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5)

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0
for i in range(n):
    me = max(me, len(e[i]))
print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

print(me)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

N = int(input())
edge = [[] for _ in range(N)]
v_dic = {}
for _ in range(N-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge[a].append(b)
    if a not in v_dic:
        v_dic[a] = 1
    else:
        v_dic[a] += 1
    if b not in v_dic:
        v_dic[b] = 1
    else:
        v_dic[b] += 1
colors = [0 for _ in range(N-1)]


def bfs(p_node, p_color):
    children_node = edge[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node-1] = c_color
        bfs(child_node, c_color)
        c_color += 1


def solve():
    bfs(0, 0)

    print(max(v_dic.values()))
    for color in colors:
        print(color)


if __name__ == '__main__':
    solve()

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

S = {}
answer = []

def search_number(a_list, b_list):
    for i in range(1, N):
        if i not in a_list and i not in b_list:
            a_list.append(i)
            b_list.append(i)
            answer.append(i)
            return


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

    if b not in S:
        S[b] = []

    search_number(S[a], S[b])
print(max(answer))
for a in answer:
    print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
beforeColor = [0]*n
numColors = [0]*n
out = [0]*(n-1)
max = 0


In = []
for i in range(n-1):
  a, b = map(int, input().split())
  In.append(a * 10**6 + b)
In.sort()

for i in range(n-1):
  a = In[i]//(10**6)
  b = In[i]%(10**6)
  numColors[a-1] += 1
  if max < numColors[a-1]:
    max = numColors[a-1]
    color = numColors[a-1]
  else:
    if numColors[a-1]-1 < beforeColor[a-1]:
      color = numColors[a-1]-1
    else:
      color = numColors[a-1]
  out[i] = color
  beforeColor[b-1] = color
  numColors[b-1] += 1
  
print(max)
for i in range(len(out)):
  print(out[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
beforeColor = [0]*n
numColors = [0]*n
out = [0]*(n-1)
max = 0


In = []
for i in range(n-1):
  a, b = map(int, input().split())
  In.append(a * 10**6 + b)

for i in range(n-1):
  a = In[i]//(10**6)
  b = In[i]%(10**6)
  numColors[a-1] += 1
  if max < numColors[a-1]:
    max = numColors[a-1]
    color = numColors[a-1]
  else:
    if numColors[a-1]-1 < beforeColor[a-1]:
      color = numColors[a-1]-1
    else:
      color = numColors[a-1]
  out[i] = color
  beforeColor[b-1] = color
  numColors[b-1] += 1
  
print(max)
for i in range(len(out)):
  print(out[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
beforeColor = [0]*n
numColors = [0]*n
out = [0]*(n-1)
max = 0


for i in range(n-1):
  a, b = map(int, input().split())
  
  numColors[a-1] += 1
  if max < numColors[a-1]:
    max = numColors[a-1]
    color = numColors[a-1]
  else:
    if numColors[a-1]-1 < beforeColor[a-1]:
      color = numColors[a-1]-1
    else:
      color = numColors[a-1]
  out[i] = color
  beforeColor[b-1] = color
  numColors[b-1] += 1

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ab_ls = [list(map(int,input().split())) for i in range(n-1)]
ans = 0
ans2 = 0
ans_max = 0
s = [[0] * n for i in range(n+1)]
for i in range(n-1):
    ans = 0
    ans2 = 0
    for j in range(n+99):
        if ans in s[ab_ls[i][0]-1]:
            ans += 1
            # print(ab_ls[i][0]-1,ab_ls[i][1]-1)
        elif ans2 in s[ab_ls[i][1]-1]:
            ans2 += 1
        else:
            s[ab_ls[i][0]-1][ab_ls[i][1]-1] = max(ans,ans2)
            s[ab_ls[i][1]-1][ab_ls[i][0]-1] = s[ab_ls[i][0]-1][ab_ls[i][1]-1]
            # print(ab_ls[i][0]-1,ab_ls[i][1]-1)
            
            ans_max = max(ans,ans2,ans_max)
            break

    # s[ab_ls[i][0]-1][ab_ls[i][1]-1] = max(s[ab_ls[i][0]-1]) + 1
    # s[ab_ls[i][1]-1][ab_ls[i][0]-1] = s[ab_ls[i][0]-1][ab_ls[i][1]-1]
            
# for i in range(n):
    # print(s[i])
print(ans_max)
# for i in range(n):
#     print(s[i])
for i in range(n-1):
    print(s[ab_ls[i][0]-1][ab_ls[i][1]-1])

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)

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


def dfs(node, pc):
    color = 1
    if color == pc:
        color += 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            ec[idx] = color

            dfs(to, color)
            color += 1


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