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 collections import deque
inf = float("inf")

n = int(input())
l = [[] for _ in range(n)]

dist = [inf for _ in range(n)]
dist[0] = 1

def bfs():
    que = deque()
    que.append(0)
    while que:
        p = que.popleft()
        color = 1
        for i in l[p]:
            if dist[p]==color:
                color+=1
            if dist[i] == inf:
                dist[i] = color
                que.append(i)
            color+=1

for i in range(n - 1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)
print(max([len(i) for i in l]))
bfs()
[print(i) for i in dist[:-1]]

Submission status: Wrong Answer

Solution code:
from collections import deque
inf = float("inf")

n = int(input())
l = [[] for _ in range(n)]

dist = [inf for _ in range(n)]
dist[0] = 1

def bfs():
    que = deque()
    que.append(0)
    while que:
        p = que.popleft()
        color = 1
        for i in l[p]:
            if dist[p] == 1:
                color = 2
            if dist[i] == inf:
                dist[i] = color
                que.append(i)
            color+=1

for i in range(n - 1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)
print(max([len(i) for i in l]))
bfs()
[print(i) for i in dist[:-1]]

Submission status: Wrong Answer

Solution code:
from collections import deque
inf = float("inf")

n = int(input())
l = [[] for _ in range(n)]

dist = [inf for _ in range(n)]
dist[0] = 1

def bfs():
    que = deque()
    que.append(0)
    while que:
        p = que.popleft()
        color = 1
        for i in l[p]:
            if dist[p] == color:
                color+=1
            if dist[i] != inf:
                continue
            else:
                dist[i] = color
                que.append(i)
            color+=1

for i in range(n - 1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)
print(max([len(i) for i in l]))
bfs()
[print(i) for i in dist[:-1]]

Submission status: Wrong Answer

Solution code:
def enable_color(vertex, color_count, used_color):
    used = used_color[vertex]
    for i in range(1, color_count+1):
        if i not in used:
            return i


from collections import deque
N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
AB.sort()

# 使う色数の判定
vertexs = [0 for _ in range(N)]
for a, b in AB:
    vertexs[a-1] += 1
    vertexs[b-1] += 1
color_count = max(vertexs)
print(color_count)

# 各頂点についてBFS
q = deque()
q.append(1)
before = 0
used_color = {} # 頂点:使用済の色
for i in range(1, N+1):
    used_color[i] = set()

while len(q) != 0:
    root = q.popleft()
    branchs = [b for a, b in AB if a == root]
    for leaf in branchs:
        c = enable_color(root, color_count, used_color)
        print(c)
        used_color[root].add(c)
        used_color[leaf].add(c)
        q.append(leaf)
        # print(q)
        # print(used_color)

Submission status: Wrong Answer

Solution code:
def enable_color(vertex, color_count, used_color):
    used = used_color[vertex]
    for i in range(1, color_count+1):
        if i not in used:
            return i


from collections import deque
N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
AB.sort()

# 使う色数の判定
vertexs = [0 for _ in range(N)]
for a, b in AB:
    vertexs[a-1] += 1
    vertexs[b-1] += 1
color_count = max(vertexs)
print(color_count)

# 各頂点についてBFS
q = deque()
q.append(1)
before = 0
used_color = {} # 頂点:使用済の色
for i in range(1, N+1):
    used_color[i] = []

while len(q) != 0:
    vtx = q.popleft()
    branchs = [b for a, b in AB if a == vtx]
    for b in branchs:
        c = enable_color(vtx, color_count, used_color)
        print(c)
        used_color[vtx].append(c)
        used_color[b].append(c)
        q.append(b)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
# グラフ準備
graph = [[] for _ in range(N + 1)]
seq = []

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

# BFS

q = deque([1])
color = [0] * (N + 1)

while q:
    checking_parent = q.popleft()
    parent_color = color[checking_parent]
    c = 1
    for child in graph[checking_parent]:
        if c == parent_color:
            c += 1
        # 使用したcolorをchildの色として格納する
        color[child] = c
        c += 1
        # childを探索候補へ追加
        q.append(child)

print(max(color))
for i in range(2, N + 1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
n = int(readline())
colors = []
sides = [0] * (n-1)
for j in range(n-1):
    a, b = map(int, readline().split())
    for i in range(len(colors)):
        if a in colors[i] or b in colors[i]:
            continue
        else:
            colors[i].append(a)
            colors[i].append(b)
            sides[j] = i+1
            break
    else:
        colors.append([a, b])
        sides[j] = len(colors)
print(len(colors))
print(*sides, sep='\n')

Submission status: Wrong Answer

Solution code:
N = int(input())
count = [[0] for _ in range(N)]
ans = [1]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tmp = []
    for i in range(len(count[a])):
        tmp.append(count[a][i])
    for i in range(len(count[b])):
        tmp.append(count[b][i])
    tmp = list(set(tmp))
    if len(tmp) == 1:
        count[a].append(1)
        count[b].append(1)
    else:
        f = False
        for i in range(len(tmp)):
            if tmp[i] == i:
                continue
            else:
                count[a].append(i)
                count[b].append(i)
                f = True
                ans.append(i)
                break
        if f == False:
            count[a].append(tmp[-1]+1)
            count[b].append(tmp[-1]+1)
            ans.append(tmp[-1]+1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
# input process
N = int(input())
graph_list = {}
graph_parent_list = {}
visit_list = {}

# initialization
for i in range(N):
    graph_list[i+1] = []
    graph_parent_list[i+1] = {}

for i in range(N-1):
    a, b = map(int, input().split())
    graph_list[a].append(b) # edge state settings
    graph_list[b].append(a)
    graph_parent_list[b][a] = 0 # edge parent settings <- color info

max_ans = 0
# max ans process
for g_key in graph_list:
    max_ans = max(max_ans, len(graph_list[g_key]))

# breadth first search
edge_list = [i for i in range(1, max_ans+1)]
color_list = []
root = 1
search_queue = []
search_queue.append([root,graph_list[root]])
while len(search_queue)>0:
    tmp_edge = [i for i in range(1, max_ans+1)]
    s_in = search_queue.pop() # [1, [2]], [2, [1, 3, 4, 5]]
    s_num = s_in[0] # 1, 2
    s_list = s_in[1] # [2], [1, 3, 4, 5]
    # parent cut process
    if s_num in graph_parent_list:
        for e_key in graph_parent_list[s_num]:
            tmp_edge.remove(graph_parent_list[s_num][e_key])
            s_list.remove(e_key)
    # visited node search
    for i in range(len(s_list)):
        c = tmp_edge[i]
        s = s_list[i]
        color_list.append(c) # color output
        graph_parent_list[s][s_num] = c
        search_queue.append([s, graph_list[s]]) # search queue insert


# output process
print(max_ans)
for c in color_list:
    print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0] = 0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 +((d+1)==visit[s])
                visit[i] = i
                q.append(i)
    print(max([len(i) for i in tree]))
    for a, b in ab:
        print(visit[b-1])

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    ans = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()
            cnt=1

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if ans[x]!=cnt:
                        ans[y]=cnt
                        cnt+=1
                    else:
                        cnt+=1
                        ans[y]=cnt
                        cnt+=1

        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)

x=tree(0)
print(max(x))
for i in range(1,n):
    print(x[i])

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

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

#print(ab)
outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
hoji = []
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        count += 1
        if dicthoji[v1] == count: #前に色を使っていたら飛ばす
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])
        hoji.append(count)
print(dicthoji)

print(max(hoji))
for i in range(N-1):
    print(dicthoji[ab[i][1]])

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

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

#print(ab)
outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
hoji = []
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        count += 1
        if dicthoji[v1] == count: #前に色を使っていたら飛ばす
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])
        hoji.append(count)
#print(dicthoji)

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

Submission status: Wrong Answer

Solution code:
import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
parent = [None] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        for v in edges[u]:
            if colors[u][v] != -1:
                continue

            if parent[u] is not None and cnt == colors[u][parent[u]]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
            parent[v] = u
            cnt += 1
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
# print(parent)
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Wrong Answer

Solution code:
import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        visited[u] = True
        for v in edges[u]:
            if visited[v]:
                continue
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
            cnt += 1
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
set_colors = [set() for _ in range(N)]
max_cnt = 1
visited = [False] * N


def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    cnt = 1
    for v in edges[u]:
        if colors[u][v] != -1:
            continue

        if cnt in set_colors[u]:
            cnt = len(set_colors[u]) + 1

        colors[u][v] = cnt
        colors[v][u] = cnt
        set_colors[u].add(cnt)
        set_colors[v].add(cnt)

        dfs(v)

    global max_cnt
    max_cnt = max(max_cnt, cnt)


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

dfs(0)
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N-1):
    b = list( map(int, input().split() ))
    A.append(b)

ans = [1]
p = 2
for i in range(1,N-1):
    q = 1
    for j in range(i+1):
        if A[i][0] != A[j][0] and A[i][0] != A[j][1]:
            if A[i][1] != A[j][0] and A[i][1] != A[j][1]:
                ans.append(ans[j])
                q = 0
                break
    if q == 1:
        ans.append(p)
        p += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))

for i in ans:
   if i>0:
      print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
G=[[]for _ in range(n)]
V=[False]*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)

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

H=[0]*(n-1)
que=deque([0])
while que:
   s=que.popleft()
   if V[s]==False:
      V[s]=True
      for ni in G[s]:
         print(ni)
      que.append(ni)

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque
def clear_maze(s):

    INF=-10**9
    ans = [INF for i in range(n)]
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            v=1
            x = d.popleft()
            if x == n-1:
                break
            for i in range(len(b[x])):
                y=b[x][i]
                if ans[y] == INF:
                    d.append(y)
                    if ans[x]==v:
                        v+=1
                    ans[y]=v
                    v+=1
        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)


c=clear_maze(0)
print(max(c))
for i in range(n-1):
    print(c[a[i][1]-1])

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque
def clear_maze(s):

    INF=-10**9
    ans = [INF for i in range(n)]
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            v=1
            x = d.popleft()
            if x == n-1:
                break
            for i in range(len(b[x])):
                y=b[x][i]
                if ans[y] == INF:
                    d.append(y)
                    if ans[x]==v:
                        v+=1
                    ans[y]=v
                    v+=1
        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)


c=clear_maze(0)
print(max(c))
for i in range(1,n):
    print(c[i])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [0 for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        K = set()
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            k = len(G[u])
            c = (G_c[u] % k) + 1
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    colors[u, v] = c
                    colors[v, u] = c
                    G_c[u] = c
                    G_c[v] = c
                    K.add(c)
                    c += 1
            G_color[u] = 'BLACK'
        return K
    K = bfs(0)
    print(len(K))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = [0]*(N-1)
V = [0]*N
for i in range(N-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    num = V[a] | V[b]
    for j in range(len(bin(num))):
        if num & (1 << j) == 0:
            ans[i] = j+1
            V[a] += 1 << j
            V[b] += 1 << j
            break

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = [0]*(N-1)
V = [0]*N
for i in range(N-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    num = V[a] | V[b]
    for j in range(2, len(bin(num))+1):
        if num & (1 << j-2) == 0:
            ans[i] = j-1
            V[a] += 1 << j-2
            V[b] += 1 << j-2
            break

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

Submission status: Wrong Answer

Solution code:
from collections import Counter 
n = int(input())

li = [[0]*2 for _ in range(n-1)]
li2c = [0] * (2 * (n - 1))

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    li[i][0] = a
    li[i][1] = b
    li2c[i * 2] = a
    li2c[i * 2 + 1] = b

c = Counter(li2c)

li.sort()

k = c.most_common()[0][1]
print(k)

p = [[0]*k for _ in range(n)] 

for a,b in li:
    for color in range(k):
        if p[a][color] == 0:
            p[a][color] = 1
            p[b][color] = 1
            print(color+1)
            break

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

n = int(input())
edge = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))
colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))

work_q = deque()
work_q.append((1, -1, -1))
color = [-1] * (n - 1)

while work_q:
    here, prev, col = work_q.popleft()
    cnt = 1
    for to, ind in edge[here]:
        if to == prev:
            continue
        if cnt == col:
            cnt += 1
        color[ind] = cnt
        work_q.append((to, here, cnt))
        cnt += 1
print(*color, sep="\n")

Submission status: Wrong Answer

Solution code:
import collections

n=int(input())
edges=[list(map(int,input().split())) for _ in range(n-1)]
g=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=edges[i]
  g[a].append(b)
  g[b].append(a)
k=0
pos=0
for i in range(n+1):
  if len(g[i])>k:
    k=len(g[i])
    pos=i
print(k)
dic={}
q=collections.deque()
q.append((pos,0))
checked=[0]*(n+1)
checked[pos]=1
while 1:
  if len(q)==0:
    break
  u,c=q.popleft()
  for i in range(len(g[u])):
    v=g[u][i]
    if checked[v]==0:
      checked[v]=1
      tc=(c+i)%k+1
      q.append((v,tc))
      dic[(u,v)]=tc
      dic[(v,u)]=tc
for i in range(n-1):
  a,b=edges[i]
  print(dic[(a,b)])

Submission status: Wrong Answer

Solution code:
import collections

n=int(input())
edges=[list(map(int,input().split())) for _ in range(n-1)]
g=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=edges[i]
  g[a].append(b)
  g[b].append(a)
k=0
pos=0
for i in range(n+1):
  if len(g[i])>k:
    k=len(g[i])
    pos=i
print(k)
dic={}
q=collections.deque()
q.append((pos,0))
checked=[0]*(n+1)
checked[pos]=1
while 1:
  if len(q)==0:
    break
  u,c=q.popleft()
  tc=1
  for i in range(len(g[u])):
    v=g[u][i]
    if checked[v]==0:
      checked[v]=1
      if tc+i==c:
        tc+=1
      q.append((v,tc+i))
      dic[(u,v)]=tc+i
      dic[(v,u)]=tc+i
for i in range(n-1):
  a,b=edges[i]
  print(dic[(a,b)])

Submission status: Wrong Answer

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

    ALL_COLORS = set(range(1, N+1))
    OK = {i+1: set(ALL_COLORS) for i in range(N)}
    colors = []
    for e in edges:
        a, b = e
        okset = OK[a] & OK[b]
        c = okset.pop()
        OK[a].remove(c)
        OK[b].remove(c)
        colors.append(c)
    print(len(set(colors)))
    for c in colors:
        print(c)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N + 1)]

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

nodes = deque([1])
count = [0] * (N + 1)

while nodes:
    node = nodes.popleft()
    nodes.extend(edges[node])

    c = 0
    for n in edges[node]:
        c += 1 + (c + 1 == count[node])
        count[n] = c

print(max(count))
for i in range(2, N+1):
    print(count[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
con = [set() for _ in range(N+1)]
res = {}

for ab in AB:
    con[ab[0]].add(ab[1])
    con[ab[1]].add(ab[0])
    res[tuple(ab)] = 0

max_len = 0
for i, c in enumerate(con):
    if max_len <= len(c):
        max_len = len(c)
        max_ind = i

colors = [set() for i in range(N+1)]
all_colors = set([i for i in range(1, max_len+2)])
q = deque()
q.append(max_ind)
node_state = [0]*(N+1)

while q != deque():
    v = q.pop()
    node_state[v] = 1
    for next_v in con[v]:
        if node_state[next_v] == 0:
            q.appendleft(next_v)
        if v < next_v:
            va = v
            vb = next_v
        else:
            va = next_v
            vb = v
        if res[(va, vb)] == 0:
            color = list(all_colors.difference(colors[va].union(colors[vb])))[0]
            res[(va, vb)] = color
            colors[va].add(color)
            colors[vb].add(color)

print(max_len)
for i in range(N-1):
    print(res[tuple(AB[i])])

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  from collections import deque
  input=sys.stdin.readline
  n=int(input())
  
  edges=deque()
  for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges.append([a,b])
  
  color=[0]*(n-1)
  head=[0]*n #上から来る色
  before=[0]*n #直前に使った色
  for i in range(n-1):
    edge=edges.popleft()
    a,b=edge[0],edge[1]
    if before[a]+1==head[a]:
      c=before[a]+2
    else:
      c=before[a]+1
    before[a]=c
    head[b]=c
    color[i]=c
  print(max(color))
  print(*color,sep='\n')
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  from collections import deque
  input=sys.stdin.readline
  n=int(input())
  
  edges=deque()
  for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges.append([a,b])
  
  color=[0]*(n-1)
  tree=[[] for _ in range(n)]
  for i in range(n-1):
    edge=edges.popleft()
    a,b=edge[0],edge[1]
    j=1
    while j in tree[a]:
      j+=1
    tree[a].append(j)
    tree[b].append(j)
    color[i]=j
  print(max(color))
  print(*color,sep='\n')
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

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

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
  
def make_tree(graph, root) -> (list, list, list):
    INF = 10 ** 15
    dist = [INF] * len(graph)
    parent = [-1] * len(graph)
    stack = [root]
    dist[root] = 0
    order = []
    parent[root] = root
    while stack:
        s = stack.pop()
        order.append(s)
        for g in graph[s]:
            if dist[g] > dist[s] + 1:
                dist[g] = dist[s] + 1
                parent[g] = s
                stack.append(g)
    return dist, parent, order
    
dist, parent, order = make_tree(graph, 1)

color = [-1] * (N + 1)
for s in order:
    ng = color[s]
    c = 1
    for g in graph[s]:
        if parent[s] == g:
            continue
        if c == ng:
            c += 1
        color[g] = c
        c += 1
print(color)

answer = []
for a, b in AB:
    if parent[a] == b:
        answer.append(color[a])
    else:
        answer.append(color[b])

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

Submission status: Wrong Answer

Solution code:
n=int(input())
edge={i:[] for i in range(n+1)}
colored={j:{} for j in range(n+1)}
before_colored=[0 for i in range(n+1)]
querie=[]
start=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    querie.append((a,b))
    if i==0:
        start=[a,b]
    

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

visited[start[0]]=True
d=[]
e=[]
p=1
for node in edge[start[0]]:
    visited[node]=True
    colored[start[0]][node]=p
    colored[node][start[0]]=p
    before_colored[node]=start[0]
    d.append(node)
    p+=1


while d:
    for some in d:
        color=1
        for node in edge[some]:
            if not visited[node]:
                visited[node]=True
                if before_colored[some]!=color:
                    before_colored[node]=color
                    e.append(node)
                    colored[some][node]=color
                    colored[node][some]=color
                    color+=1
                else:
                    color+=1
                    before_colored[node]=color
                    e.append(node)
                    colored[some][node]=color
                    colored[node][some]=color
                    color+=1
                    
                
    if e:
        d=e.copy()
        e=[]
    else:
        d=[]
K=0
for i in range(1,n+1):
  K=max(K,len(edge[i]))
print(K)
for i in range(n-1):
  print(colored[querie[i][0]][querie[i][1]])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
connection = [[0]*(N+1) for _ in range(N+1)]

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

for i in range(N-1):
    connection[ab[i][0]][ab[i][1]] = -1
    connection[ab[i][1]][ab[i][0]] = -1

max_edge_num = 0
for i, con_i in enumerate(connection):
    if max_edge_num > sum(con_i):
        max_edge_num = sum(con_i)
        max_edge_ind = i

max_edge_num = - max_edge_num

q = deque()
q.append(max_edge_ind)
while q != deque():
    colors = [i for i in range(0, max_edge_num+1)]
    V = q.pop()
    for i, V_v in enumerate(connection[V]):

        if V_v != 0:
            if V_v == -1:
                q.append(i)
                for c in colors:
                    if c != 0:
                        connection[V][i] = connection[i][V] = c
                        colors[c] = 0
                        break
            else:
                colors[V_v] = 0

print(max_edge_num)
for i in range(N-1):
    print(connection[ab[i][0]][ab[i][1]])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
connection = [[0]*(N+1) for _ in range(N+1)]

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

for i in range(N-1):
    connection[ab[i][0]][ab[i][1]] = -1
    connection[ab[i][1]][ab[i][0]] = -1

max_edge_num = 0
for i, con_i in enumerate(connection):
    if max_edge_num > sum(con_i):
        max_edge_num = sum(con_i)
        max_edge_ind = i

max_edge_num = - max_edge_num

q = deque()
q.append(max_edge_ind)
while q != deque():
    colors = [i for i in range(0, max_edge_num+1)]
    V = q.pop()
    for i, V_v in enumerate(connection[V]):

        if V_v != 0:
            if V_v == -1:
                q.append(i)
                for c in colors:
                    if c != 0:
                        connection[V][i] = connection[i][V] = c
                        colors[c] = 0
                        break
            else:
                colors[V_v] = 0

print(max_edge_num)
for i in range(N-1):
    print(connection[ab[i][0]][ab[i][1]])

Submission status: Wrong Answer

Solution code:
N=int(input())
R=[[] for i in range(N)]
a=[]
b=[]
L=[]

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

for i in range(N-1):
    L.append([len(R[i]),i])

L.sort(reverse=True)

K=L[0][0]

for i in range(N-1):
    if L[i][0]!=K:break
    if L[i][1] in b:
        K+=1
        break

print(K)

C=[[] for i in range(K)]
for i in range(N-1):
    for k in range(K):
        if (a[i] in C[k]) or (b[i] in C[k]):continue
        else:
            print(k+1)
            C[k].append(a[i])
            C[k].append(b[i])
            break

Submission status: Wrong Answer

Solution code:
N=int(input())
R=[[] for i in range(N)]
a=[]
b=[]
L=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    R[a[i]].append(b[i])
    L.append(len(R[a[i]]))

K=max(L)

if len(set(a))!=1:K+=1
print(K)

C=[[] for i in range(K)]
for i in range(N-1):
    for k in range(K):
        if (a[i] in C[k]) or (b[i] in C[k]):continue
        else:
            print(k+1)
            C[k].append(a[i])
            C[k].append(b[i])
            break