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())
L=[[] for i in range(n)]
ans=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    c=1
    while True:
        if c in L[a]:
            c+=1
            continue
        if c in L[b]:
            c+=1
            continue
        break
    ans.append(c)
    L[a].append(c)
    L[b].append(c)
print(max(ans))
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
def find_min_color(colors, a, b):
    color = 1
    while True:
        if color not in colors[a] and color not in colors[b]:
            return color
        color += 1


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]

    color_list = []
    colors = {i + 1: set() for i in range(n)}
    k = 0

    for edge in edges:
        a, b = edge
        min_color = find_min_color(colors, a, b)
        color_list.append(min_color)
        k = max(k, min_color)
        colors[a].add(min_color)
        colors[b].add(min_color)

    print(k)
    print('\n'.join(map(str, color_list)))


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(N: int, a: "List[int]", b: "List[int]"):
    ca = collections.Counter(a)
    cb = collections.Counter(b)
    K = 0
    for i in ca.keys():
        K = max(K, ca[i] + cb[i])
    print(K)
    print(1)
    c = 1
    for i in range(1, N-1):
        cnt = 0
        for j in [a[i-1], b[i-1]]:
            if j not in [a[i], b[i]]:
                cnt += 1
        if cnt == 2:
            print(1)
            c = 1
            continue
        c += 1
        print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
el = defaultdict(lambda :[])
for i in range(n-1):
    a, b = iip()
    el[a-1].append((b-1, i))
    el[b-1].append((a-1, i))

#print(el)

def main():
    color = [None for i in range(n-1)]
    cmax = 0
    que = deque()
    que.append((0, 0))

    while que:
        parent, used_color =que.popleft()
        children = el[parent]
        cn = 1

        for child, edge_num in children:
            el[child].remove((parent, edge_num))

            if cn == used_color:
                cn += 1
            color[edge_num] = cn
            cmax = max(cn, cmax)
            cn += 1

            que.append((child, cn))

    print(cmax)
    for i in color:
        print(i)



main()

Submission status: Wrong Answer

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
el = defaultdict(lambda :[])
for i in range(n-1):
    a, b = iip()
    el[a-1].append((b-1, i))
    el[b-1].append((a-1, i))

print(el)

def main():
    color = [None for i in range(n-1)]
    cmax = 0
    que = deque()
    que.append((0, 0))

    while que:
        parent, used_color =que.popleft()
        children = el[parent]
        cn = 1

        for child, edge_num in children:
            el[child].remove((parent, edge_num))

            if cn == used_color:
                cn += 1
            color[edge_num] = cn
            cmax = max(cn, cmax)
            cn += 1

            que.append((child, cn))

    print(cmax)
    for i in color:
        print(i)



main()

Submission status: Wrong Answer

Solution code:
N=int(input())

A=[[] for _ in range(N)]
B=[]
m=0

for _ in range(N-1):
    a,b=map(int,input().split())
    c=0
    while True:
        c+=1
        if c not in A[a-1] and c not in A[b-1]:
            B.append(c)
            A[a-1].append(c)
            A[b-1].append(c)
            m=max(m,c)
            break

print(m)
for i in range(N-1):
    print(B[i])

Submission status: Wrong Answer

Solution code:
N=int(input())

A=[[] for _ in range(N)]
B=[]
m=0

for _ in range(N-1):
    a,b=map(int,input().split())
    c=0
    while True:
        c+=1
        if c not in A[a-1]:
            B.append(c)
            A[a-1].append(c)
            A[b-1].append(c)
            m=max(m,c)
            break

print(m)
for i in range(N-1):
    print(B[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    graph = [set() for _ in range(N+1)]
    for a, b in ab:
        graph[a].add(b)
        graph[b].add(a)

    d = deque()
    d.append(1)

    ans = [-1] * (N+1)

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    ans = ans[2:]
    print(max(ans))
    print("\n".join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#146_D
import queue

def swap(x, y):
    if x > y:
        x, y = y, x
    return (x, y)

n = int(input())

edges = [[] for _ in range(n)]
edges_dict = {}
ans = [0 for _ in range(n-1)]
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    edges_dict[(a-1, b-1)] = i
    
k, k_idx = 0, 0
for i in range(n):
    if len(edges[i]) > k:
        k = len(edges[i])
        k_idx = i

que = queue.Queue()
que.put((k_idx, 0))
while not que.empty():
    q, x = que.get()
    tmp = 0
    for to in edges[q]:
        if ans[edges_dict[swap(q, to)]] != 0:
            continue
        if tmp == x:
            tmp += 1
        ans[edges_dict[swap(q, to)]] = tmp
        que.put((to, tmp))
        tmp += 1
            
print(k)
print(*ans, sep= '\n')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for i in range(n)]
num = 0

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

    e[a-1].append([b-1,i])
    e[b-1].append([a-1,i])
    num = max(num,len(e[a-1]),len(e[b-1]))

ans = [-1]*(n-1)
ans[0] = 1
q = deque([])
q.append((0,1))
q.append((1,1))
while q:
    bef,pn = q.popleft()
    for cn,nex in enumerate(e[bef]):
        if ans[nex[1]] == -1:
            if pn+cn > num:
                ans[nex[1]] = (pn+cn)%num
            else:
                ans[nex[1]] = pn+cn
            q.append((nex[0],ans[nex[1]]))

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

Submission status: Wrong Answer

Solution code:
num = int(input())
line_list = []
ans = []

for i in range(num - 1):
    a, b = map(int, input().split())
    s = 1
    if i == 0:
        line_list.append({a, b})
        ans.append(s)
    else:
        while s <= len(line_list):
            if not a in line_list[s - 1] and not b in line_list[s - 1]:
                line_list[s - 1].add(a)
                line_list[s - 1].add(b)
                ans.append(s)
                break
            else:
                s += 1
        else:
            line_list.append({a, b})
            ans.append(s)

print(len(line_list))
for item in ans:
    print(item)

Submission status: Wrong Answer

Solution code:
n = int(input())
# s = input()
c = []
hen = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    hen[a-1].append(b-1); hen[b-1].append(a-1)
    c.append([a-1,b-1])

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

child = [[] for _ in range(n)]
for [a,b] in c:
    color = 1
    while (color in child[a]) or (color in child[b]):
        color += 1

    child[a].append(color)
    child[b].append(color)
    print(color)

Submission status: Wrong Answer

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
# a = list(map(int, input().split()))
n = int(input())
# s = input()
c = []
hen = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    hen[a-1].append(b-1); hen[b-1].append(a-1)
    c.append([a-1,b-1])

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

child = [[] for _ in range(n) ]
for [a,b] in c:
    # print(a,b)
    color = 1
    # print(child[b])
    while color in child[a] or color in child[b]:

        color += 1
    child[a].append(color)
    child[b].append(color)
    print(color)

Submission status: Wrong Answer

Solution code:
n = int(input())
# s = input()
c = []
hen = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    hen[a-1].append(b-1); hen[b-1].append(a-1)
    c.append([a-1,b-1])

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

num = [0] * n
for i in c:
    color = 1
    color = max(num[i[0]],num[i[1]]) + 1
    num[i[0]] += 1
    num[i[1]] += 1
    print(color)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)
M = 0

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

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    M = max(M,MA[now])
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

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

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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


for i in range(N):
    heapq.heapify(color[i])

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

    else:
        if color[a-1]:
            if color[a-1][0] != 1:
                mim = heapq.heappop(color[a-1])
                heapq.heappush(color[a-1],mim)
                heapq.heappush(color[a-1],mim-1)
                heapq.heappush(color[b-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[a-1][-1]
                heapq.heappush(color[a-1],nax+1)
                heapq.heappush(color[b-1],nax+1)
                ans[i] = nax+1
        else:
            if color[b-1][0]!= 1:
                mim = heapq.heappop(color[b-1])
                heapq.heappush(color[b-1],mim)
                heapq.heappush(color[b-1],mim-1)
                heapq.heappush(color[a-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[b-1][-1]
                heapq.heappush(color[b-1],nax+1)
                heapq.heappush(color[a-1],nax+1)
                ans[i] = nax+1

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

N = int(input())

edges = [[] for i in range(N+1)]
color = [0 for i in range(N-1)]

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

root = -1
MAX = 0

for i in range(N+1):
    if MAX < len(edges[i]):
        root = i
        MAX = len(edges[i])

K = MAX

def dfs(parent,v,c):
    for i in range(len(edges[v])):
        if edges[v][i][0] != parent:
            color[edges[v][i][1]] = (c+i+1)%K
            dfs(v,edges[v][i][0],(c+i+1)%K)

dfs(-1,root,0)

print(K)

for i in color:
    if i == 0:
        print(K)
    else:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

N = int(input())

edges = [[] for i in range(N+1)]
color = [0 for i in range(N-1)]

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

root = -1
MAX = 0

for i in range(N+1):
    if MAX < len(edges[i]):
        root = i
        MAX = len(edges[i])

K = MAX

def dfs(parent,v,c):
    for i in range(len(edges[v])):
        if edges[v][i][0] != parent:
            color[edges[v][i][1]] = (c+i)%K
            print(color)
            dfs(v,edges[v][i][0],(c+i)%K)

dfs(-1,root,0)

print(K)

for i in color:
    if i == 0:
        print(K)
    else:
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
E = [[] for _ in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
color_num = max(len(E[i]) for i in range(N+1))
print(color_num)
color = [0]*(N+1)

start = 1
q = deque([start])
while(q):
    v = q.pop()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == color[v])
        color[u] = c
        q.append(u)
for i in range(N-1):
    print(color[ab[i][1]])

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
E = [[] for _ in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
    E[ab[i][1]].append(ab[i][0])
#print(E)
color_num = max(len(E[i]) for i in range(N+1))
print(color_num)
color = [[] for i in range(N+1)]
for i in range(N-1):
    for j in range(1,color_num+1):
        if(j not in color[ab[i][0]] and j not in color[ab[i][1]]):
            color_id = j
            break
    print(color_id)
    color[ab[i][0]].append(color_id)
    color[ab[i][1]].append(color_id)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
A=[]
B=[0]*(n-1)
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  A.append(a*10**6+b)
D=dict(zip(A,B))
ans=0
for i in range(n):
  if len(G[i])>ans:
    ans=len(G[i])
    a=i
print(ans)
VC=[10**6]*n #各頂点と親を結ぶ辺の色を記憶
#aを根とする木をDFS
E=[0]*n
E[a]=1
F=deque([a])
while len(F)>0:
  s=F[0]
  F.popleft()
  c=1
  for i in range(len(G[s])):
    if E[G[s][i]]==0:
      F.append(G[s][i])
      E[G[s][i]]=1
      if c==VC[s]:
        c=c+1
      VC[G[s][i]]=c
      t=s
      D[min(s+1,G[s][i]+1)*10**6+max(s+1,G[s][i]+1)]=VC[G[s][i]]
      c=c+1
for i in D.values():
  print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    ab = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
        ab.append([a, b])
    queue = deque([1])

    # 木の親を決める
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    # 色番号を割り当てる
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

    print(max(color[2:]))
    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])
    print(color)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    queue = deque([1])

    # 木の親を決める
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    # 色番号を割り当てる
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

    print(max(color[2:]))
    for c in color[2:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    for i in range(1, vertex):
        a, b = map(int, input().split())
        tree[a].append((b, i))
        tree[b].append((a, i))
    max_deg = 0
    root = 0
    for i in range(1, vertex):
        if max_deg < len(tree[i]):
            root = i
            max_deg = len(tree[i])
    queue = deque([root])
    while not queue == deque():
        color_list = [i for i in range(1, max_deg + 1)]
        now = queue.pop()
        for i, n in enumerate(tree[now]):
            if color[n[0]] == 0:
                color[n[0]] = color_list[0]
                queue.append(n[1])
                color_list.pop(0)
            else:
                if color[n[0]] in color_list:
                    color_list.remove(color[n[0]])
    print(max_deg)
    for c in color[2:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    for i in range(1, vertex):
        a, b = map(int, input().split())
        tree[a].append((b, i))
        tree[b].append((a, i))
    max_deg = 0
    root = 0
    for i in range(1, vertex):
        if max_deg < len(tree[i]):
            root = i
            max_deg = len(tree[i])
    queue = deque([root])
    while not queue == deque():
        color_list = [i for i in range(1, max_deg + 1)]
        now = queue.popleft()
        for i, n in enumerate(tree[now]):
            if color[n[0]] == 0:
                color[n[0]] = color_list[0]
                queue.append(n[1])
                color_list.pop(0)
            else:
                if color[n[0]] in color_list:
                    color_list.remove(color[n[0]])
    print(max_deg)
    for c in color[2:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

li = [[] for i in range(n+1)]

ans = []

for _ in range(n-1):
    a,b = map(int, input().split())
    # print(a,b)
    # print(li)
    for k in range(1,n+1):
        if (k not in li[a]) and (k not in li[b]):
            li[a].append(k)
            li[b].append(k)
            break
    ans.append(k)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

li = [[] for i in range(n+1)]

ans = []

for _ in range(n-1):
    a,b = map(int, input().split())
    # print(a,b)
    # print(li)
    k = 1
    while True:
        if (k not in li[a]) and (k not in li[b]):
            li[a].append(k)
            li[b].append(k)
            break
        else:
            k+=1
    ans.append(k)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
key = [0]*n
child = [[] for i in range(n)]
input_order = [0]*(n-1)

for i in range(n-1):
    a, b = map(int, input().split())
    input_order[i] = [a-1, b-1]
    key[a-1] += 1
    key[b-1] += 1
    child[a-1].append([a-1, b-1])

ans = max(key)
print(ans)
color = [[0]*n for i in range(n)]
color_min = [1]*n
yet = [[False]*n for i in range(n)]
not_yet = deque(child[0])

#本番   
while len(not_yet) > 0:
    key = not_yet.popleft()
    a, b = key[0], key[1]
    color[a][b] = max([color_min[a], color_min[b]])
    if color[a][b] == color_min[a]:
        color_min[a] += 1
    if color[a][b] == color_min[b]:
        color_min[b] += 1
    
    for value in child[b]:
        if yet[value[0]][value[1]] == True:
            continue
        not_yet.append(value)
        yet[value[0]][value[1]] = True

for i in range(n-1):
    a, b = input_order[i][0], input_order[i][1]
    print(color[a][b])

Submission status: Wrong Answer

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


def dfs(graph, hist, color, now, depth, clr):
    hist[now] = 1
    color[now] = clr + 1
    for clr, cld in enumerate(graph[now]):
        if hist[cld] == 0:
            dfs(graph, hist, color, cld, depth+1, depth+clr)
    return 0


N = int(input())

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

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

hist = [0] * (N + 1)
color = [0] * (N + 1)
dfs(graph, hist, color, 1, 0, 0)
print(max(color))
for c in color[2:]:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
graph = defaultdict(list)
def int_(num_str):
    return int(num_str) - 1
parents = [0]*N
parents[0] = N-1
for _ in range(N-1):
    a, b = map(int_, input().split())
    graph[a].append(b)
    parents[b] = a
max_color = max([len(v) for v in graph.values()]) + 1
print(max_color)
used = [set() for _ in range(N)]
ans = []
for i in range(N):
    parent = parents[i]
    for color in range(1, max_color+1):
        if not ans:
            ans.append(0)
            break
        else:
            if color != ans[parent] and color not in used[parent]:
                ans.append(color)
                used[parent].add(color)
                break
for num in ans[1:]:
    print(num)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
graph = defaultdict(list)
def int_(num_str):
    return int(num_str) - 1
parents = [0]*N
parents[0] = N-1
for _ in range(N-1):
    a, b = map(int_, input().split())
    graph[a].append(b)
    parents[b] = a
max_color = max([len(v) for v in graph.values()]) + 1
print(max_color)
used = [set() for _ in range(N)]
ans = []
for i in range(N):
    parent = parents[i]
    for color in range(1, max_color+1):
        if not ans:
            ans.append(color)
            break
        else:
            if color != ans[parent] and color not in used[parent]:
                ans.append(color)
                used[parent].add(color)
                break
for num in ans[1:]:
    print(num)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
graph = defaultdict(list)
def int_(num_str):
    return int(num_str) - 1
parents = [0]*N
parents[0] = N-1
for _ in range(N-1):
    a, b = map(int_, input().split())
    graph[a].append(b)
    parents[b] = a
max_color = max([len(v) for v in graph.values()]) + 1
print(max_color)
used = [set() for _ in range(N)]
ans = []
for i in range(N):
    parent = parents[i]
    for color in range(1, max_color+1):
        if not ans:
            ans.append(color)
            break
        else:
            if color != ans[parent] and color not in used[parent]:
                ans.append(color)
                used[parent].add(color)
                break
for num in ans:
    print(num)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
graph = defaultdict(list)
def int_(num_str):
    return int(num_str) - 1
parents = [0]*N
parents[0] = N-1
for _ in range(N-1):
    a, b = map(int_, input().split())
    graph[a].append(b)
    parents[b] = a
max_color = max([len(v) for v in graph.values()]) + 1
print(max_color)
used = [set() for _ in range(N)]
ans = []
for i in range(N):
    parent = parents[i]
    for color in range(1, max_color+1):
        if not ans:
            ans.append(color)
            break
        else:
            if color != ans[parent] and color not in used[parent]:
                ans.append(color)
                used[parent].add(color)
                break
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for value in AB_dict.values():
    print(value)
# print(AB_dict)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]

print(max_edges)
for value in AB_dict.values():
    print(value)
# print(AB_dict)
# print(Colors)

Submission status: Wrong Answer

Solution code:
from collections import deque

import sys
sys.setrecursionlimit(10**6)

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

#入力を木構造に入力する
root = AB[0][0]
nodes[root][0] = root
for i in range(N-1):
    a,b = AB[i]
    nodes[a][1].append(b)
    nodes[b][0] = a
#print(nodes)

K = 0

for i in range(1,N+1):
    if nodes[i][0] != i:
        K = max(K,len(nodes[i][1])+1)
    else:
        K = max(K,len(nodes[i][1]))

print(K)

Q = deque([root])

while len(Q) != 0:
    q = Q.popleft()
    children = nodes[q][1]
    root_color = nodes[q][2]
    i = 1
    for child in children:
        Q.append(child)
        if i == root_color:
            i += 1
        nodes[child][2] = i
        i += 1

#print(nodes)

for a,b in AB:
    print(nodes[b][2])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

#入力を木構造に入力する
root = AB[0][0]
nodes[root][0] = root
for i in range(N-1):
    a,b = AB[i]
    nodes[a][1].append(b)
    nodes[b][0] = a
#print(nodes)

K = 0

for i in range(1,N+1):
    if nodes[i][0] != i:
        K = max(K,len(nodes[i][1])+1)
    else:
        K = max(K,len(nodes[i][1]))

print(K)

Q = deque([root])

while len(Q) != 0:
    q = Q.popleft()
    children = nodes[q][1]
    root_color = nodes[q][2]
    i = 1
    for child in children:
        Q.append(child)
        if i == root_color:
            i += 1
        nodes[child][2] = i
        i += 1

#print(nodes)

for a,b in AB:
    print(nodes[b][2])