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 queue import Queue

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = {}
        
    def add_edge(self, v1, v2):
        self.adjacency_dict[v1][v2] = -1
        self.adjacency_dict[v2][v1] = -1
    
    def paint(self, v1, v2, color):
        self.adjacency_dict[v1][v2] = color
        self.adjacency_dict[v2][v1] = color
        
    def get_color(self, v1, v2):
        return self.adjacency_dict[v1][v2]
    
    def next_vertices(self, v):
        return self.adjacency_dict[v]


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


tree = Graph()
for i in range(1, N+1):
    tree.add_vertex(i)
for a,b in edges:
    tree.add_edge(a, b)

most_edges_vertex = -1
max_colors = 0
for k,v in tree.adjacency_dict.items():
    if len(v) > max_colors:
        most_edges_vertex = k
        max_colors = len(v)


# BFS
prev_color = -1
q = Queue()
q.put(most_edges_vertex)
while not q.empty():
    vertex = q.get()
    nexts = tree.next_vertices(vertex)
    color = 1 if prev_color != 1 else 2

    for v,c in nexts.items():
        if c > 0:
            continue
        q.put(v)
        
        # 色ぬり
        tree.paint(vertex, v, color)
        
        # 次の色
        color += 1
        if color == prev_color:
            color += 1

print(max_colors)
for v1,v2 in edges:
    print(tree.get_color(v1, v2))

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N)]

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

ans = [0] * (N - 1)
q = deque([[1, 0, -1]])
while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node: continue
        if cnt == pcol: cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1
print(ans)
print(max(ans))
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [set() for i in range(n)]

for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  if i == 0:
    s = b
  a[b].add(c)
  a[c].add(b)


col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [s]

while v:
  d = v.pop(0)
  k = 1
  for i in a[d]:
    if visited[i] == False:
      if col[d] == k:
        k += 1
      col[i] = k
      visited[i] = True
      v.append(i)
      k += 1

print (max(col))
for i in col[1:]:
  print (i)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [set() for i in range(n)]

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


col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [0]

while v:
  d = v.pop(0)
  k = 1
  for i in a[d]:
    if visited[i] == False:
      if col[d] == k:
        k += 1
      col[i] = k
      visited[i] = True
      v.append(i)
      k += 1

print (max(col))
for i in col[1:]:
  print (i)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = [set() for _ in range(N)]
c=[]
for i in range(N-1):
  x,y = (int(r) for r in input().rstrip('\n').split())
  cm = d[x-1]|d[y-1]
  for m in range(N+1):
    if m not in cm:
      c.append(m)
      d[x-1].add(m)
      d[y-1].add(m)
      break
print(max(c)+1)
for a in c:
  print(a+1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = [[] for i in range(N)]
c=[]
C=[]
for _ in range(N-1):
  C.extend(int(r)-1 for r in input().rstrip('\n').split())
K=max(C.count(x) for x in range(N))
print(K)
for i in range(N-1):
  a = C[2*i]
  b = C[1+2*i]
  print(max(C[:2*i+1].count(a),C[:2*i+1].count(b)))

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = [[] for i in range(N)]
c=[]
for i in range(N-1):
  x,y = (int(r)-1 for r in input().rstrip('\n').split())
  p = set(d[x])
  q = set(d[y])
  cm = p|q
  for m in range(N+1):
    if m not in cm:
      c.append(m)
      d[x].append(m)
      d[y].append(m)
      break
print(max(c)+1)
for a in c:
  print(a+1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = {i:[] for i in range(1,N+1)}
c=[]
for i in range(N-1):
  x,y = (int(r) for r in input().rstrip('\n').split())
  p = set(d[x])
  q = set(d[y])
  cm = p|q
  for m in range(N+1):
    if m not in cm:
      c.append(m)
      d[x].append(m)
      d[y].append(m)
      break
print(max(c)+1)
for a in c:
  print(a+1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = {i:[] for i in range(1,N+1)}
c=[]
for i in range(N-1):
  x,y = (int(x) for x in input().rstrip('\n').split())
  p = set(d[x])
  q = set(d[y])
  cm = p|q
  for m in range(N+1):
    if m not in cm:
      c.append(m)
      d[x].append(m)
      d[y].append(m)
      break
print(max(c)+1)
for a in c:
  print(a+1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d = {i:[] for i in range(1,N+1)}
c=[]
k=0
for i in range(N-1):
  x,y = (int(x) for x in input().rstrip('\n').split())
  p = set(d[x])
  q = set(d[y])
  cm = p|q
  cm = cm|set([N])
  for m in range(max(cm)+1):
    if m not in cm:
      c.append(m)
      d[x].append(m)
      d[y].append(m)
      break
print(max(c)+1)
for a in c:
  print(a+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

stack = deque([0])
stack.append(0)
ans = [0 for _ in range(n)]
while stack:
    v = stack.popleft()
    c = 1
    for nv in g[v]:
        if ans[v] == c:
            c += 1
        ans[nv] = c
        c += 1
        stack.append(nv)

print(max(ans))
for i in range(n):
    if ans[i] == 0:
        continue
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

ma = 0
for i in range(n):
    ma = max(ma, len(g[i]))

seen = [False] * n
stack = deque()
stack.append(0)
ans = [0] * n
while stack:
    v = stack.popleft()
    seen[v] = True
    i = 1
    for nv in g[v]:
        if seen[nv]:
            continue
        if ans[v] == i:
            i += 1
        ans[nv] = i
        i += 1
        stack.append(nv)

print(ma)
for i in range(1, n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

ma = 0
for i in range(n):
    ma = max(ma, len(g[i]))

seen = [False] * n
stack = deque()
stack.append(0)
ans = [0] * n
while stack:
    v = stack.pop()
    seen[v] = True
    i = 1
    for nv in g[v]:
        if seen[nv]:
            continue
        if ans[v] == i:
            i += 1
        ans[nv] = i
        i += 1
        stack.append(nv)

print(ma)
for i in range(1, n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append([b-1,i])
        edge[b-1].append([a-1,i])
    cols = [0]*(n-1)#i番目の辺の色
    max_c = [0]*(n)
    que=deque()
    c = 1
    max_color = 0
    for e in edge[0]:
        que.append([e,c])
        c+=1
    for i in range(n):
        max_c[i] = len(edge[i])
        max_color = max(max_c[i],max_color)

    while que:
        v=que.popleft()
        ver = v[0]
        color = v[1]

        if(cols[ver[1]]>0):
            continue
        else:
            cols[ver[1]] = color
            new_c = max_c[ver[0]]
            for next_v in edge[ver[0]]:
                if(new_c==color):
                    new_c -= 1
                que.append([next_v,new_c])
                new_c -= 1

    print(max_color)
    for i in range(n-1):
        print(cols[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append([b-1,i])
        edge[b-1].append([a-1,i])
    cols = [0]*(n-1)#i番目の辺の色
    max_c = [0]*(n)
    que=deque()
    c = 1
    max_color = 0
    for e in edge[0]:
        que.append([e,c])
        c+=1
    for i in range(n):
        max_c[i] = len(edge[i])
        max_color = max(max_c[i],max_color)

    while que:
        v=que.popleft()
        ver = v[0]
        color = v[1]

        if(cols[ver[1]]>0):
            continue
        else:
            cols[ver[1]] = color
            new_c = max_c[i]
            for next_v in edge[ver[0]]:
                if(new_c==color):
                    new_c -= 1
                que.append([next_v,new_c])
                new_c -= 1

    print(max_color)
    for i in range(n-1):
        print(cols[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append([b-1,i])
        edge[b-1].append([a-1,i])
    cols = [0]*(n-1)#i番目の辺の色
    max_c = [0]*(n)
    que=deque()
    c = 1
    max_color = 0
    for e in edge[0]:
        que.append([e,c])
        c+=1
    for i in range(n):
        max_c[i] = len(edge[i])
        max_color = max(max_c[i],max_color)

    while que:
        v=que.popleft()
        vertex = v[0][0]
        edge_ind = v[0][1]
        color = v[1]
        col_num = max_c[vertex]

        if(cols[edge_ind]==0):
            cols[edge_ind] = color

            for next_v in edge[vertex]:
                if(col_num==color):
                    col_num-=1
                que.append([next_v,col_num])

    print(max_color)
    for i in range(n-1):
        print(cols[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append([b-1,i])
        edge[b-1].append([a-1,i])
    cols = [0]*(n-1)#i番目の辺の色
    max_c = [0]*(n)
    que=deque()
    c = 1
    max_color = 0
    for e in edge[0]:
        que.append([e,c])
        c+=1
    for i in range(n):
        max_c[i] = len(edge[i])
        max_color = max(max_c[i],max_color)

    while que:
        v=que.popleft()
        ver = v[0]
        color = v[1]

        if(cols[ver[1]]>0):
            continue
        else:
            cols[ver[1]] = color
            new_c = max_color
            for next_v in edge[ver[0]]:
                if(new_c==color):
                    new_c -= 1
                que.append([next_v,new_c])
                new_c -= 1

    print(max_color)
    for i in range(n-1):
        print(cols[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    n = int(input())
    tree = []
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        tree.append([min(a,b),max(a,b),n])
        edge[a-1].append([b-1,i])
        edge[b-1].append([a-1,i])
    cols = [0]*(n-1)#i番目の辺の色
    max_c = [0]*(n)
    tree.sort(key = lambda x:x[0])
    que=deque()
    c = 1
    for e in edge[0]:
        que.append([e,c])
        c+=1
    for i in range(n):
        max_c[i] = len(edge[i])

    while que:
        v=que.popleft()
        ver = v[0]
        color = v[1]

        if(cols[ver[1]]>0):
            continue
        else:
            cols[ver[1]] = color
            new_c = 1
            for next_v in edge[ver[0]]:
                if(new_c==color):
                    new_c += 1
                que.append([next_v,new_c])
                new_c += 1
    print(max(max_c))
    for i in range(n-1):
        print(cols[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = 10**9
def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[[] for _ in range(n+1)]
  reached=[False]*(n+1)
  while q:
    i = q.popleft()
    reached[i] = True
    temp = 1
    for pos in graph[i]:
      if reached[pos]:
        continue
      while temp in color[i] or temp in color[pos]:
        temp += 1
      color[pos].append(temp)
      print(temp)
      temp += 1
      q.append(pos)
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = 10**9
def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[[] for _ in range(n+1)]
  reached=[False]*(n+1)
  while q:
    i = q.popleft()
    reached[i] = True
    temp = 1
    for pos in graph[i]:
      if reached[pos]:
        continue
      while temp in color[i]:
        temp += 1
      color[pos].append(temp)
      print(temp)
      temp += 1
      q.append(pos)
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = 10**9
def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[0]*(n+1)
  reached=[False]*(n+1)
  while q:
    i = q.popleft()
    reached[i] = True
    temp = 1
    for pos in graph[i]:
      if reached[pos]:
        continue
      if temp == color[i]:
        temp += 1
      color[pos] = temp
      print(temp)
      temp += 1
      q.append(pos)
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = 10**9
def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[0]*(n+1)
  reached=[False]*(n+1)
  while q:
    i = q.popleft()
    if reached[i]:
      continue
    temp = 1
    for pos in graph[i]:
      if temp == color[i]:
        temp += 1
      color[pos] = temp
      q.append(pos)
      print(temp)
      reached[pos] = True
      temp += 1
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = 10**9
def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
  ans = 0
  for i in range(1,n):
    ans = max(ans, len(graph[i]))
  print(ans)
  for i in range(n-1):
    print(i%ans + 1)
      
if __name__ == '__main__':
  main()

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())
cnt = [0]*(N+1)
AB = []
for _ in range(N-1):
    a,b = map(int,readline().split())
    cnt[a] += 1
    cnt[b] += 1
    AB.append((a,b))
K = max(cnt)
print(K)
use_cnt = [[] for _ in range(N+1)]
for a,b in AB:
  for i in range(1,K+1):
    if (i not in use_cnt[a]) and (i not in use_cnt[b]):
      print(i)
      use_cnt[a].append(i)
      use_cnt[b].append(i)
      break

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())
cnt = [0]*(N+1)
AB = []
for _ in range(N-1):
    a,b = map(int,readline().split())
    cnt[a] += 1
    cnt[b] += 1
    AB.append((a,b))
K = max(cnt)
print(K)
use_cnt = [0]*(N+1)
for a,b in AB:
    color = max(use_cnt[a],use_cnt[b])
    print(color+1)
    use_cnt[a] = (color+1)%K
    use_cnt[b] = (color+1)%K

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

def coloring(n, previous, col): #頂点nにpreviousから色colで辿ってきた。
	cnt = 1
	for x in graph[n]:
		print(n, x)
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col #やってきた頂点との間における色
		else:
			if cnt == col:
				cnt += 1
			color[(x, n)] = cnt
			color[(n, x)] = cnt
			coloring(x, n, cnt)
			cnt += 1

coloring(0, -1, 0)

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

ans = max([len(x) for x in graph])
print(ans)

color = [set() for _ in range(N)]
for i in range(N-1):
	a, b = ab[i]
	for i in range(1, ans+1):
		if not i in color[a-1] and not i in color[b-1]:
			color[a-1].add(i)
			color[b-1].add(i)
			print(i)
			break

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

ans = max([len(x) for x in graph])
print(ans)

color = [[] for _ in range(N)]
for i in range(N-1):
	a, b = ab[i]
	for i in range(1, ans+1):
		if not i in color[a-1] and not i in color[b-1]:
			color[a-1].append(i)
			color[b-1].append(i)
			print(i)
			break

Submission status: Wrong Answer

Solution code:
#create date: 2020-07-05 13:34

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
    
    l = [-1] * n
    l[0] = 10**10
    q = deque([0])
    while q:
        v = q.popleft()
        vcolor = l[v]
        for i, w in enumerate(g[v]):
            q.append(w)
            if i < vcolor:
                l[w] = i
            else:
                l[w] = i + 1
    #print(l)
    print(max(l[1:])+1)
    for i in l[1:]:
        print(i+1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#create date: 2020-07-05 13:34

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
    
    l = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        m = len(g[v])
        color = list()
        for i in range(n-1):
            if l[v] == i:
                continue
            color.append(i)
        #print(l, v, color)
        for c, w in zip(color, g[v]):
            q.append(w)
            l[w] = c
    print(l)
    print(max(l)+1)
    for i in l[1:]:
        print(i+1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#create date: 2020-07-05 13:34

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
    
    l = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        m = len(g[v])
        color = list()
        for i in range(m+1):
            if l[v] == i:
                continue
            color.append(i)
        for c, w in zip(color, g[v]):
            q.append(w)
            l[w] = c
    
    print(max(l)+1)
    for i in l[1:]:
        print(i+1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
nord = [[0] for _ in range(N+1)]
ansmax = 0
ans = []
for i in range(N-1):
    a, b = map(int, input().split())
    for j in range(1, 10*5+1):
        if (j not in nord[a]) and (j not in nord[b]):
            nord[a].append(j)
            nord[b].append(j)
            ans.append(j)
            break
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]

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

edge_len = list(map(len, edge))
edge_len[0] -= 1

colors = set(range(max(edge_len) + 1))


def bfs(i, used_color):
    valid_colors = copy.deepcopy(colors)
    try:
        valid_colors.remove(used_color)
    except Exception:
        None

    queue = []

    for child, color in zip(edge[i], valid_colors):
        print(color + 1)
        queue.append((child, color))

    for (to, c) in queue:
        bfs(to, c)


print(len(colors))
bfs(0, -1)

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]

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

colors = set(range(max(map(len, edge))))


def bfs(i, used_color):
    valid_colors = copy.deepcopy(colors)
    try:
        valid_colors.remove(used_color)
    except Exception:
        None

    queue = []

    for child, color in zip(edge[i], valid_colors):
        print(color + 1)
        queue.append((child, color))

    for (to, c) in queue:
        bfs(to, c)


print(len(colors))
bfs(0, -1)

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]

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

colors = set(range(max(map(len, edge)) + 1))


def bfs(i, used_color):
    valid_colors = copy.deepcopy(colors)
    try:
        valid_colors.remove(used_color)
    except Exception:
        None

    queue = []

    for child, color in zip(edge[i], valid_colors):
        print(color + 1)
        queue.append((child, color))

    for (to, c) in queue:
        bfs(to, c)


print(len(colors))
bfs(0, -1)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

N = int(input())
Gb = [ [] for _ in range(N) ]
Gu = [ [] for _ in range(N) ]

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

    Gb[a].append(b)
    Gb[b].append(a)

    Gu[a].append(b)

# print(Gu)

colors = list(range(max(map(len, Gb))))

def bfs(vs, p=None):
    valid_colors = filter(lambda c: c != p, colors) if p is not None else colors

    for v, c in zip(vs, valid_colors):
        print(c + 1)
        bfs(Gu[v], c)

print(len(colors))
bfs(Gu[0])

Submission status: Wrong Answer

Solution code:
"""2020/7/2再挑戦"""
#幅優先探索 親の頂点と色を覚えておく。親の色を除く＋1ずつ足していく。color_maxを超えたら余りをとる。
from collections import deque
N = int(input())
connection ={i:set() for i in range(1,N+1)}

for i in range(1,N):
    a,b = (int(i) for i in input().split())
    connection[a].add(b)
    connection[b].add(a)

#最小の色数
c =[]
for i in connection.values():
    c.append(len(i))
color_min =max(c)

#幅優先探索
start =1
color={i:0 for i in range(1,N+1)} #P:今の頂点と次への辺の色を記録(tuple)。
passed =set() # 通過した記録
dq =deque([start]) #スタートは1でいいのか？
color[start] =0
while len(dq) >0:
    now =dq.popleft()
    passed.add(now)
    c1 =color[now]
    for next in connection[now]:
        if next not in passed:
            c1 +=1
            c1 %=color_min
            color[next] =c1  #0 <=c <= color_min-1のため　＋１
            dq.append(next)
print(color_min)
for i in range(2,N+1):
    print(color[i] +1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
k = 0
data = [[] for _ in range(n)]
ans_index = []

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

q = deque([0])
color = [0] * n
print(data)
while q:
    cur = q.popleft()
    c = 1
    for x in data[cur]:
        if c == color[cur]:
            c += 1
    
        color[x] = c
        c += 1
        q.append(x)

print(max(color))
for i in ans_index:
    print(color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

dic = {i:[] for i in range(1,N+1)}

rlt = [0]*(N-1)

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

while h:
  j = 1
  c = 0
  t = h.popleft()
  for k in dic[t[0]]:
    if k[0] == t[1]:
      c = rlt[k[1]]
      break
  for k in dic[t[0]]:
    if k[0] == t[1]:
      continue
    if c == j:
      j += 1
    rlt[k[1]] = j
    h.append((k[0],t[0]))
    j += 1
      
for l in rlt:
  print(l)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

dic = {i:[] for i in range(1,N+1)}

rlt = [0]*(N-1)

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

while h:
  j = 1
  c = 0
  t = h.popleft()
  for k in dic[t[0]]:
    if k[0] == t[1]:
      c = rlt[k[1]]
      break
  for k in dic[t[0]]:
    if k[0] == t[1]:
      continue
    if c == j:
      j += 1
    rlt[k[1]] = j
    h.append((k[0],t[0]))
    j += 1
      
print(rlt)