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:
# input
n = int(input())

edge = [[0, 0, 0] for i in range(n-1)]
for i in range(n-1):
    edge[i][0] ,edge[i][1] = map(int, list(input().split()))

# process
def findcolor(p):
    if p == 1: 
        return 0
    else: 
        for e in edge:
            if e[1] == p:
                return e[2]

j = 0
k = 0
for i in range(n):
    i += 1
    color = 0

    while j < n-1:
        if edge[j][0] == i:
            color += 1
            if color == findcolor(i): color += 1

            edge[j][2] = color
            if k < color: k = color

            j += 1
        else:
            break

# output
print(k)
for e in edge:
    print(e[2])

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())

    color = [0] * n
    list_a = [0] * (n-1)
    list_b = [0] * (n-1)
    for i in range(n-1):
        a,b = map(int,input().split())
        list_a[i] = a
        list_b[i] = b
        color[a-1] += 1
        color[b-1] += 1
    print(max(color))

    cnt = [1] * n
    for i in range(n-1):
        if cnt[list_a[i]-1] > cnt[list_b[i]-1]:
            print(cnt[list_a[i]-1])
            cnt[list_a[i]-1] +=  1

        elif cnt[list_a[i]-1] == cnt[list_b[i]-1]:
            print(cnt[list_a[i]-1])
            cnt[list_a[i]-1] += 1
            cnt[list_b[i]-1] += 1
        else:
            print(cnt[list_b[i]-1])
            cnt[list_b[i]-1] += 1




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
A = [0] * (N-1)
B = [0] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    A[i] = a
    B[i] = b
K = 0
for i in range(N):
    K = max(len(graph[i]), K)

ans = [[0] * N for _ in range(N)]

# BFSのためのデータ構造
dist = [False for _ in range(N)]
que = deque()

# 初期条件
dist[0] = True
que.append(0)
color_num = [[] for _ in range(N)]

# BFS開始
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if dist[new_v]:   # すでに探索済みの頂点は探索しない
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        for k in range(1, K+1):
            if k in color_num[v]:
                continue
            if k in color_num[new_v]:
                continue
            else:
                ans[v][new_v] = k
                ans[new_v][v] = k
                color_num[v].append(k)
                color_num[new_v].append(k)
                break
        
print(ans)
# 答えの出力
print(K)
for i in range(N-1):
    print(ans[A[i]][B[i]])

Submission status: Wrong Answer

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque
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)

q = deque([0])
color=[0]*n
# color[-1]=9
while q:
    v=q.popleft()
    c=0
    for nv in G[v]:
        c+=1+(c+1==color[v])
        color[nv]=c
        q.append(nv)
del color[0]
print(max(color))
print(*color,sep='\n')

Submission status: Wrong Answer

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque
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)

q = deque([0])
color=[0]*(n-1)

while q:
    v=q.popleft()
    c=0
    for nv in G[v]:
        c+=1+(c+1==color[v-1])
        color[nv-1]=c
        q.append(nv)
print(max(color))
print(*color,sep='\n')

Submission status: Wrong Answer

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque
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)

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

i=0
while q:
    v=q.popleft()
    c=0
    for nv in G[v]:
        if v==0:
            c+=1
        else:
            c+=1+(c+1==color[v-1])
        color[nv-1]=c
        q.append(nv)
print(max(color))
print(*color,sep='\n')

Submission status: Wrong Answer

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque
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)

q = deque([0])
color=[0]*(n-1)

i=0
while q:
    v=q.popleft()
    c=0
    for nv in G[v]:
        if v==0:
            c+=1
        else:
            c+=1+(c+1==color[v-1])
        color[nv-1]=c
        q.append(nv)
print(max(color))
print(*color,sep='\n')

Submission status: Wrong Answer

Solution code:
# ABC146 D - Coloring Edges on Tree
from collections import deque
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)

q = deque([0])
color=[0]*(n-1)

i=0
while q:
    v=q.popleft()
    c=0
    for nv in G[v]:
        c+=1+(c+1==color[v-1])
        color[nv-1]=c
        q.append(nv)
print(max(color))
print(*color,sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
G = [[] for _ in range(N)]
color = [[-1]*N for _ in range(N)]
E = []
for i in range(N-1):
	a, b = map(int, input().split())
	G[a-1].append(b-1)
	E.append((a, b))
	
used = [set() for _ in range(N)]

for a,eadges in enumerate(G):
	c = 1
	for b in eadges:
		while c in used[b] or c in used[a]:
			c+=1
		color[a][b] = c
		used[a].add(c)
		used[b].add(c)

for e in E:
	a,b = map(int, e)
	print(color[a-1][b-1])

Submission status: Wrong Answer

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

graph = [[] for i in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
#print(graph)

root = 1
stack = [root]
order = []
parent = [0] * (N + 1)

while stack:
  s = stack.pop()
  order.append(s)
  for g in graph[s]:
    if g == parent[s]:
      continue
    else:
      parent[g] = s
      stack.append(g)
#print("order:", order)

color = [-1] * (N+1)
for i in range(1, N):
  ng = parent[i]
  c = 1
  for g in graph[i]:
    if g == parent[i]:
      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(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		#print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]:
			if col == c: col += 1
		for c in used[nv]:
			if col == c: col += 1

		used[v].append(col)
		used[nv].append(col)
		ans[tuple(sorted([v, nv]))] = col
		queue.append(nv)

#print(used)

ans = [ans[(m[0]-1, m[1]-1)] for m in M]
print(max(ans))
for a in ans:
	print(a)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	# G[b].append(a)

# print(G)

dist = [[-1, i, -1] for i in range(N)]
queue = deque()

dist[0] = [-1, 0, 0]
queue.append(0)

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		# print(v, nv, G[v])
		
		if dist[nv][2] != -1: continue
		
		dist[nv][0] = v
		dist[nv][2] = dist[v][2]+1
		queue.append(nv)

dist[0].append(1)
COLOR = [1]
colors = [-1] * N
colors[0] = -1
# print(colors)
# print(dist)

for i,d in enumerate(dist):
	if i==0: continue
	par = d[0]
	me = d[1]
	dis = d[2]
	bro = []
	for di in dist:
		if di[0] == par and di[2] == dis and di[1] != me:
			bro.append(di)
	col = []
	col.append(colors[par])
	gp = dist[par][0]
	col.append(colors[gp])
	for b in bro:
		idx = b[1]
		if colors[idx] != -1:col.append(colors[idx])
	# print("me:{}, bro:{}, col:{}".format(me, bro, col))
	# print("COLORS:", COLOR)
	for C in COLOR:
		if not C in col:
			colors[i] = C
			break
	else:
		COLOR.append(max(COLOR)+1)
		colors[i] = COLOR[-1]
	# print("my color:", colors[i])

# print(colors)

colors.pop(0)
print(len(set(colors)))
for c in colors:
	print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
for i in path_num_to_edges[0]:
    d.append(i)
while d:
    temp_edge=d.pop()
    new_path_color=1
    if temp_edge in tree_edge_flag:
        continue
    tree_edge_flag.add(temp_edge)
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]==new_path_color:
            new_path_color+=1
        if path_color[path_num]!=None:
            continue
        path_color[path_num]=new_path_color
        new_path_color+=1
        d.append(other_edge)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
d.append(0)
while d:
    temp=d.pop()
    temp_color=path_color[temp]
    edges=path_num_to_edges[temp]
    new_path_color=1
    for edge in edges:
        for other_edge,path_num in tree_path[edge]:
            if path_color[path_num]!=None:
                continue
            if new_path_color==temp_color:
                new_path_color+=1
            path_color[path_num]=new_path_color
            new_path_color+=1
            d.append(path_num)


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

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    # i != j => (ai, bi) != (aj, bj)
    next_ = [dict([]) for _ in range(n + 1)]
    color = [set([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        use = set(range(1, len(_next) + 1)) - color[c]
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            print(_n, u)
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            color[c].add(u)
            color[_n].add(u)
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Wrong Answer

Solution code:
N = int(input())

from collections import defaultdict
from collections import deque

g = defaultdict(list)

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

#print(g)
q = deque()
q.append((1, 0))

res = []
n = 0
while q:
  #print(q)
  node, color = q.popleft()
  
  n = max(n, color)
  i = 1
  for nei in g[node]:
    if i == color:
      i += 1
    q.append((nei, i))
    res.append(i)
    i += 1
print(n)
for c in res:
  print(c)

Submission status: Wrong Answer

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

a,b = [],[]
graph = [[] for i in range(N+1)]
for i in range(N-1):
  a.append(AB[i][0])
  b.append(AB[i][1])
  graph[a[i]].append(b[i])
  graph[b[i]].append(a[i])
#print("graph:", graph)

parent = [0] * (N+1)
order = []
stack = [1]

while stack:
  s = stack.pop() #後入れ先出し。深さ優先探索。
  order.append(s)
  for g in graph[s]:
    if g == parent[s]: ###ここ間違えたので注意。parentならcontinue。
      continue    
    #if parent[g] == 0:
    parent[g] = s
    stack.append(g)
#print("order:", order) #右手迷路完成。深さ優先探索。
#print("parent:", parent)
color = [-1] * (N+1)

for r in order:
  ng = parent[r]
  c = 1
  for g in graph[r]:
    if g == parent[r]: ###やはりこいつを忘れがち。逆走はしない。
      continue
    if g == ng:
      c += 1
    color[g] = c #edgeを見るときはparentを見る。
    c += 1
#print(color)

answer = []
for a,b in AB:
  if a == parent[b]:
    answer.append(color[b])
  else:
    answer.append(color[a])
print(max(answer))
print("\n".join(map(str,answer)))

Submission status: Wrong Answer

Solution code:
#入力時間の差分を見ておく。
#余計なprintでWAにしておく。
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)) #zipでmとmを結合して一つの配列にしている
#print("AB:", AB)

#グラフの書き方はN^2ではなくこれ。N=10^5のとき。
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1 #根を仮に1としている。木はどこを根にしても良い。
parent = [0] * (N+1) #根に近い方のノード。一択。
order = [] #???
stack = [root] #スタック：あとに入れたものが先に入る何か

#dequeを用いなくてもstackは可能。
#ノードではなく、グラフの問題@木では親ノードを先に決める。
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]: # 1-2-3 [0,1,2]
      #seenよりもparentと同一かどうかの方が速そう。
      #グラフの繋がりがparentならcontinue、違うなら自身がparent。
      if y == parent[x]:
        continue
      parent[y] = x
      stack.append(y)
print("order:", order) #右手迷路が完成している。
print("parnt:", parent)

color = [-1] * (N+1) #???

#おそらくこのループの最悪値がNlogN
for x in order:
    ng = color[x] #親ノードとのエッジ。
    c = 1 #最小値
    for y in graph[x]: #xのノードを全探索
        if y == parent[x]:  #xの親ノードなら飛ばす
            continue
        if c == ng: #親ノードのエッジの色の時に++。親ノードを決めることで、エッジを一択に。
            c += 1
        color[y] = c
        c += 1
#オーダーの際のエッジの色が出た。
#これは標準入力の順番とは異なる。
print("color:", color)


answer = []
#
for a,b in AB:
    if parent[a] == b: #子ノードの番号を見る。
        answer.append(color[a])
    else:
        answer.append(color[b])

K = max(answer)
print(K)
print('\n'.join(map(str,answer))) #for文を書かない出力のこの形式は綺麗。

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n-1)

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    t[a].append((b, i))
q = deque([(0, 0)])
while q:
    print(q)
    v, pc = q.popleft()
    nc = 0
    for nv, edge in t[v]:
        nc += 1
        if nc == pc:
            nc += 1
        color[edge] = nc
        q.append((nv, nc))

print(max(color))
print(*color, sep="\n")

Submission status: Wrong Answer

Solution code:
#入力時間の差分を見ておく。
#余計なprintでWAにしておく。
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)) #zipでmとmを結合して一つの配列にしている
#print("AB:", AB)

#グラフの書き方はN^2ではなくこれ。N=10^5のとき。
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1 #根を仮に1としている。木はどこを根にしても良い。
parent = [0] * (N+1) #根に近い方のノード。一択。
order = [] #???
stack = [root] #スタック：あとに入れたものが先に入る何か

#dequeを用いなくてもstackは可能。
#ノードではなく、グラフの問題@木では親ノードを先に決める。
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]: # 1-2-3 [0,1,2]
      #seenよりもparentと同一かどうかの方が速そう。
      #グラフの繋がりがparentならcontinue、違うなら自身がparent。
      if y == parent[x]:
        continue
      parent[y] = x
      stack.append(y)
print("order:", order) #右手迷路が完成している。
print("parnt:", parent)

color = [-1] * (N+1) #???

#おそらくこのループの最悪値がNlogN
for x in order:
    ng = color[x] #親ノードとのエッジ。
    c = 1 #最小値
    for y in graph[x]: #xのノードを全探索
        if y == parent[x]:  #xの親ノードなら飛ばす
            continue
        if c == ng: #親ノードのエッジの色の時に++。親ノードを決めることで、エッジを一択に。
            c += 1
        color[y] = c
        c += 1
#オーダーの際のエッジの色が出た。
#これは標準入力の順番とは異なる。
print("color:", color)


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

K = max(answer)
print(K)
print('\n'.join(map(str,answer))) #for文を書かない出力のこの形式は綺麗。

Submission status: Wrong Answer

Solution code:
n = int(input())
neibors = [[] for _ in range(n)]
colors = [-1 for _ in range(n - 1)]
for i in range(n - 1):
  a, b = tuple(map(int, input().split(' ')))
  used_color = []
  for nei in neibors[a - 1] + neibors[b - 1]:
  	used_color.append(colors[nei])
  sorted(used_color)
  
  for j in range(len(used_color)):
    if used_color[j] != j + 1:
      colors[i] = j + 1
  else:
    colors[i] = len(used_color) + 1
      
  neibors[a - 1].append(i)
  neibors[b - 1].append(i)

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

Submission status: Wrong Answer

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N = read_int(input_stream)
  color_table = [set() for i in range(N)]
  combination = []
  ans = 0
  for index in range(N-1):
    i,j = read_ints(input_stream)
    i -= 1
    j -= 1
    for k in range(1, N*2):
      if k not in color_table[i] and k not in color_table[j]:
        color_table[i].add(k)
        color_table[j].add(k)
        combination.append(str(k))
        ans = max(ans, len(color_table[i]), len(color_table[j]))
        break
  result = [str(ans)]
  result.extend(combination)
  return result



def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Wrong Answer

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N = read_int(input_stream)
  color_table = [set() for i in range(N)]
  combination = []
  ans = 0
  for index in range(N-1):
    i,j = read_ints(input_stream)
    i -= 1
    j -= 1
    for k in range(1, N):
      if k not in color_table[i] and k not in color_table[i]:
        color_table[i].add(k)
        color_table[j].add(k)
        combination.append(str(k))
        ans = max(ans, len(color_table[i]), len(color_table[j]))
        break
  result = [str(ans)]
  result.extend(combination)
  return result



def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
color = {1}
nodes = []
a_l, b_l = [], []
for i in range(N-1):
    a,b = map(int, input().split())
    a_l.append(a)
    b_l.append(b)
for a, b in zip(a_l, b_l):
    if a not in dic and b not in dic:
        dic[a] = {1}
        dic[b] = {1}
        nodes.append(1)
    elif a not in dic and b in dic:
        for i in range(1,N):
            if i not in dic[b]:
                nodes.append(i)
                dic[a] = {i}
                dic[b].add(i)
                color.add(i)
                break
    elif b not in dic and a in dic:
        for i in range(1,N):
            if i not in dic[a]:
                nodes.append(i)
                dic[b] = {i}
                dic[a].add(i)
                color.add(i)
                break
    else:
        used = dic[a] | dic[b]
        for i in range(1,N):
            if i not in used:
                dic[a].add(i)
                dic[b].add(i)
                nodes.append(i)
                color.add(i)
                break
print(len(color))
for i in nodes:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
color = {1}
nodes = []
a_l, b_l = [], []
for i in range(N-1):
    a,b = map(int, input().split())
    a_l.append(a)
    b_l.append(b)
for a, b in zip(a_l, b_l):
    if a not in dic and b not in dic:
        dic[a] = [1]
        dic[b] = [1]
        nodes.append(1)
    elif a not in dic and b in dic:
        used = set(dic[b])
        for i in range(1,N):
            if i not in used:
                nodes.append(i)
                dic[a] = [i]
                dic[b].append(i)
                color.add(i)
                break
    elif b not in dic and a in dic:
        used = set(dic[a])
        for i in range(1,N):
            if i not in used:
                nodes.append(i)
                dic[b] = [i]
                dic[a].append(i)
                color.add(i)
                break
    else:
        used = set(dic[a]) | set(dic[b])
        for i in range(1,N):
            if i not in used:
                dic[a].append(i)
                dic[b].append(i)
                nodes.append(i)
                color.add(i)
                break
print(len(color))
for i in nodes:
    print(i)

Submission status: Wrong Answer

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

cs = [1]
c = 1
max_c = 1

for i,(a,b) in enumerate(G[1:]):
    if a in G[i] or b in G[i]:
        c += 1
        max_c = max(c, max_c)
    else:
        c = 1
    cs.append(c)

print(max_c)
for cc in cs:
    print(cc)

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    
    list_a = []
    already_point = [0] * N
    max_color = 0

    for i in range(N-1):

        a, b = map(int, input().split())
        already_point[a-1] = already_point[a-1] + 1
        already_point[b-1] = already_point[b-1] + 1

        if(max_color < already_point[a-1]):
            max_color = already_point[a-1]

        if(max_color < already_point[b-1]):
            max_color = already_point[b-1]

        list_a.append([a-1, b-1])

    print(max_color)

    list_b = []

    for i in range(N):
        list_b.append([])

    for item_list in list_a:

        already_color = set(list_b[item_list[0]] + list_b[item_list[1]])

        for i in range(max_color):

            if i not in already_color:

                print(i+1)
                list_b[item_list[0]].append(i)
                list_b[item_list[1]].append(i)
                break

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
s = [[] for _ in range(N+1)]
ans = [0 for _ in range(N-1)]
m = 1
for i in range(N-1):
    a,b = map(int,input().split())
    r = m + 1
    for j in range(1,m+1):
        if j in s[a] or j in s[b]:
            continue
        else:
            r = j
            break
    s[a].append(r)
    s[b].append(r)
    ans[i] = r
    if r > m:
        m = r
print(m)
for i in range(N-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [0 for i in range(n-1)]
node = [[0] for i in range(n)]
max_c = 1
for i in range(n-1):
    node1, node2 = map(int, input().split())
    c1 = max(node[node1 - 1])
    c2 = max(node[node2 - 1])
    c = max(c1, c2) + 1
    for j in range(c - 1):
        if not(j in node[node1 - 1]) and not(j in node[node2-1]):
            c = j
            break
    node[node1-1].append(c)
    node[node2-1].append(c)
    edge[i] = c
    max_c = max(c, max_c)
print(max_c)
for i in edge:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())



def isset(array, num):
  try:
    _var = array[str(num)]
  except KeyError:
    return False
  return True


def set_col(ai, bi, tree_col_list):
  used_a = []
  used_b = []
  if isset(tree_col_list, ai):
    used_a = tree_col_list[str(ai)]
  if isset(tree_col_list, bi):
    used_b = tree_col_list[str(bi)]
  for i in range(1, n + 1):
    if i in used_a or i in used_b:
      continue
    else:
      used_a.append(i)
      used_b.append(i)
      tree_col_list[str(ai)] = used_a
      tree_col_list[str(bi)] = used_b
      return i, tree_col_list
  raise Exception("hoge")

tree_col_list = {}
result = []
while True:
  try:
    ai, bi = list(map(int, input().split()))
    r, tree_col_list = set_col(ai, bi, tree_col_list)
    result.append(r)
  except EOFError:
    break

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

Submission status: Wrong Answer

Solution code:
def top_sort_tree(g,root):
    n = len(g)
    parent = [-1]*n
    top_order = [-1]*n
    pos = 0
    q = [root]
    #from collections import deque
    #q = deque([root])
    while q:
        v = q.pop()
        top_order[pos] = v
        pos += 1
        for c in g[v]:
            if c != parent[v]:
                parent[c] = v
                q.append(c)

    return top_order

#####################################

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

n = int(input())
ab = map(int,read().split())

g = [[] for _ in range(n)]
for a,b in zip(ab,ab):
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
#print(g)
print(top_sort_tree(g,0)[0])

Submission status: Wrong Answer

Solution code:

def top_sort_tree(g,root):
    n = len(g)
    parent = [-1]*n
    top_order = [-1]*n
    pos = 0
    #q = [root]
    from collections import deque
    q = deque([root])
    while q:
        v = q.popleft()
        top_order[pos] = v
        pos += 1
        for c in g[v]:
            if c != parent[v]:
                parent[c] = v
                q.append(c)

    return top_order

#####################################

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

n = int(input())
ab = map(int,read().split())

g = [[] for _ in range(n)]
for a,b in zip(ab,ab):
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
#print(g)
print(top_sort_tree(g,0)[0])

Submission status: Wrong Answer

Solution code:

def top_sort_tree(g,root):
    n = len(g)
    parent = [-1]*n
    top_order = [-1]*n
    pos = 0
    #q = [root]
    from collections import deque
    q = deque([root])
    while q:
        v = q.pop()
        top_order[pos] = v
        pos += 1
        for c in g[v]:
            if c != parent[v]:
                parent[c] = v
                q.append(c)

    return top_order

#####################################

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

n = int(input())
ab = map(int,read().split())

g = [[] for _ in range(n)]
for a,b in zip(ab,ab):
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
#print(g)
print(top_sort_tree(g,0)[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
import numpy as np
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
for child in sorted(children.keys()):
    used = np.zeros((100000),dtype="bool")
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.argmin()+1
        ans[j] = temp
        used[temp-1] = True
for b in B:
    print(ans[b])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
for i in range(n-1):
  a[i],b[i]=map(int,input().split())
  
lis=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
  lis[a[i]][b[i]]=1
  lis[b[i]][a[i]]=1
ans=0
for i in range(n+1):
  num=sum(lis[i])
  ans=max(num,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
count = [0 for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = max(count)

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in reversed(range(MAX)):
    c = l+1
    if c in used[i-1] or c in used[j-1]:
      continue
    used[i-1].add(c)
    used[j-1].add(c)
    color[k] = c
    break

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
count = [0 for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = max(count)
if MAX > N-1:
  print(Z)

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in range(MAX):
    c = l+1
    if c in used[i-1] or c in used[j-1]:
      continue
    used[i-1].add(c)
    used[j-1].add(c)
    color[k] = c
    break

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

Submission status: Wrong Answer

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

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in range(N-1):
    c = l+1
    if c in used[i-1] or c in used[j-1]:
      continue
    used[i-1].add(c)
    used[j-1].add(c)
    color[k] = c
    break

MAX = max([len(i) for i in used])
print(MAX)
for i in color:
  print(i)

Submission status: Wrong Answer

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

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

count = [0 for _ in range(N)]
for [i,j] in edges:
  count[i-1] += 1
  count[j-1] += 1
MAX = max(count)

used = [set() for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in range(MAX):
    c = l+1
    if c in used[i-1] or c in used[j-1]:
      continue
    used[i-1].add(c)
    used[j-1].add(c)
    color[k] = c
    break

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