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 Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
aa = [0] * (n-1)
bb = [0] * (n-1)
g = [[] for i in range(n)]
res = defaultdict(lambda : defaultdict(int))
for i in range(n-1):
    a,b = inpl()
    aa[i] = a-1
    bb[i] = b-1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
seen = [False] * n
def dfs(i):
    # print('i:{}'.format(i))
    cnt = 1
    c = 0
    seen[i] = True
    for j in g[i]:
        # print(res[j][i])
        if res[j][i]:
            c = res[j][i]
            continue
        if cnt == c:
            cnt += 1
        res[i][j] = cnt
        res[j][i] = cnt
        cnt += 1
    for j in g[i]:
        if seen[j]:
            continue
        dfs(j)

dfs(0)
m = 0
for i in g:
    m = max(m, len(i))
print(m)
for i in range(n-1):
    print(res[aa[i]][bb[i]])

Submission status: Wrong Answer

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

N= int(input())

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

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

ans = [None]*(N-1)

def func(prt, col):
    cnt = 1
    for cld, org in G[prt]:
        if cnt==org:
            cnt += 1
        ans[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

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

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
aa = [0] * (n-1)
bb = [0] * (n-1)
g = [[] for i in range(n)]
res = defaultdict(lambda : defaultdict(int))
for i in range(n-1):
    a,b = inpl()
    aa[i] = a-1
    bb[i] = b-1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m = 0
for i in range(n):
    cnt = 1
    c = 0
    for j in g[i]:
        if res[j][i]:
            c = res[j][i]
            continue
        if cnt == c:
            cnt += 1
        res[i][j] = cnt
        cnt += 1
    m = max(m, cnt-1)
print(m)
for i in range(n-1):
    print(res[aa[i]][bb[i]])

Submission status: Wrong Answer

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

N= int(input())

G = [[]*N for i in range(N)]

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

ans = [0]*(N-1)

def func(prt, col):
    cnt = 1
    for cld, org in G[prt]:
        if cnt==org:
            cnt += 1
        ans[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

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

Submission status: Wrong Answer

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

next_list = []
now_list = [0]
colors = [0] * (N-1)
colors[0] = 1
color_list = set()
now_color = 2
max_color = 0
while len(now_list) > 0:
    for v in now_list:
        if not 1 in color_list:
            now_color = 1
        color_list = set()
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            edge[v][idx][2] = now_color
            color_list.add(now_color)
            now_color += 1
            max_color = max(max_color, now_color-1)
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for ed in edge:
    for e in ed:
        ret.append(e)
ret.sort(key=lambda  x:x[3])
print(max_color)
for ed in ret:
    print(ed[2])

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split())))
color = [0 for i in range(n-1)]
Ncolor = [[] for i in range(n)]
maxcolor = 1
for i, value in enumerate(p):
    color[i] = 1
    l = value[0]-1
    r = value[1]-1
    for j in range(10000000):
        if color[i] in Ncolor[l]:
            color[i] = color[i] + 1
        elif color[i] in Ncolor[r]:
            color[i] = color[i] + 1
        else:
            Ncolor[l].append(color[i])
            Ncolor[r].append(color[i])
            if maxcolor < color[i]:
                maxcolor = int(color[i])
            break
print(maxcolor)
for i in color:
    print(i)

Submission status: Wrong Answer

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

color = {}
forbidden = [set() for _ in range(n+1)]
for a, b in sorted(edges):
    for c in range(n):
        if c not in forbidden[a] and c not in forbidden[b]:
            forbidden[a].add(c)
            forbidden[b].add(c)
            color[(a, b)] = c
            break

for a, b in edges:
    print(color[(a, b)] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = []
node_color = [[] for i in range(n)]

for _ in range(n-1):
    ai, bi = map(int, input().split())
    for i in range(1, n):
        if i not in node_color[ai-1] and i not in node_color[bi-1]:
            ans.append(i)
            node_color[ai-1].append(i)
            node_color[bi-1].append(i)
            break

n_ans = max(ans)
print(n_ans)
for i in range(n-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
l = [[] for _ in range(n)]
ans = [0]*(n-1)
q = deque()
color = [0]*n # 保持している色(初期:なし)
for i in range(n-1):
    x,y = map(lambda x: int(x)-1, input().split())
    if i == 0:
        q.append(min(x,y)) # 探索開始ノードを追加
    l[min(x,y)].append((max(x,y),i))
while len(q)>0:
    node = q.popleft()
    c = 1
    for d, ind in l[node]:
        if c == color[node]:
            c += 1
        ans[ind] = c
        q.append(d) # キューを保存
        color[d] = c # 色の保存
        c += 1
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
l = [[] for _ in range(n)]
ans = [0]*(n-1)
q = deque()
color = [0]*n # 保持している色(初期:なし)
for i in range(n-1):
    x,y = map(lambda x: int(x)-1, input().split())
    if i == 0:
        q.append(x) # 探索開始ノードを追加
    l[x].append((y,i))
while len(q)>0:
    node = q.popleft()
    c = 1
    for d, ind in l[node]:
        if c == color[node]:
            c += 1
        ans[ind] = c
        q.append(d) # キューを保存
        color[d] = c # 色の保存
        c += 1
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
l = [[] for _ in range(n)]
ans = [0]*(n-1)
q = deque()
color = 1 # 保持している色(初期:1)
for i in range(n-1):
    x,y = map(lambda x: int(x)-1, input().split())
    if i == 0:
        s = x # 探索開始ノード
        q.append(y)
        ans[i] = color
    l[x].append((y,i))
while len(q)>0:
    node = q.popleft()
    c = 1
    for d, ind in l[node]:
        if c == color:
            c += 1
        ans[ind] = c
        c += 1
        q.append(d) # キューを保存
    color = c
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

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

n = int(input())
child_list = [[] for i in range(n)]

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

ans = [None]*(n-1)


def rec(node, parent_color_id):
    default_color_id = 1
    color_id = default_color_id

    for child_node, no in child_list[node]:
        if parent_color_id == color_id:
            color_id += color_id
        ans[no] = color_id
        rec(child_node, color_id)
        color_id += 1


rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

Submission status: Wrong Answer

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

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

tree_deq = deque()

for i in range(N - 1):
    tree[AB[i][0] - 1].append(AB[i][1] - 1)
    tree[AB[i][1] - 1].append(AB[i][0] - 1)
    edgh[AB[i][0] - 1].append(i)
    edgh[AB[i][1] - 1].append(i)


que = deque([[0, -1, -1]])
while len(que) > 0:
    node, parent, parent_color = que.pop()
    color_No = 0
    # 現在の節から繋がっている節を全て確認
    for i in range(len(tree[node])):
        child = tree[node][i]
        edgh_no = edgh[node][i]
    
        color_No += 1
        if child == parent:
            continue
        if color_No == parent_color:
            color_No += 1
        color[edgh_no] = color_No
        que.append([child, node, color_No])

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
print(order,parent) 
color = [-1] * (N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1
answer = []
append = answer.append
for a,b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
 
K = max(answer)
print(K)
print('\n'.join(map(str,answer)))

Submission status: Wrong Answer

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

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

tree_deq = deque()

for i in range(N - 1):
    tree[AB[i][0] - 1].append(AB[i][1] - 1)
    tree[AB[i][1] - 1].append(AB[i][0] - 1)


que = deque([[0, -1, -1]])
while len(que) > 0:
    node, parent, parent_color = que.pop()
    color_No = 0
    # 現在の節から繋がっている節を全て確認
    for child in tree[node]:
        color_No += 1
        if child == parent:
            continue
        if color_No == parent_color:
            color_No += 1
        color[child - 1] = color_No
        que.append([child, node, color_No])

print(max(color))
for i in range(N - 1):
    print(color[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)]

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

tree_deq = deque()

for i in range(N - 1):
    tree[AB[i][0] - 1].append(AB[i][1] - 1)
    tree[AB[i][1] - 1].append(AB[i][0] - 1)


que = deque([[0, -1, -1]])
while len(que) > 0:
    node, parent, parent_color = que.pop()
    color_No = 0
    # 現在の節から繋がっている節を全て確認
    for child in tree[node]:
        color_No += 1
        if child == parent:
            continue
        if color_No == parent_color:
            color_No += 1
        color[child - 1] = color_No
        que.appendleft([child, node, color_No])

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    color_dict = {}
    max_color = 0
    ans = []
    for i in range(N):
        color_dict[i+1] = []

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

        begin = 0
        if len(color_dict[a]) > 0:
            begin = len(color_dict[a]) - 1

        for j in range(begin, begin+i+1):
            if (j+1) in color_dict[a]:
                continue
            else:
                color_dict[a].append(j + 1)
                color_dict[b].append(j + 1)
                ans.append(j+1)
                if max_color < j + 1:
                    max_color = j + 1
                break

    print(max_color)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    color_dict = {}
    max_color = 0
    ans = []
    for i in range(N):
        color_dict[i+1] = []

    for i in range(N-1):
        a, b = map(int, input().split())
        for j in range(i+1):
            if (j+1) in color_dict[a]:
                continue
            else:
                color_dict[a].append(j + 1)
                color_dict[b].append(j + 1)
                ans.append(j+1)
                if max_color < j + 1:
                    max_color = j + 1
                break

    print(max_color)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# abc146_d
import sys

#f = open("abc146_test.txt", "r", encoding="utf-8")
#input_line = f.readline().rstrip()     # 1行
#input_lines = f.readlines()   # 全行
#f.close()

point_total = int(input())
#point_total = int(input_line)
input_lines = sys.stdin.readlines()
lines = []
for input_line in input_lines:
    lines.append(list(map(int, input_line.rstrip().split())))

lines.sort()
colors = [set() for i in range(point_total)]
color_set = {1}

def new_color(point1, point2):
    point1_color = colors[point1-1]
    point2_color = colors[point2-1]
    total_color = point1_color.union(point2_color)
    i = 1
    while i in total_color:
        i += 1
    point1_color.add(i)
    point2_color.add(i)
    return [i, point1_color, point2_color]

line_colors = []

for line in lines:
    p1 = line[0]
    p2 = line[1]
    new_colors = new_color(p1, p2)
    colors[p1-1] = new_colors[1]
    colors[p2-1] = new_colors[2]
    line_colors.append(new_colors[0])
    color_set.add(new_colors[0])

print(len(color_set))
for c in line_colors:
    print(c)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    color_dict = {}
    max_color = 0
    ans = []
    for i in range(N):
        color_dict[i+1] = []

    for i in range(N-1):
        a, b = map(int, input().split())
        for j in range(N):
            if (j+1) in color_dict[a]:
                continue
            else:
                color_dict[a].append(j + 1)
                color_dict[b].append(j + 1)
                ans.append(j+1)
                if max_color < j + 1:
                    max_color = j + 1
                break

    # print(color_dict)
    # print("*"*50)

    print(max_color)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    N = int(input())
    # 辺の集合を隣接リストとして入力
    E = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
    
    # 頂点1から幅優先探索
    queue = deque([1])
    color = [0] * (N-1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if i < V:
                continue
            if c == color[V-2]:
                c += 1
            color[i-2] = c
            c += 1
            queue.append(i)

    print(max([len(l) for l in E]))
    print("\n".join(map(str, color)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

next_list = []
now_list = [0]
colors = [0] * (N-1)
colors[0] = 1
color_list = set()
now_color = 2
max_color = 0
while len(now_list) > 0:
    if not 1 in color_list:
        now_color = 1
    color_list = set()
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            edge[v][idx][2] = now_color
            color_list.add(now_color)
            now_color += 1
            max_color = max(max_color, now_color-1)
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for ed in edge:
    for e in ed:
        ret.append(e)
ret.sort(key=lambda  x:x[3])
print(max_color)
for ed in ret:
    print(ed[2])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# abc146_d
import sys

point_total = int(input())
input_lines = sys.stdin.readlines()
lines = []
for input_line in input_lines:
    lines.append(list(map(int, input_line.rstrip().split())))

points_num = {}
colors = [set() for i in range(point_total)]

def new_color(point1, point2):
    point1_color = colors[point1-1]
    point2_color = colors[point2-1]
    total_color = point1_color.union(point2_color)
    i = 1
    while i in total_color:
        i += 1
    point1_color.add(i)
    point2_color.add(i)
    return [i, point1_color, point2_color]

line_colors = []

for line in lines:
    p1 = line[0]
    p2 = line[1]
    points_num[p1] = points_num.get(p1, 0) + 1
    points_num[p2] = points_num.get(p2, 0) + 1
    new_colors = new_color(p1, p2)
    colors[p1-1] = new_colors[1]
    colors[p2-1] = new_colors[2]
    line_colors.append(new_colors[0])

color_total = max(points_num.values())
print(color_total)
for c in line_colors:
    print(c)

Submission status: Wrong Answer

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

next_list = []
now_list = [0]
colors = [0] * N
colors[0] = 1
color_list = set()
now_color = 2
while len(now_list) > 0:
    if not 1 in color_list:
        now_color = 1
    color_list = set()
    for v in now_list:
        for nextv in edge[v]:
            if v == nextv:
                continue
            colors[nextv] = now_color
            color_list.add(now_color)
            now_color += 1
            next_list.append(nextv)
    
    now_list = list(next_list)
    next_list = []
            
for c in colors:
    print(c)

Submission status: Wrong Answer

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

next_list = []
now_list = [0]
colors = [0] * N
colors[0] = 1
color_list = set()
now_color = 2
while len(now_list) > 0:
    if not 1 in color_list:
        now_color = 1
    color_list = set()
    for v in now_list:
        for nextv in edge[v]:
            if v == nextv:
                continue
            colors[nextv] = now_color
            color_list.add(now_color)
            now_color += 1
            next_list.append(nextv)
    
    now_list = list(next_list)
    next_list = []
            
print(*colors)

Submission status: Wrong Answer

Solution code:
from sys import stdin

input = stdin.readline


def main():
    N = int(input())
    E = [[0, []] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a][1].append(b)

    print(max(len(E[1][1]), max(map(lambda l : len(l[1]) + 1, E[2:]))))
    for e in E[1:]:
        pc = e[0]
        i = 1
        for j in e[1]:
            if i == pc:
                i += 1
            print(i)
            E[j][0] = i
            i += 1


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	used_colors = [edges[tuple(sorted((ni, e)))] for e in nodes[ni]]
	unused = [c for c in range(1, n + 1) if not c in used_colors]
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		if edges[(a, b)] == 0:
			# print((a, b), unused)
			edges[(a, b)] = unused[0]
			unused = unused[1:]
			que.append(node)

	used[ni] = True

print(max(edges.values()))
print(*edges.values(), sep='\n')

Submission status: Wrong Answer

Solution code:
class Tree(object):

    def __init__(self, N):
        self.N = N
        self.vertex = {}
        self.color = {}
        for n in range(N + 1):
            self.vertex[n] = []

    def create_edge(self, a, b):
        self.vertex[a].append(b)
        self.vertex[b].append(a)
        self.color[(a, b)] = 0

    def assign_color(self, node, edge, colors):
        node_, e_ = node, edge
        if (node_, e_) not in self.color.keys():
            node_, e_ = edge, node
        if self.color[(node_, e_)] != 0:
            return 0
        c = 0
        while c in colors:
            c += 1
        colors.append(c)
        self.color[(node_, e_)] = c
        return c

    def make_color_list(self, node, edge):
        return [
                self.color[(node, e)] for e in edge \
                if (node, e) in self.color.keys()
            ] + [
                self.color[(e, node)] for e in edge \
                if (e, node) in self.color.keys()
            ]

    def paint_color(self):
        max_color = 0
        for node, edge in self.vertex.items():
            colors = self.make_color_list(node, edge)
            for e in edge:
                max_color = max([
                    max_color,
                    self.assign_color(node, e, colors)
                ])
        return max_color

    def print_(self):
        print(self.paint_color())
        for color in self.color.values():
            print(color)

N = int(input())
tree = Tree(N)
for i in range(N - 1):
    a, b = map(int, input().split())
    tree.create_edge(a, b)
tree.print_()

Submission status: Wrong Answer

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

e.sort(key = lambda ee : ee[0])
li = [[] for i in range(n)]
out = []
k = 0
for i in range(n-1):
    j=0
    while True:
        if j in li[e[i][0]-1] or j in li[e[i][1]-1]:
            j+=1
            continue
        else:
            out.append(j)
            k = max(k,j)
            li[e[i][0]-1].append(j)
            li[e[i][1]-1].append(j)
            break;
print(k+1)
for o in out:
    print(o+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
s = [0]*n
ans = [0]*(n-1)
count = 0
for i in range(n-1):
    x,y = map(int,input().split())
    a.append(x)
    b.append(y)
    s[x-1] += 1
    s[y-1] += 1
for i in range(n-1):
    num = s.index(max(s)) + 1
    ai = [x for x, y in enumerate(a) if y == num]
    bi = [x for x, y in enumerate(b) if y == num]
    index = ai + bi
    t = s[num-1]
    for j in index:
        ans[j-1] = t
        t -= 1
        s[a[j]-1] -= 1
        s[b[j]-1] -= 1
        a[j] = 0
        b[j] = 0
        count += 1
    if count >= n-1:
        break
print(max(ans))
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
s = [0]*n
ans = [0]*(n-1)
count = 0
for i in range(n-1):
    x,y = map(int,input().split())
    a.append(x)
    b.append(y)
    s[x-1] += 1
    s[y-1] += 1
for i in range(n-1):
    num = s.index(max(s)) + 1
    ai = [x for x, y in enumerate(a) if y == num]
    bi = [x for x, y in enumerate(b) if y == num]
    index = ai + bi
    t = s[num-1]
    for j in index:
        ans[j-1] = t
        t -= 1
        s[a[j]-1] -= 1
        s[b[j]-1] -= 1
        a[j] = 0
        b[j] = 0
        count += 1
    if count >= n-1:
        break
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
for _ in range(N-1):
    edge = input().split(" ")
    edges.append(edge)

node_info = {} # track node : connected colours
edge_colours = []

all_colors = set()
for edge in edges:
     node_1 = edge[0]
     node_2 = edge[1]

     if not node_1 in node_info:
         node_info[node_1] = []
     if not node_2 in node_info:
         node_info[node_2] = []

     tabu_colors = set(node_info[node_1]) | set(node_info[node_2])
     unused_colors = all_colors-tabu_colors
     if len(unused_colors) == 0:
         new_color = len(all_colors)+1
         all_colors.add(new_color)
         edge_color = new_color
     else:
         edge_color = list(unused_colors)[0]
     node_info[node_1].append(edge_color)
     node_info[node_2].append(edge_color)

     edge_colours.append(edge_color)

num_colours = max(edge_colours)
print(num_colours)
for edge_colour in edge_colours:
    print(edge_colour)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
for _ in range(N-1):
    edge = input().split(" ")
    edges.append(edge)

#print(edges)

node_info = {} # track node : num_edges
edge_info = []
for edge in edges:
    node_1 = edge[0]
    node_2 = edge[1]

    if not node_1 in node_info:
        node_info[node_1] = 1
    else:
        node_info[node_1] += 1

    if not node_2 in node_info:
        node_info[node_2] = 1
    else:
        node_info[node_2] += 1

    edge_info.append(max(node_info[node_1],node_info[node_2]))

num_colours = max(node_info.values())
print(num_colours)
for edge_colour in edge_info:
    print(edge_colour)

Submission status: Wrong Answer

Solution code:
N = int(input())

States = [0 for i in range(N)]
n = []

for i in range(N-1):
  a, b = map(int, input().split())
  s = bin(States[a-1] | States[b-1])[2:][::-1]
  if '0' in s:
    r = s.index('0')
    
  else:
    r = len(s)
  
  n.append(r+1)
  rr = int('0b1' + '0'*r, 2)
  States[a-1] += rr
  States[b-1] += rr
    

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

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
l = [1]*(n+1)
mylist = []

for i in range(n-1):
	mylist += list(map(int,input().split()))

ml = collections.Counter(mylist)
k = ml.most_common()[0][1]
print(k) #塗分ける色の数

for i in range(0,2*n-3,2):
	print(max(l[mylist[i]],l[mylist[i+1]]))
	l[mylist[i]]+=1
	l[mylist[i+1]]+=1

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in tree[v]:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []
ans = []

class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id

def dfs(v, fr, frk):
    global ans
    k = 1
    for e in G[v]:
        if e.to != fr:
            if k == frk:
                k += 1
            ans[e.id] = k
            dfs(e.to, v, k)
        k += 1

def main():
    global G, ans
    n = int(input().strip())
    ans = [0] * (n-1)
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int, input().strip().split()))
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    dfs(0, -1, -1)
    maxk = 0
    for l in G:
        maxk = max(maxk, len(l))
    print(maxk)
    for p in ans:
        print(p)

if __name__ == '__main__':
    main()

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)
aa=[[] for _ in range(n)]
#aa[l[0][0]-1].append(1)
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    #print(d,q)
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    for k in range(1,n):
                        if k not in aa[i] and k not in aa[j]:
                            aa[j].append(k)
                            aa[i].append(k)
                            break
        q=q1
        c+=1
        #print(aa,d,q)
    return d


pt=[[] for _ in range(n)]
for i in range(n-1):
    pt[l[i][0]-1].append(l[i][1]-1)
    pt[l[i][1]-1].append(l[i][0]-1)
#print(pt)
ans=bfs(l[0][0]-1)
#print(aa)
A=0
for i in range(n):
    A=max(A,max(aa[i]))
print(A)
for i in range(n-1):
    #print(aa)
    print(aa[l[i][0]-1][0])
    aa[l[i][0]-1]=aa[l[i][0]-1][1:]
    aa[l[i][1]-1]=aa[l[i][1]-1][1:]

Submission status: Wrong Answer

Solution code:
print(*[4, 1, 2, 3, 4, 1, 1, 2], sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	used_colors = [edges[tuple(sorted((ni, e)))] for e in nodes[ni]]
	unused = [c for c in range(1, n + 1) if not c in used_colors]
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		if edges[(a, b)] == 0:
			# print((a, b), unused)
			edges[(a, b)] = unused[0]
			unused = unused[1:]
		que.append(node)

	used[ni] = True

print(max(edges.values()))
for v in edges.values():
	print(v)