Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:
n = int(input())

lst = [set() for _ in range(n + 1)]

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

    not_used = colors - lst[a] - lst[b]

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

    ans.append(x)

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


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

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)
result=[0 for _ in range(n-1)] #各辺の色
for i in range(n-1):
  s=set(result[j] for j in data[edges[i][0]-1]).union(set(result[j] for j in data[edges[i][1]-1]))
  for j in range(colors):
    if j + 1 in s:
      continue
    result[i]=j+1
    break
for r in result:
  print(r)

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()

tree ={ i+1:{} for i in range(N)}

alls={}

output=[]
for i in range(N-1):
    A,B=two_int()
    for i in range(1,N):
        if i not in tree[A] and i not in tree[B]:
            if i not in alls:
                alls[i]=1
            tree[A][i]=1
            tree[B][i]=1
            output.append(i)
            break

print(len(alls))
for i in output:
    print(i)

output

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
L=[{}for i in range(N+1)]
ans=[]
for i in range(N-1):
    a,b=map(int,input().split())
    for j in range(1,N):
        if j not in L[a]:
            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:
import collections

n = int(input())
edge = []
node = [0] * n
edge_color = collections.defaultdict(list)
for _ in range(n-1):
    edge.append(list(map(int, input().split())))

color = 1
ans = []
added_color = [1]
for e in edge:
    if node[e[0]-1] == 0 and node[e[1]-1] == 0:
        ans.append(color)
        edge_color[e[0]-1].append(color)
        edge_color[e[1]-1].append(color)
    else:
        flag = 0
        for a in added_color:
            if a not in edge_color[e[0]-1] and a not in edge_color[e[1]-1]:
                ans.append(a)
                flag = 1
                edge_color[e[0]-1].append(a)
                edge_color[e[1]-1].append(a)
                break
        if flag == 0:
            color += 1
            ans.append(color)
            added_color.append(color)
            edge_color[e[0]-1].append(color)
            edge_color[e[1]-1].append(color)
    node[e[0]-1] += 1
    node[e[1]-1] += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

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(str, colors)))

Submission status: Wrong Answer

Solution code:
n = int(input())
ab_ls = [list(map(int,input().split())) for i in range(n-1)]
ans = 0
ans_max = 0
s = [[0] * n for i in range(n+1)]
for i in range(n-1):
    ans = 0
    for j in range(n):
        if ans in s[ab_ls[i][0]-1]:
            ans += 1
            # print(ab_ls[i][0]-1,ab_ls[i][1]-1)
        else:
            s[ab_ls[i][0]-1][ab_ls[i][1]-1] = ans
            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,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-1):
    # print(s[i])
    print(s[ab_ls[i][0]-1][ab_ls[i][1]-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])
    T = sorted(T)
    C = [set([]) for k in range(N+1)]
    ans = []
    for e in T:
        t = 1
        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:
# -*- coding: utf-8 -*-

N = int(input())
LST = [[0] * 1 for i in range(N + 1)]

for i in range(N - 1):
    X, Y = map(int, input().split())
    LST[X].append(Y)
    LST[Y].append(X)

lenMAX = 1
outputSTR = []
for i in range(len(LST)):
    if lenMAX < len(LST[i]) - 1:
        lenMAX = len(LST[i]) - 1

    for k in range(len(LST)):
        if len(LST[i]) >= len(LST[k]) and (i in LST[k]):
            LST[k].remove(i)

for i in range(len(LST)):
    for j in range(len(LST[i])):
        if j != 0:
            outputSTR.append(j)

print(lenMAX)
for i in outputSTR:
    print(i)

Submission status: Wrong Answer

Solution code:
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]) or (tmp in 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
ma = max(tree)
print(ma)
for i in range(N-1):
    print(hen[i]+1)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

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

for i in range(n-1):
  a, b = nm()
  g[a].append((a,b))

colors = [[] for _ in range(n+1)]
childcolors = [[] for _ in range(n+1)]
maxc = 0

for i in range(1, n):
  num = 1
  for j in range(len(g[i])):
    while True:
      if num not in colors[g[i][j][0]] and num not in childcolors[g[i][j][0]]:
        childcolors[g[i][j][0]].append(num)
        colors[g[i][j][1]].append(num)
        maxc = max(maxc, num)
        break
      num += 1

print(maxc)
for c in colors:
  if len(c) > 0:
    print(c[0])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

for i in tree:
    tmp = len(i)
    ans = max(tmp,ans)

print(ans)

for i in range(1, n):
    if i <= ans:
        print(i)
    else:
        print(i-ans)

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)

    #関係の数字
    a,b = lines[0][0],lines[0][1]
    n=1

    for l in lines:

        if n == 1:
            print(n)
            n+=1
        else:

            if l[0] == a or l[0] == b or l[1] == b:
                print(n)
                n+=1
                
            else:
                print(1)
                n=2

        a,b = l[0],l[1]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
#node=[[] for _ in range(n)]
c_num=[0 for _ in range(n)]
arr=[]
ans=[0 for _ in range(n-1)]
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    arr.append([a-1,b-1])
    #node[a-1].append(b-1)
    #node[b-1].append(a-1)
    c_num[a-1]+=1
    c_num[b-1]+=1
c=max(c_num)
c_arr=[{i for i in range(1,c+1)} for _ in range(n)]
print(c)
for i in range(n-1):
    del_num=list(c_arr[arr[i][0]])[0]
    print(del_num)
    if del_num in c_arr[arr[i][1]]:
        c_arr[arr[i][1]].remove(del_num)
        c_arr[arr[i][0]].remove(del_num)

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
    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())
l=[list(map(int,input().split())) for i in range(n-1)]
l.sort()
#print(l)
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
#print(r)
for i in range(n):
    if aa<=r[i]:
        aa=r[i]
        c=i+1
#print(c)
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
for i in range(n-1):
    if l[i][0]!=c and l[i][1]!=c:
        B=w[l[i][0]-1]+w[l[i][1]-1]
        #print(B)
        for j in range(1,max(r)+1):
            if j not in B:
                p[i]=j
                w[l[i][0]-1].append(j)
                w[l[i][1]-1].append(j)
                break
for i in range(n-1):
    print(p[i])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edge_num = [0]*(N+1)
edges = []
for _ in range(N-1):
    a,b = map(int,input().split())
    edge_num[a] += 1
    edge_num[b] += 1
    edges.append([a,b])
# print(edge_num)
# print(edges)
used_color_table = [[0] for _ in range(N+1)]
#print(used_color_table)

K = max(edge_num)
print(K)
for edge in edges:
    for color in range(1,K+1):
        if not color in used_color_table[edge[0]] and not color in used_color_table[edge[1]]: # use new color
            color_idx = color
            continue
    print(color_idx)
    used_color_table[edge[0]].append((color_idx))
    used_color_table[edge[1]].append((color_idx))

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for i in range(N)]
lines = []
colors = [[] 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].append(color)
    colors[lines[i][1] - 1].append(color)
    ans[i] = color

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

Submission status: Wrong Answer

Solution code:
def f(x):
  return int(x) - 1

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [[int(x) for x in input().split()] for _ in range(N - 1)]

N_dict = {}
for i in range(N):
    N_dict[i + 1] = []

ans_list = []
for i in range(N - 1):
    j = 1
    while True:
        if j in N_dict[AB[i][0]] or j in N_dict[AB[i][0]]:
            j += 1
        else:
            ans_list.append(j)
            N_dict[AB[i][0]].append(j)
            N_dict[AB[i][1]].append(j)
            break
print(max(ans_list))
for i in range(N - 1):
    print(ans_list[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
leaves = {}
values = []
results = []
for i in range(n-1):
    e = input().split()
    if e[0] not in leaves and e[1] not in leaves:
        results.append("1")
        leaves.update({e[0] : 1})  
        leaves.update({e[1] : 1})    
    elif e[0] not in leaves and e[1] in leaves:
        leaves.update({e[0] : 1}) 
        results.append(int(leaves[e[1]])+1)
        leaves[e[1]] += 1
    elif e[0] in leaves and e[1] not in leaves:
        leaves.update({e[1] : 1})
        results.append(int(leaves[e[0]])+1)
        leaves[e[0]] += 1
    else:
        if int(leaves[e[0]]) > int(leaves[e[1]]):
            results.append(int(leaves[e[0]])+1)
        else: 
            results.append(int(leaves[e[1]])+1)
        leaves[e[0]] += 1   
        leaves[e[1]] += 1

for key in leaves:
    values.append(leaves[key])

m = max(values)
print(m)

for r in results:
    print(r)

Submission status: Wrong Answer

Solution code:
import sys
#def input():
#    return sys.stdin.readline()[:-1]

#edges = []

N = int(input())

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

colors = []


for i in range(N-1):
  a, b = map(int, input().split())
  color = max(nodes[a-1], nodes[b-1]) + 1
  nodes[a-1] += 1
  nodes[b-1] += 1
  colors.append(color)
  #edges.append((a,b))

#print(edges)
print(len(set(colors)))
print(*colors, sep="\n", end="")

Submission status: Wrong Answer

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

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      if cc == c:
        c += 1
      dfs(v,u,cc)
    cc += 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Submission status: Wrong Answer

Solution code:
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:
from collections import defaultdict
def solve():
    n = int(input())
    A = defaultdict(list)
    C = [0] * (n + 1)
    D = [0] * (n + 1)
    for i in range(1, n):
        a, b = map(int, input().split())
        A[a].append([b, i])
        C[b] = i
    D[1] = 1
    for a, bi in A.items():
        for i, (b, c) in enumerate(bi, start=1):
            if not D[c]:
                if C[a] == i:
                    D[c] = len(bi) + 1
                else:
                    D[c] = i
    print(len(set(D)) - 1)
    print(*D[1:-1], sep="\n")
solve()

Submission status: Wrong Answer

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

graph = [[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
ans = [float('inf')]*(n+1)
visit = [False] * (n+1)

abc = float('inf')
for aa in range(len(graph[1:])):
    if len(graph[aa])>=3:
        abc=aa
if abc ==float('inf'):
    for aa in range(len(graph[1:])):
        if len(graph[aa])==1:
            bbb = aa
    queque = [bbb]
    visi =[False]*(n+1)
    pppp = 0
    while queque:
        q = queque.pop()
        pppp+=1
        if pppp == (n//2)+1:
            abc = q
            break
        
        visi[q]=True
        for i in graph[q]:
            if not visi[i]:
                visi[i] = True
                queque.append(i)
        
    

que = [abc]

ans[abc]=1
while que:
    q = que.pop()
    visit[q] = True
    for i in graph[q]:
        if not visit[i]:
            visit[i] = True
            que.append(i)
            ans[i]=ans[q]+1
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

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

used = [set() for i in range(N+1)]
answer = []

for a, b in edges:
    cur = 1
    #s = used[a] | used[b]
    while cur in used[a]:
        cur += 1
    answer.append(cur)
    used[a].add(cur)
    used[b].add(cur)

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

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([]) for k in range(N+1)]
    ans = []
    for e in T:
        t = 1
        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:
n = int(input())
tree_i = {}
tree_n = {}
for i in range(n-1):
  a,b = map(int,input().split())
  tree_i[(a,b)] = i
  if a in tree_n:
    tree_n[a].append(b)
  else:
    tree_n[a] = [b]
  if b in tree_n:
    tree_n[b].append(a)
  else:
    tree_n[b] = [a]

ans = [0 for i in range(n-1)]

def coloring(n_b,n,color_b,tree_i,tree_n):
  nodes = tree_n[n]
  color = 0
  for node in nodes:
    if node ==n_b:
      continue
    if color == color_b:
      color += 1
    a = min(n,node)
    b = max(n,node)
    ans[tree_i[(a,b)]] = color
    coloring(n,node,color,tree_i,tree_n)
    color +=1

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
AB = LRI(N - 1)

g = {i : 0 for i in range(1, N + 1)}
for a, b in AB:
    g[a] += 1
    g[b] += 1

k = max(g.values())
print(k)

gk = [[0] for _ in range(N + 1)]
for a, b in AB:
    c = (gk[a][-1] % k) + 1
    print(c)
    gk[a].append(c)
    gk[a].sort()
    gk[b].append(c)
    gk[b].sort()

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
                c = K
            else:
                c = min(nokori)
            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:
N = int(input())
L = [0] * (10 ** 5 + 1)
L_ = [0] * (10 ** 5 + 1)
A = []
for i in range(N-1):
    a, b = map(int, input().split())
    A.append((a, b))
    L[a] += 1
    L[b] += 1
m = max(L)
print(m)
for i in range(N - 1):
    a, b = A[i]
    print(max(L_[a], L_[b])+1)
    L_[a] += 1
    L_[b] += 1

Submission status: Wrong Answer

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

abd = {}
for a, b in ab:
  abd[a] = abd.get(a,set())
  abd[a].add(len(abd[a]) + 1)
  
  abd[b] = abd.get(b,set())
  abd[b].add(len(abd[b]) + 1)

rk = max([len(x) for x in abd.values()])
print(rk)

for a, b in ab:
  c = abd[a].pop()
  abd[b].discard(c)
  print(c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#abc146_d
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

ai=[]
bi=[]
count = [0 for i in range(n+1)]

#print(count)
for i in range(n-1):
	tmp = input().split()
	a,b = list(map(lambda a: int(a), tmp))
	ai.append(a)
	bi.append(b)
	count[a]+=1
	count[b]+=1
#print(count)

maxapexcount=count[1]
maxapexno=1
for i in range(n+1):
	if(count[i]>maxapexcount):
		maxapexcount=count[i]
		maxapexno=i
print(maxapexcount)





listtmp = [[0 for i in range(n+1)] for j in range(n+1)]
k=0
for i in range(n-1):
	for j in range(1,n+1):
		tmp=((k+j-1)%maxapexcount)+1
		#print(tmp)
		if(listtmp[ai[i]][tmp]!=1)and(listtmp[bi[i]][tmp]!=1):
			listtmp[ai[i]][tmp]=1
			listtmp[bi[i]][tmp]=1
			print(tmp)
			k=tmp
			break

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())
    l = pcol[a] if pcol[a] > pcol[b] else pcol[b]
    for colo in range(l, n-1):
        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:
                while (not use[a][pcol[a]]) and pcol[a] < n-2:
                    pcol[a] += 1
            if pcol[b] == colo:
                while (not use[b][pcol[b]]) and pcol[b] < n-2:
                    pcol[b] += 1
            if colors < colo:
                colors = colo
            break
print(colors+1)
for co in brcol:
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
#def input():
#    return sys.stdin.readline()[:-1]

#edges = []

N = int(input())

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

colors = []


for i in range(N-1):
  a, b = map(int, input().split())
  color = max(nodes[a-1], nodes[b-1]) + 1
  nodes[a-1] += 1
  nodes[b-1] += 1
  colors.append(color)
  #edges.append((a,b))

#print(edges)
print(len(set(colors)))
print(*colors, sep="\n")

Submission status: Wrong Answer

Solution code:
class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}

    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def print_graph(self):
        print(self.adjacency_dict)


if __name__ == "__main__":
    n = int(input())
    ab = list()
    for i in range(n-1):
        ab.append(list(map(int, input().split())))

    # 双方向でnodeを張って、数を数える
    graph = Graph()
    for i in range(n):
        graph.add_vertex(i)
    for e in ab:
        graph.add_edge(e[0]-1, e[1]-1)

    color_num = 0
    for i in range(n):
        color_num = max(color_num, len(graph.adjacency_dict[i]))

    print(color_num)

    count = 1
    start = 0
    end = 0

    for i in range(n-1):
        if start == ab[i][0] or end == ab[i][1] or end == ab[i][0]:
            print(count)
        else:
            count = 1
            print(count)
        count += 1
        start = ab[i][0]
        end = ab[i][1]

Submission status: Wrong Answer

Solution code:
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())
    hen[i] = max(tree[a-1], tree[b-1])
    while True:
        if (hen[i] in ape[a-1]) or (hen[i] in ape[b-1]):
            hen[i] -= 1
        else:
            break
    ape[a-1].add(hen[i])
    ape[b-1].add(hen[i])
    tree[a-1] += 1
    tree[b-1] += 1
ma = max(tree)
print(ma)
for i in range(N-1):
    print(hen[i]+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
#node=[[] for _ in range(n)]
c_num=[0 for _ in range(n)]
arr=[]
ans=[0 for _ in range(n-1)]
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    arr.append([a-1,b-1])
    #node[a-1].append(b-1)
    #node[b-1].append(a-1)
    c_num[a-1]+=1
    c_num[b-1]+=1
c=max(c_num)
c_arr=[[i for i in range(1,c+1)] for _ in range(n)]
print(c)
for i in range(n-1):
    try:
        del_num=c_arr[arr[i][0]].pop(0)
        print(del_num)
    except:
        print("hofe")
        exit()
    if del_num in c_arr[arr[i][1]]:
        c_arr[arr[i][1]].remove(del_num)

Submission status: Wrong Answer

Solution code:
n=int(input())
ltmp=[0 for i in range(n)]
l=[list(map(int,input().split())) for _ in range(n-1)]
for i in l:
    ltmp[i[0]-1]+=1
    ltmp[i[1]-1]+=1
d=max(ltmp)
lans=[set() for i in range(n)]
print(d)
for i in l:
    for j in range(d):
        if j+1 not in lans[i[0]-1] and j+1 not in lans[i[1]-1]:
            lans[i[0]-1].add(j+1)
            lans[i[1]-1].add(j+1)
            print(j+1)
            break

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())

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

for _ in range(N - 1):
  a, b = (int(i) for i in input().split(' '))
  
  lsttmp = copy.copy(lst[a])
  lsttmp.extend(lst[b])
  lsttmp = list(set(lsttmp))
  
  cnt = 1
  while True:
    if not(cnt in lsttmp):
      break
    
    cnt += 1
  
  ans.append(cnt)
  lst[a].append(cnt)
  lst[b].append(cnt)

ans.insert(0, max(ans))

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

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
a,b,c,d=[],[],[],[]
for i in range(n):
    b.append([])
for i in range(n-1):
    a.append(list(map(int,input().split())))
for i in range(n-1):
    j=0
    d.append(a[i][0])
    d.append(a[i][1])
    while True:
        if j not in b[a[i][0]-1] and j not in b[a[i][1]-1]:
            c.append(j)
            b[a[i][0]-1].append(j)
            b[a[i][1]-1].append(j)
            break
        j+=1
print(collections.Counter(d).most_common()[0][1])
for i in range(n-1):
    print(c[i]+1)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

#print(mylist)

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

for i in range(1, len(mylist)):
    color = 0
    for j in range(len(mylist[i])):
        if mylist[i][j] > i:
            if color%(myans)+1 not in myanslist[i-1]: 
                myanslist[i] += [color%(myans)+1]
                color += 1
            else:
                color += 1
                myanslist[i] += [color%(myans)+1]
                color += 1
#print(myanslist)
        
for i in range(1, len(myanslist)):
    for j in myanslist[i]:
        print(j)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
c = [set() for i in range(n)]
cnt = [0 for i in range(n)]

for i in range(n - 1):
  _a, _b = map(int, input().split())
  cnt[_a - 1] += 1
  cnt[_b - 1] += 1
  a[i] = _a
  b[i] = _b

color = max(cnt)
print(color)

for i in range(n - 1):
  s = c[a[i] - 1] | c[b[i] - 1]
  for j in range(color):
    if j not in s:
      c[a[i] - 1].add(j)
      c[b[i] - 1].add(j)
      print(j + 1)
      break