Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:

from collections import deque

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

tree = [[] for _ in range(N + 1)]
for a, b in X:
    tree[a].append(b)
    tree[b].append(a)

color = [0] * (N + 1)
color[1] = 1
q = deque([1])
while q:
    u = q.popleft()
    c = 1
    for v in tree[u]:
        if color[v] > 0:
            continue

        if c == color[u]:
            c += 1
        color[v] = c
        c += 1
        q.append(v)

print(max(len(v) for v in tree))
print(*color[1:-1], sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

C=[0]*(N-1)
G=[set() for _ in range(N+1)]

T={i:False for i in range(1,N+1)}
T[2]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)

            p,q=min(v,w),max(v,w)
            c=1
            while c in G[p] or c in G[q]:
                c+=1
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)

print(max(C))
print("\n".join(map(str,C)))

Submission status: Wrong Answer

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

next_set = deque([(0,0)])
colors = [0]*(N-1)
while next_set:
    p, i = next_set.popleft()
    cnt = 1 if colors[i] != 1 else 2
    for q, j in edges[p]:
        if colors[j] != 0:
            continue
        colors[j] = cnt
        cnt += 1
        if cnt == i:
            cnt += 1
        next_set.append((q, j))
print(max(colors))
print(*colors, sep="\n")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if edge[i][v] == cnt:
          cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[] for i in range(n)]
done=[0 for i in range(n)]

dic={}
pair=[]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  dic[(a-1,b-1)]=0
  dic[(b-1,a-1)]=0
  pair.append([a-1,b-1])


def bfs():
  que=[0]
  done[0]=1

  while(que):
    now=que.pop(0)
    cnt=1
    for i in l[now]:

      if dic[(now,i)]==cnt:
        cnt+=1
        continue
       
      if done[i]!=0:
        continue

      que.append(i)
      dic[(now,i)]=cnt
      dic[(i,now)]=cnt
      done[i]=cnt
      cnt+=1

bfs()
ans=0
for a,b in pair:
  ans=max(ans,dic[a,b])

print(ans)
for a,b in pair:
  print(dic[a,b])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[] for i in range(n)]
done=[0 for i in range(n)]

dic={}
pair=[]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  dic[(a-1,b-1)]=0
  dic[(b-1,a-1)]=0
  pair.append([a-1,b-1])


def bfs():
  que=[0]
  done[0]=1
  
  while(que):
    now=que.pop(0)
    cnt=1
    for i in l[now]:

      if dic[(now,i)]==cnt:
        cnt+=1
        continue
       
      if cnt==done[i]:
        continue

      que.append(i)
      dic[(now,i)]=cnt
      dic[(i,now)]=cnt
      done[i]=cnt
      cnt+=1

bfs()
ans=0
for a,b in pair:
  ans=max(ans,dic[a,b])

print(ans)
for a,b in pair:
  print(dic[a,b])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
    k = 0
    for i in edge:
        k = max(k,len(i))
    color = [INF]*(n)
    d = [INF]*(n)
    d[0] = 0
    color[0] = k
    q = collections.deque([0])
    while q:
        p = q.popleft()
        now_color = color[p]
        if now_color == 1:
            get_color = 2
        else:
            get_color = 1
        for v in edge[p]:
            if d[v] == INF:
                q.append(v)
                d[v] = d[p] + 1
                color[v] = get_color
                if get_color == k:
                    get_color = 1
                else:
                    get_color+=1
    print(k)
    for i in range(1,n):
        print(color[i])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
    k = 0
    for i in edge:
        k = max(k,len(i))
    color = [INF]*(n)
    d = [INF]*(n)
    d[0] = 0
    color[0] = k
    q = collections.deque([0])
    while q:
        p = q.popleft()
        now_color = color[p]
        if now_color == 1:
            get_color = 2
        else:
            get_color = 1
        for v in edge[p]:
            if d[v] == INF:
                q.append(v)
                d[v] = d[p] + 1
                color[v] = get_color
                if get_color == k:
                    get_color = 1
                else:
                    get_color+=1
    for i in range(n):
        print(color[i])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
    k = 0
    for i in edge:
        k = max(k,len(i))
    color = [INF]*(n)
    d = [INF]*(n)
    d[0] = 0
    color[0] = k
    q = collections.deque([0])
    while q:
        p = q.popleft()
        now_color = color[p]
        for v in edge[p]:
            if d[v] == INF:
                q.append(v)
                d[v] = d[p] + 1
                if now_color == k:
                    now_color = 1
                else:
                    now_color+=1
                color[v] = now_color
    for i in range(n):
        print(color[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
'''
N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

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

for s, t in ST:
    for k in range(1, max(num[s-1], num[t-1])+1):
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
    rel[s-1].append(k)
    rel[t-1].append(k)
'''
from collections import deque

N = ii()
d = defaultdict(int)
ST = li2(N-1)
rel = [[] for _ in range(N)]
q = deque()

for s, t in ST:
    d[(s-1, t-1)] = -1
    rel[s-1].append(t-1)
    rel[t-1].append(s-1)

ind = (0, 0)

for i in range(N):
    if len(rel[i]) > ind[1]:
        ind = (i, len(rel[i]))

s = ind[0]
max_k = ind[1]
c = 1
for t in rel[s]:
    d[(min(s, t), max(s, t))] = c
    q.append((c, t))
    c += 1

while q != deque():
    cst = q.popleft()
    c, s = cst[0], cst[1]
    counter = 1
    for t in rel[s]:
        if d[(min(s, t), max(s, t))] == -1:
            color = (c + counter) % max_k
            d[(s, t)] = color
            counter += 1
            q.append((color, t))

print(ind[1])
for s, t in ST:
    if (d[(s-1, t-1)] + 1) % max_k == 0:
        print(max_k)
    else:
        print((d[(s-1, t-1)] + 1) % max_k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
'''
N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

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

for s, t in ST:
    for k in range(1, max(num[s-1], num[t-1])+1):
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
    rel[s-1].append(k)
    rel[t-1].append(k)
'''
from collections import deque

N = ii()
d = defaultdict(int)
ST = li2(N-1)
rel = [[] for _ in range(N)]
q = deque()

for s, t in ST:
    d[(s-1, t-1)] = 0
    rel[s-1].append(t-1)
    rel[t-1].append(s-1)

ind = (0, 0)

for i in range(N):
    if len(rel[i]) > ind[1]:
        ind = (i, len(rel[i]))

s = ind[0]
max_k = ind[1]
c = 1
for t in rel[s]:
    d[(min(s, t), max(s, t))] = c
    q.append((c, t))
    c += 1

while q != deque():
    cst = q.popleft()
    c, s = cst[0], cst[1]
    counter = 0
    for t in rel[s]:
        if d[(min(s, t), max(s, t))] == 0:
            color = (c + counter) % max_k + 1
            d[(s, t)] = color
            counter += 1
            q.append((color, t))

print(ind[1])
for s, t in ST:
    print(d[(s-1, t-1)])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

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

for s, t in ST:
    for k in range(1, max(num[s-1], num[t-1])+1):
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
    rel[s-1].append(k)
    rel[t-1].append(k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

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

k = max_k

for s, t in ST:
    for k in range(1, max(num[s-1], num[t-1])+1):
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
    rel[s-1].append(k)
    rel[t-1].append(k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
num = [0] * N
ST = li2(N-1)

for s, t in ST:
    num[s-1] += 1
    num[t-1] += 1

max_k = max(num)
print(max_k)

cnt = [1] * N
#for i in range(N):
    #count[i] = num[i]

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

for s, t in ST:
    k = max(num[s-1], num[t-1])
    while True:
        if (k not in rel[s-1]) and (k not in rel[t-1]):
            print(k)
            break
        k = (k - 1) % max_k
    num[s-1] -= 1
    num[t-1] -= 1 
    rel[s-1].append(k)
    rel[t-1].append(k)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col_adj = [[-1] for _ in range(n)]
col = [0]*(n-1)
col[0] = 1
visited = [0]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(not visited[next_v[1]]):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            visited[next_v[1]] = 1
            que.append(next_v)
print(max(col))
for i in col:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col = [0]*(n-1)
col[0] = 1
visited = [-1]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(visited[next_v[1]]==-1):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            visited[next_v[1]] = 1
            que.append(next_v)
print(max(col))
for i in col:
    print(i)

Submission status: Wrong Answer

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

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

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(nn[i])

Submission status: Wrong Answer

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

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

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(2,n+1):
    print(col[i])

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    g = {}
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append((b-1, i))
        g.setdefault(b-1, [])
        g[b-1].append((a-1, i))
        
    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        color = 1 if prevcol != 1 else 2
        for nxt, colidx in g[node]:
            if colors[colidx] is None:
                colors[colidx] = color
                nodes.append((color, nxt))
                color += 1 if prevcol != colidx+1 else 2

    print(maxdeg)
    for col in colors:
        print(col)
            
            




if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

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

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

m = max(map(len,l)) + 1

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]

for i in range(1,n+1):
    for la in l[i]:
        col[la] = co[i].pop()
        co[la].discard(col[la])
print(m)
for i in range(2,n+1):
    print(col[i])

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    g = {}
    edges = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [[None for _ in range(N)] for _ in range(N)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        #print(colors)
        #print(prev, node, prevcol)
        #print(cols)
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx] 
            if colors[node][nxt] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
            colors[node][nxt] = col
            colors[nxt][node] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for src, dst in edges:
        print(colors[src][dst])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
n = int(sys.stdin.readline())
G = [[] for _ in range(n)]
ans = dict()
ans_sort = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G[b].append(a)
    ans[str(a)+"_"+str(b)] = -1
    ans_sort.append(str(a)+"_"+str(b))

V = [-1]*n
que = deque([0])
V[0] = 0
C = set(list(range(1,n+1)))
while que:
    nw = que.popleft()
    c = 1
    for nx in G[nw]:
        if V[nx]!=-1: continue
        V[nx] = min(C-set([V[fr] for fr in G[nw]])-set([V[nw]]))
        ans[str(nw)+"_"+str(nx)] = V[nx]
        que.append(nx)

print(max(V))
for ab in ans_sort:
    print(ans[ab])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
n = int(sys.stdin.readline())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G[b].append(a)

C = set(list(range(1,n+1)))
V = [-1]*n
que = deque([0])
V[0] = 0
while que:
    nw = que.popleft()
    for nx in G[nw]:
        if V[nx]!=-1: continue
        V[nx] = min(C-set([V[fr] for fr in G[nw]])-set([V[nw]]))
        que.append(nx)

print(max(V))
for i in range(1,n):
    print(V[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
connect = defaultdict(list)
used_color = set()
node_has_color = defaultdict(set)
# 木構造生成
for a, b in ab:
    connect[a].append(b)

def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        target = queue.popleft()
        if not connect[target]:
            continue
        for dst in connect[target]:
            if not node_has_color[target]:
                node_has_color[target].add(1)
                node_has_color[dst].add(1)
                used_color.add(1)
                queue.append(dst)
            else:
                can_color = used_color - node_has_color[target]
                if not can_color:
                    tmp = max(used_color) + 1
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    used_color.add(tmp)
                    queue.append(dst)
                else:
                    lst = sorted(list(can_color))
                    node_has_color[target].add(lst[0])
                    node_has_color[dst].add(lst[0])
                    queue.append(dst)
                    

bfs(1)
print(len(used_color))
for a, b in ab:
    ans = list(set(node_has_color[a]) & set(node_has_color[b]))
    if len(ans) == 1:
        print(ans[0])
    else:
        ans.sort()
        print(ans[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
d = [0] * (N + 1)
for a, b in ab:
    d[a] += 1
    d[b] += 1
print(max(d))
for a, b in ab:
    print(max(d[a], d[b]))
    d[a] -= 1
    d[b] -= 1

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = []
color = [0] * (N + 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    color[a] += 1
    color[b] += 1
    ans.append(max(color[a], color[b]))
print(max(ans))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = []
color = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    for j, s in enumerate(color):
        if a not in s and b not in s:
            ans.append(j + 1)
            color[j].add(a)
            color[j].add(b)
            break
print(max(ans))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
connect = defaultdict(list)
used_color = set()
node_has_color = defaultdict(set)
# 木構造生成
for a, b in ab:
    connect[a].append(b)

def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        target = queue.popleft()
        if not connect[target]:
            continue
        for dst in connect[target]:
            if not node_has_color[target]:
                node_has_color[target].add(1)
                node_has_color[dst].add(1)
                used_color.add(1)
                queue.append(dst)
            else:
                can_color = used_color - node_has_color[target]
                if not can_color:
                    tmp = max(used_color) + 1
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    used_color.add(tmp)
                    queue.append(dst)
                else:
                    lst = list(can_color)
                    node_has_color[target].add(lst[0])
                    node_has_color[dst].add(lst[0])
                    queue.append(dst)

bfs(1)
print(len(used_color))
for a, b in ab:
    ans = list(set(node_has_color[a]) & set(node_has_color[b]))
    if len(ans) == 1:
        print(ans[0])
    else:
        ans.sort()
        print(ans[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
connect = defaultdict(list)
used_color = set()
node_has_color = defaultdict(set)
# 木構造生成
for a, b in ab:
    connect[a].append(b)

def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        target = queue.popleft()
        if not connect[target]:
            continue
        for dst in connect[target]:
            if not node_has_color[target]:
                node_has_color[target].add(1)
                node_has_color[dst].add(1)
                used_color.add(1)
                queue.append(dst)
            else:
                can_color = used_color - node_has_color[target]
                if not can_color:
                    tmp = max(used_color) + 1
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    used_color.add(tmp)
                    queue.append(dst)
                else:
                    lst = list(can_color)
                    node_has_color[target].add(lst[0])
                    node_has_color[dst].add(lst[0])
                    queue.append(dst)

bfs(1)
print(len(used_color))
for a, b in ab:
    ans = list(set(node_has_color[a]) & set(node_has_color[b]))
    if len(ans) == 1:
        print(ans[0])
    else:
        print(ans[1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
connect = defaultdict(list)
used_color = set()
node_has_color = defaultdict(set)
# 木構造生成
for a, b in ab:
    connect[a].append(b)

def ans(start):
    queue = deque()
    queue.append(start)
    while queue:
        target = queue.popleft()
        if not connect[target]:
            continue
        for dst in connect[target]:
            if not node_has_color[target]:
                print(1)
                node_has_color[target].add(1)
                node_has_color[dst].add(1)
                used_color.add(1)
                queue.append(dst)
            else:
                can_color = used_color - node_has_color[target]
                if not can_color:
                    tmp = max(used_color) + 1
                    print(tmp)
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    used_color.add(tmp)
                    queue.append(dst)
                else:
                    lst = list(can_color)
                    tmp = lst[0]
                    print(tmp)
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    queue.append(dst)

def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        target = queue.popleft()
        if not connect[target]:
            continue
        for dst in connect[target]:
            if not node_has_color[target]:
                node_has_color[target].add(1)
                node_has_color[dst].add(1)
                used_color.add(1)
                queue.append(dst)
            else:
                can_color = used_color - node_has_color[target]
                if not can_color:
                    tmp = max(used_color) + 1
                    node_has_color[target].add(tmp)
                    node_has_color[dst].add(tmp)
                    used_color.add(tmp)
                    queue.append(dst)
                else:
                    lst = list(can_color)
                    node_has_color[target].add(lst[0])
                    node_has_color[dst].add(lst[0])
                    queue.append(dst)

bfs(1)
print(len(used_color))
used_color = set()
node_has_color = defaultdict(set)
ans(1)