Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:
N = int(input())
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 = [[] 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].append(c)
    used[j-1].append(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)]

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

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

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

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !

import sys
sys.setrecursionlimit(10**6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])
    print(v)
 
ans = [None] * (N-1)
 
def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]

Submission status: Wrong Answer

Solution code:
import queue

n = int(input())
G = [[] for i in range(n)]
vp = [() for i in range(n - 1)]

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

que = queue.Queue()
que.put(0)
used = [0] * n
used[0] = 1
K = 0
cs = [0] * n
dic = {}
while not que.empty():
        v = que.get()
        if len(G[v]) > K:
                K = len(G[v])
        col = 1
        for u in G[v]:
                print(u)
                if used[u]:
                        continue
                if col == cs[v]:
                        col += 1
                cs[u] = col
                dic[(u, v)] = col
                dic[(v, u)] = col
                col += 1
                used[u] = 1
                que.put(u)
print(K)
for i in vp:
        print(dic[i])

Submission status: Wrong Answer

Solution code:
from collections import deque


test = ""
test = \
"""
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
"""
test = list(reversed(test.strip().splitlines()))
if test:
    def inp():
        return test.pop()
else:
    def inp():
        return input()
    

n = int(inp())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, inp().split()))


adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)
root = 0

Submission status: Wrong Answer

Solution code:
from collections import deque


test = ""
#test = \
"""
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
"""
test = list(reversed(test.strip().splitlines()))
if test:
    def inp():
        return test.pop()
else:
    def inp():
        return input()
    

n = int(inp())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, inp().split()))


adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)
root = 0
for i in range(0, n+1):
    if len(adjacency_list[i]) == max_order:
        root = 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])

paint = [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 = [[] for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in range(MAX):
    c = l+1
    if c not in used[i-1] and c not in used[j-1]:
      used[i-1].append(c)
      used[j-1].append(c)
      paint[k] = c
      break

print(MAX)
for i in paint:
  print(int(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])
paint = [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 = [[] for _ in range(N)]

for k, [i,j] in enumerate(edges):
  for l in range(MAX):
    c = l+1
    if c not in used[i-1] and c not in used[j-1]:
      used[i-1].append(c)
      used[j-1].append(c)
      paint[k] = c
      break

print(MAX)
for i in paint:
  print(int(i))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
edges = []
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
paint = np.zeros(N-1)
count = [0 for _ in range(N+1)]
for [i,j] in edges:
  count[i] += 1
  count[j] += 1
MAX = max(count)

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

for k, [i,j] in enumerate(edges):
  c = 0
  for l in range(MAX):
    c = l+1
    if c not in used[i-1] and c not in used[j-1]:
      used[i-1].append(c)
      used[j-1].append(c)
      paint[k] = c
      break

print(MAX)
for i in list(paint):
  print(int(i))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
edges = []
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
paint = np.zeros(N-1)
count = np.zeros(N+1)
count += 1
count = list(count)

for i in range(N):
  for j in range(i+1,N+1):
    if [i,j] in edges:
      paint[edges.index([i,j])] = max(count[i],count[j])
      count[i], count[j] = count[i]+1, count[j]+1

print(int(max(count)-1))
for i in list(paint):
  print(int(i))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
road=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n-1):
    a[i],b[i]=map(int,input().split())
    road[a[i]][b[i]] = 1
    road[b[i]][a[i]] = 1
ma=0
for i in range(n+1):
    now=0
    ma=max(ma,sum(road[i]))
print(ma)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
road=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n-1):
    a[i],b[i]=map(int,input().split())
    road[a[i]][b[i]] = 1
    road[b[i]][a[i]] = 1
ma=0
for i in range(n+1):
    now=0
    for j in range(n+1):
        if road[i][j]==1:
            now+=1
    ma=max(ma,now)
print(ma)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n - 1)] 
dic = {}
tmp = 0 
color = []
for i in p:
        if i[0] in dic:
                dic[i[0]] = dic[i[0]] + 1 
                color.append(dic[i[0]])
        else:
                dic[i[0]] = 1 
                if i[1] in dic:
                        dic[i[1]] = dic[i[0]] + 1 
                        color.append(dic[i[1]])
                else:
                        dic[i[1]] = 1 
                        color.append(1)
print(max(color))
for i in color:
        print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

"""
for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color
"""

color_edges(0, 1)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

roots = [node for node in ends if len(ends[node]) > 1]
if len(roots) > 0:
    root = roots[0]
else:
    root = 1

def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

"""
for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color
"""

color_edges(0, root)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if leaf not in edges[e]]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            del(_ends[parent])

for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
road=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n-1):
    a[i],b[i]=map(int,input().split())
    road[a[i]][b[i]] = 1
ma=0
for i in range(n+1):
    now=0
    for j in range(n+1):
        if road[i][j]==1:
            now+=1
    ma=max(ma,now)
print(ma)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(E.keys())
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

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

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = sorted([(i,-len(ends[i])) for i in ends], key = lambda a: a[1])
order = [t[0] for t in order]

for i in range(N):
    ii = order[i]
    p = palette[:]
    for j in ends[ii]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

for i in range(1,N):
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color

print(len(palette))
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

for i in range(1,N):
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color

for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
n = int(input())

#1っこ多くしていることに注意。０番目は必ずから。頂点のindexをそのままいれておk
data = [[] for _ in range(n+1)]
for _ in range(n-1):
    line = input()
    a, b = map(int, line.split(" "))
    data[a].append(b)
    data[b].append(a)

max = 0
for ele in data:
    if len(ele) > max:
        max = len(ele)

print(max)

Submission status: Wrong Answer

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

check=[False]*n
ans=[[0 for i in range(n)]for j in range(n)]

from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678

while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		q.append(next)
		iro+=1

print(max(max(ans)))

for i in range(n-1):
	print(ans[ab[i][0]][ab[i][1]])

Submission status: Wrong Answer

Solution code:
N = int(input())

TopList = []#頂点から最少の色の数を求める
GList = []#i + 1行目の保存

ColorList = []
for i in range(0, N):
    if i != 0:
        GList.append([0, 0])
    TopList.append(0)
    ColorList.append([])

for i in range(0, N - 1):
    A, B = map(int, input().split())
    TopList[A - 1] += 1
    TopList[B - 1] += 1
    GList[i][0] = A
    GList[i][1] = B

count = -1
for i in range(0, len(TopList)):
    if count < TopList[i]:
        count = TopList[i]

print(count)
for i in range(0, len(GList)):
    for q in range(1, count + 1):#color決め
        if q in ColorList[GList[i][0] - 1]:
            continue
        elif q in ColorList[GList[i][1] - 1]:
            continue
        else:
            ColorList[GList[i][0] - 1].append(q)
            ColorList[GList[i][1] - 1].append(q)
            print(q)
            break

Submission status: Wrong Answer

Solution code:
N = int(input())

TopList = []#頂点から最少の色の数を求める
GList = []#i + 1行目の保存

ColorList = []
for i in range(0, N):
    if i != 0:
        GList.append([0, 0])
    TopList.append(0)
    ColorList.append([])

for i in range(0, N - 1):
    A, B = map(int, input().split())
    TopList[A - 1] += 1
    TopList[B - 1] += 1
    GList[i][0] = A
    GList[i][1] = B

count = -1
for i in range(0, len(TopList)):
    if count < TopList[i]:
        count = TopList[i]

print(count)
for i in range(0, len(GList)):
    for q in range(0, count):#color決め
        if q in ColorList[GList[i][0] - 1]:
            continue
        elif q in ColorList[GList[i][1] - 1]:
            continue
        else:
            ColorList[GList[i][0] - 1].append(q)
            ColorList[GList[i][1] - 1].append(q)
            print(q)
            break

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
graph=[[] for i in range(n)]#0-indexed
edges=[tuple(map(int,input().split())) for i in range(n-1)]#1-indexed
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}#0-indexed
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
if most_connected>graph[most_connected][0]:
  most_connected,graph[most_connected][0]=graph[most_connected][0],most_connected
edge_color[(most_connected,graph[most_connected][0])]=1
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    #print((V,I))
    edge_color[(V,I)]=vertex[V]%color+1
    vertex[V],vertex[I]=vertex[V]%color+1,vertex[V]%color+1 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

Submission status: Wrong Answer

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	maxd=0
	edges=[0]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		adj[b].append(a)
		edges.append(0)
		dic[(a,b)]=i+1
		if(maxd<len(adj[a])):
			maxd=len(adj[a])
			indx=a
		if(maxd<len(adj[b])):
			maxd=len(adj[b])
			indx=b
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	#print(available)
	#print(adj)
	for i in range(1,n+1):
		for j in adj[i]:
			if (i,j) in dic:
				if(edges[dic[(i,j)]]==0):
					edges[dic[(i,j)]]=available[i][0]
					available[j].remove(available[i][0])
					available[i].pop(0)
					
			if (j,i) in dic:
				if(edges[dic[(j,i)]]==0):
					edges[dic[(j,i)]]=available[j][0]
					available[i].remove(available[j][0])
					available[j].pop(0)
	print(edges)
	print(maxd)
	for i in range(1,len(edges)):
		print(edges[i])
main()

Submission status: Wrong Answer

Solution code:
def main():
	n=int(input())
	indx=0
	dic={}
	#print(dic)
	maxd=0
	edges=[0]
	adj=[[] for i in range(n+1)]
	for i in range(n-1):
		ab=input().split()
		a=int(ab[0])
		b=int(ab[1])
		adj[a].append(b)
		adj[b].append(a)
		edges.append(0)
		dic[(a,b)]=i+1
		if(maxd<len(adj[a])):
			maxd=len(adj[a])
			indx=a
		if(maxd<len(adj[b])):
			maxd=len(adj[b])
			indx=b
	#print(maxd)
	visited=[[0 for i in range(maxd+1)] for i in range(n+1)]
	available=[[i+1 for i in range(maxd)] for i in range(n+1)]
	#print(available)
	#print(dic)
	a=indx
	for i in range(len(adj[indx])):
		b=adj[indx][i]
		if (a,b) in dic:
			edges[dic[(a,b)]]=i+1
		else:
			edges[dic[(b,a)]]=i+1
		#print(i+1)
		available[a].remove(i+1)
		available[b].remove(i+1)
	#print(available)
	#print(adj)
	for i in range(1,n+1):
		for j in adj[i]:
			#print(i,j)
			if (i,j) in dic:
				#print('hello')
				if(edges[dic[(i,j)]]==0):
					#print('Hello')
					edges[dic[(i,j)]]=available[i][0]
					available[i].pop(0)
					available[j].pop(0)
			if (j,i) in dic:
				if(edges[dic[(j,i)]]==0):
					#print('Hello')
					
					edges[dic[(j,i)]]=available[j][0]
					available[i].pop(0)
					available[j].pop(0)
	print(maxd)
	for i in range(1,len(edges)):
		print(edges[i])




main()

Submission status: Wrong Answer

Solution code:
import collections

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

n = int(input())
al = []
bl = []
cl = []
ngl = []
for i in range(n-1):
    a,b = map(int,input().split())
    #aがすでにalに入っているとき
    if a in al:
        d = my_index_multi(al,a)
        for x in d:
            ngl.append(cl[x])
    if b in al:
        d = my_index_multi(al,b)
        for x in d:
            ngl.append(cl[x])        
    if a in bl:
        d = my_index_multi(bl,a)
        for x in d:
            ngl.append(cl[x])
    if b in bl:
        d = my_index_multi(bl,b)
        for x in d:
            ngl.append(cl[x])
    al.append(a)
    bl.append(b)
    if ngl == []:
        cl.append(1)
    if ngl != []:
        for i,ng in enumerate(set(ngl),1):
            if ng != i:
                cl.append(i)
                ngl = []
                break
    if ngl != []:
        cl.append((max(ngl)+1))
    ngl = []
print(len(collections.Counter(cl)))
for i in range(len(cl)):
    print(cl[i])

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

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

p = [0] * n
c = [0] * n
d = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0

q = [0]
p[0] = -1

while q:
    x = q.pop()
    temp = c[x]
    color = 1
    me = max(me, len(e[x]))
    for y in e[x]:
        if color == temp:
            color += 1
        if d[y] == 0:
            q.append(y)
            c[y] = color
            p[y] = x
        color += 1
    d[x] = 1

print(me)

for a, b in ab:
    if p[a] == b:
        print(c[a])
    else:
        print(c[b])

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

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

p = [0] * n
c = [0] * n
d = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0

q = [0]
p[0] = -1

while q:
    x = q.pop()
    temp = c[x]
    color = 0
    me = max(me, len(e[x]))
    for y in e[x]:
        if color == temp:
            color += 1
        if d[y] == 0:
            q.append(y)
            c[y] = color
            p[y] = x
        color += 1
    d[x] = 1

print(me)

for a, b in ab:
    if p[a] == b:
        print(c[a])
    else:
        print(c[b])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    children[a-1].append((i+1,b-1))

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child[0]] = color
        queue.append(child[1])
        color += 1
    maxColor = max(maxColor, color-1)

print(maxColor)
for i in range(1,N):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
dim = [0 for _ in range(n+1)] #次数のカウント
parent = [0 for _ in range(n+1)] #頂点iの親
col = [[] for _ in range(n+1)]  #頂点iが使っている色
AB = []
for i in range(n-1):
    a, b = map(int, input().split())
    AB.append([a, b, i])
    parent[b] = a
    dim[a] += 1
    dim[b] += 1
#幅優先探索のためにソート
AB_sorted = sorted(AB)
prev_a = -1
for j in range(n-1):
    a = AB_sorted[j][0]
    b = AB_sorted[j][1]
    index = AB_sorted[j][2]
    if a != prev_a:
        paint = 1
    
    while paint in col[ parent[a] ]:#親が使っていない色にする
        paint += 1
    col[a].append(paint) #自分が使ったと記録
    col[parent[a]].append(paint) #親が使ったと記録
    AB[index].append(paint) #辺の色を追加
    prev_a = a

print(max(dim))
for i in range(n-1):
    print(AB[i][3])

Submission status: Wrong Answer

Solution code:
n = int(input())
dim = [0 for _ in range(n+1)] #次数のカウント
parent = [0 for _ in range(n+1)] #頂点iの親
col = [[] for _ in range(n+1)]  #頂点iが使っている色
AB = []
for i in range(n-1):
    a, b = map(int, input().split())
    AB.append([a, b, i])
    parent[b] = a
    dim[a] += 1
    dim[b] += 1
#幅優先探索のためにソート
AB_sorted = sorted(AB)
prev_a = -1
for j in range(n-1):
    a = AB_sorted[j][0]
    b = AB_sorted[j][1]
    index = AB_sorted[j][2]
    if a != prev_a:
        paint = 0
    
    while paint in col[ parent[a] ]:#親が使っていない色にする
        paint += 1
    col[a].append(paint) #自分が使ったと記録
    col[parent[a]].append(paint) #親が使ったと記録
    AB[index].append(paint) #辺の色を追加
    prev_a = a

print(max(dim))
for i in range(n-1):
    print(AB[i][3])

Submission status: Wrong Answer

Solution code:
n=int(input())

nodes=[[] for i in range(n)]
ans=[]
for i in range(n-1):
    a,b=list(map(int, input().split()))
    for c in range(1,n+1):
        if c not in nodes[a-1] and c not in nodes[b-1]:
            nodes[a-1].append(c)
            nodes[b-1].append(c)
            ans.append(c)
            # print("{}{} {}{} {}".format(a-1,nodes[a-1],b-1,nodes[b-1],nodes))
            break

# print(nodes)
print(len(max(nodes,key=lambda x: max(x))))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    keys = [tuple(int(i)-1 for i in input().split()) for _ in range(N-1)]
    for e in keys:
        G[e[0]].append(e[1])
        G[e[1]].append(e[0])
    max_deg = 0
    for g in G:
        max_deg = max(max_deg, len(g))
    edge_color = {k: 0 for k in keys}
    colors = [i+1 for i in range(max_deg)]

    G_color = ['WHITE' for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            c = 0
            if G_parent[u] != "NIL" and colors[c] == edge_color[(G_parent[u], u)]:
                c = (c+1) % max_deg
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = colors[c]
                    c = (c+1) % max_deg
            G_color[u] = 'BLACK'

    bfs(0)
    print(max_deg)
    for k in keys:
        print(edge_color[k])


if __name__ == '__main__':
    main()