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())
ab = []
ncolor = 0
for i in range(N-1):
    a,b = map(int,input().split())
    ab.append((a,b))
ab.sort()
ans  = [0]*(N-1)
color = [[0] for _ in range(N)]
for i in range(N-1):
    a,b = ab[i]
    if a == 1:
        ncolor = max(color[0])+1
        ans[i] = ncolor
        color[a-1].append(ncolor)
        color[b-1].append(ncolor)
    else:
        for j in range(1, 10**5):
            if j not in color[a-1]:
                ncolor = j
                break
        ans[i] = ncolor
        color[a-1].append(ncolor)
        color[b-1].append(ncolor)
print(max(ans))
for i in ans:
    print(i)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

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

tree=[[] for i in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

seen=set()
seen.add(0)

que=deque()
que.append(0)

ans_dict={}
while que:
  x=que.popleft()

  color_num=1
  for i in tree[x]:
    if i not in seen:
      seen.add(i)
      que.append(i)
      ans_dict[(x+1,i+1)]=color_num
      ans_dict[(i+1,x+1)]=color_num
      color_num+=1

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Submission status: Wrong Answer

Solution code:
n=int(input())

import sys
sys.setrecursionlimit(10 ** 7)

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

max_color=0
for graph_i in graph:
    max_color=max(max_color, len(graph_i))
print(max_color)

colors=[-1]*(n-1)

def dfs(v, color, pre):
    if color!=1:
        nc=0
    else:
        nc=1
    for e in graph[v]:
        # print(e,nc)
        if e[0]==pre:
            continue
        colors[e[1]]=nc
        dfs(e[0],nc,v)
        nc+=1
        if nc==color:
            nc+=1

dfs(0,-1,-1)

for c in colors:
    print(c+1)

Submission status: Wrong Answer

Solution code:
n=int(input())

import sys
sys.setrecursionlimit(10 ** 7)

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

max_color=0
for graph_i in graph:
    max_color=max(max_color, len(graph_i))
# print(max_color)

colors=[-1]*(n-1)

def dfs(v, color, pre):
    if color!=1:
        nc=0
    else:
        nc=1
    for e in graph[v]:
        # print(e,nc)
        if e[0]==pre:
            continue
        colors[e[1]]=nc
        dfs(e[0],nc,v)
        nc+=1
        if nc==color:
            nc+=1

dfs(0,-1,-1)

for c in colors:
    print(c+1)

Submission status: Wrong Answer

Solution code:
n=int(input())

import sys
sys.setrecursionlimit(10 ** 7)

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

max_color=0
for graph_i in graph:
    max_color=max(max_color, len(graph_i))
# print(max_color)

colors=[-1]*(n-1)

def dfs(v, color, pre):
    if color!=1:
        nc=0
    else:
        nc=1
    for e in graph[v]:
        # print(e,nc)
        if e[0]==pre:
            continue
        colors[e[1]]=nc
        dfs(e[0],nc,v)
        nc+=1
        if nc==color:
            nc+=1

dfs(0,-1,-1)

for c in colors:
    print(c+1)

Submission status: Wrong Answer

Solution code:

N = int(input())

S = [[0] * (N+1) for i in range(N+1)]
A = [[0] * (N+1) for i in range(N+1)]

C = []
for _ in range(N-1):
    a, b = map(int, input().split())
    S[a][b] = 1
    S[b][a] = 1
    s = 0
    while s in A[a]:
        s += 1
    A[a][b] = s
    A[b][a] = s
    C.append([a, b])
    

K = 0
for i in range(1, N+1):
    #print(S[i])
    K = max(K, sum(S[i]))
    
#print()
"""
for i in range(1, N+1):
    print(A[i])
    
print()
"""
print(K)

for i in range(N-1):
    print(A[C[i][0]][C[i][1]])

Submission status: Wrong Answer

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    al = [[] for _ in range(n)]
    e = [(-1, -1) for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = [int(j) - 1 for j in read().split()]
        al[a].append(b)
        al[b].append(a)
        e[i] = (a, b)
    k = max(map(len, al))
    print(k)
    c = [set() for _ in range(n)]
    for i in range(n - 1):
        a, b = e[i]
        for ci in range(1, k + 1):
            if ci not in c[a] and ci not in c[b]:
                print(ci)
                c[a].add(ci)
                c[b].add(ci)
                break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
K = 0
Ans = []
Color = [set([]) for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(1, N):
        if (i not in Color[a]) and (i not in Color[b]):
            Color[a].add(i)
            Color[b].add(i)
            Ans.append(i)
            K = max(K, i)
            break
print(K)
for a in Ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(idx,k,colored):
  q = deque()
  visited[idx] = True
  q.append(idx)
  while q:
    r = q.pop()
    c = set(graph[r].values())
    color = 0
    for n in graph[r].keys():
      if not visited[n]:
        if color == colored[r]: color+=1
        colored[n] = color
        graph[r][n] = color
        graph[n][r] = color
        color += 1

        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
colored = [0]*(N+1)
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k,colored)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    ver = graph[r].keys()
    col = graph[r].values()
    for n in set(ver):
      if not visited[n]:
        if color not in set(col):
          """graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k"""
        else:
          """color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k"""
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    ver = graph[r].keys()
    col = graph[r].values()
    for n in set(ver):
      if not visited[n]:
        """if color not in set(col):
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k"""
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())

graph = [[] for _ in range(n)]
edges = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edges[(a, b)] = i
    edges[(b, a)] = i

que = deque([0])
ans = [0] * (n - 1)
visited = [0] * n
visited[0] = 0
while que:
    a = que.popleft()
    c = 1
    for b in graph[a]:
        if not visited[b]:
            if visited[a] == c:
                c += 1
            visited[b] = c
            ans[edges[(a, b)]] = c
            c += 1
            que.append(b)

k = max(ans)
print(k)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())

graph = [[] for _ in range(n)]
edges = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    # graph[b].append(a)
    edges[(a, b)] = i
    # edges[(b, a)] = i

que = deque([0])
ans = [0] * (n - 1)
visited = [0] * n
visited[0] = 1
while que:
    a = que.popleft()
    c = 1
    for b in graph[a]:
        if not visited[b]:
            if visited[a] == c:
                c += 1
            visited[b] = c
            ans[edges[(a, b)]] = c
            c += 1
            que.append(b)

k = max(ans)
print(k)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node():
    def __init__(self,n):
        self.parent=[-1]*n
        self.son=[[]for i in range(n)]
        self.sonnum=[0]*n
        self.color=[None]*n
        self.candidateColor=[[]for i in range(n)]
    def addSon(self,y,x):#xの親をy
        self.parent[x]=y
        self.son[y].append(x)
        self.sonnum[y]+=1
    def getsonNum(self,x):
        return self.sonnum[x]
    def getparent(self,x):
        return self.parent[x]
    def getson(self,x):
        return self.son[x]
    def setColor(self,x,c):
        self.color[x]=c
        
n=int(input())
G=Node(n)
for i in range(n-1):
    a,b=map(int,input().split())
    G.addSon(a-1,b-1)
dp=[10**8]*n

dp[0]=G.getsonNum(0)
now=0
toVis=deque()
for son in G.getson(now):
    toVis.appendleft(son)
while len(toVis)>0:
    
    numpare=dp[now]

    #sonpre=G.getsonNum(now)
    now=toVis.popleft()
    son=G.getson(now)
    if len(son)==0:
        dp[now]=numpare
        continue
    for girl in son:
        toVis.appendleft(girl)
        dp[now]=1+G.getsonNum(now)
    #nece=sonpre+1
    #if nece>numpare:
     #   dp[now]=nece
    #else:
     #   dp[now]=numpare
max=0
G.setColor(0,0)
for i in range(n):
    if max<dp[i]:
        max=dp[i]
    son=G.getson(i)
    #print(i,":",son)
    c=G.color[i]
    count=1
    for j in son:
        if count==c:
            count+=1
        G.setColor(j,count)
        count+=1

print(max)
#print(dp)
for i in range(1,n):
    print(G.color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node():
    def __init__(self,n):
        self.parent=[-1]*n
        self.son=[[]for i in range(n)]
        self.sonnum=[0]*n
        self.color=[None]*n
        self.candidateColor=[[]for i in range(n)]
    def addSon(self,y,x):#xの親をy
        self.parent[x]=y
        self.son[y].append(x)
        self.sonnum[y]+=1
    def getsonNum(self,x):
        return self.sonnum[x]
    def getparent(self,x):
        return self.parent[x]
    def getson(self,x):
        return self.son[x]
    def setColor(self,x,c):
        self.color[x]=c
        
n=int(input())
G=Node(n)
for i in range(n-1):
    a,b=map(int,input().split())
    G.addSon(a-1,b-1)
dp=[10**8]*n

dp[0]=G.getsonNum(0)
now=0
toVis=deque()
for son in G.getson(now):
    toVis.appendleft(son)
while len(toVis)>0:
    
    numpare=dp[now]

    sonpre=G.getsonNum(now)
    now=toVis.popleft()
    son=G.getson(now)
    if len(son)==0:
        dp[now]=numpare
        continue
    for girl in son:
        toVis.appendleft(girl)
    nece=sonpre+1
    if nece>numpare:
        dp[now]=nece
    else:
        dp[now]=numpare
print(dp[-1])
G.setColor(0,0)
for i in range(n):
    son=G.getson(i)
    #print(i,":",son)
    c=G.color[i]
    count=1
    for j in son:
        if count==c:
            count+=1
        G.setColor(j,count)
        count+=1


for i in range(1,n):
    print(G.color[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node():
    def __init__(self,n):
        self.parent=[-1]*n
        self.son=[[]for i in range(n)]
        self.sonnum=[0]*n
        self.color=[None]*n
        self.candidateColor=[[]for i in range(n)]
    def addSon(self,y,x):#xの親をy
        self.parent[x]=y
        self.son[y].append(x)
        self.sonnum[y]+=1
    def getsonNum(self,x):
        return self.sonnum[x]
    def getparent(self,x):
        return self.parent[x]
    def getson(self,x):
        return self.son[x]
    def setColor(self,x,c):
        self.color[x]=c
        
n=int(input())
G=Node(n)
for i in range(n-1):
    a,b=map(int,input().split())
    G.addSon(a-1,b-1)
dp=[10**8]*n

dp[0]=G.getsonNum(0)
now=0
toVis=deque()
for son in G.getson(now):
    toVis.appendleft(son)
while len(toVis)>0:
    
    numpare=dp[now]

    sonpre=G.getsonNum(now)
    now=toVis.popleft()
    son=G.getson(now)
    if len(son)==0:
        dp[now]=numpare
        continue
    for girl in son:
        toVis.appendleft(girl)
    nece=sonpre+1
    if nece>numpare:
        dp[now]=nece
    else:
        dp[now]=numpare
print(dp[-1])
G.setColor(0,0)
for i in range(n):
    son=G.getson(i)
    #print(i,":",son)
    c=G.color[i]
    count=0
    for j in son:
        if count==c:
            count+=1
        G.setColor(j,count)
        count+=1


for i in range(1,n):
    print(G.color[i]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node():
    def __init__(self,n):
        self.parent=[-1]*n
        self.son=[[]for i in range(n)]
        self.sonnum=[0]*n
        self.color=[None]*n
        self.candidateColor=[[]for i in range(n)]
    def addSon(self,y,x):#xの親をy
        self.parent[x]=y
        self.son[y].append(x)
        self.sonnum[y]+=1
    def getsonNum(self,x):
        return self.sonnum[x]
    def getparent(self,x):
        return self.parent[x]
    def getson(self,x):
        return self.son[x]
    def setColor(self,x,c):
        self.color[x]=c
        
n=int(input())
G=Node(n)
for i in range(n-1):
    a,b=map(int,input().split())
    G.addSon(a-1,b-1)
dp=[10**8]*n

dp[0]=G.getsonNum(0)
now=0
toVis=deque()
for son in G.getson(now):
    toVis.appendleft(son)
while len(toVis)>0:
    
    numpare=dp[now]

    sonpre=G.getsonNum(now)
    now=toVis.popleft()
    son=G.getson(now)
    if len(son)==0:
        dp[now]=numpare
        continue
    for girl in son:
        toVis.appendleft(girl)
    nece=sonpre+1
    if nece>numpare:
        dp[now]=nece
    else:
        dp[now]=numpare
print(dp[-1])
G.setColor(0,0)
for i in range(n):
    son=G.getson(i)
    #print(i,":",son)
    c=G.color[i]
    print(c+1)
    count=0
    for j in son:
        if count==c:
            count+=1
        G.setColor(j,count)
        count+=1

Submission status: Wrong Answer

Solution code:
#problem1
from collections import deque
d=deque()
e=deque()
N=int(input())
graph=[[] for i in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
#頂点1からスタート
K=1
d.append(1)
visited=[False for i in range(N+1)]
color=[-1 for i in range(N+1)]
visited[1]=True
color[1]=-1

while d:
    while d:
        x=d.popleft()
        par_color=color[x]
        c=1
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                if c!=par_color:
                    color[node]=c
                    K=max(K,c)
                else:
                    c+=1
                    color[node]=c
                    K=max(K,c)
                e.append(node)
                c+=1
    if e:
        d=e
        e=deque()
A=max(color)
print(A)
for i in range(2,N+1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
#problem1
from collections import deque
d=deque()
e=deque()
N=int(input())
graph=[[] for i in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
#頂点1からスタート
K=1
d.append(1)
visited=[False for i in range(N+1)]
color=[-1 for i in range(N+1)]
visited[1]=True
color[1]=-1

while d:
    while d:
        x=d.popleft()
        par_color=color[x]
        c=1
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                if c!=par_color:
                    color[node]=c
                    c+=1
                    K=max(K,c)
                else:
                    c+=1
                    color[node]=c
                    c+=1
                    K=max(K,c)
                e.append(node)
    if e:
        d=e
        e=deque()
print(K-1)
for i in range(2,N+1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)
color_set = set(range(1, color_num + 1))
color = [set() for _ in range(N)]
for a, b in ablist:
    ac = color[a]
    bc = color[b]
    for ele in color_set:
        if ele not in (ac | bc):
            c = ele
            break
    ac.add(c)
    bc.add(c)
    print(c)

Submission status: Wrong Answer

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)
color = [[0]*N for _ in range(N)]
for a, b in ablist:
    ac = [color[a][edge] for edge in graph[a]]
    bc = [color[b][edge] for edge in graph[b]]
    c = max(max(ac), max(bc)) + 1
    color[a][b] = c
    color[b][a] = c
    print(c)

Submission status: Wrong Answer

Solution code:
def int_(num_str):
    return int(num_str) - 1

N = int(input())
graph = [[] for _ in range(N)]
ablist = [list(map(int_, input().split())) for _ in range(N-1)]
for a, b in ablist:
    graph[a].append(b)
    graph[b].append(a)
color_num = max([len(v) for v in graph])
print(color_num)
color = [[0]*N for _ in range(N)]
for a, b in ablist:
    ac = [color[a][edge] for edge in color[a]]
    bc = [color[b][edge] for edge in color[b]]
    c = max(max(ac), max(bc)) + 1
    color[a][b] = c
    color[b][a] = c
    print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
lis = [0 for i in range(N)]
store = [0 for i in range(N-1)]
store2 = [0 for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    store[i]=max(lis[a-1],lis[b-1])+1
    lis[a-1]=store[i]
    lis[b-1]=store[i]
    store2[a-1]+=1
    store2[b-1]+=1

print(max(store2))
ma = max(store2)
for i in range(N-1):
    tmp = store[i]%ma
    if tmp==0:
        tmp = ma
    print(tmp)

Submission status: Wrong Answer

Solution code:
N=int(input())
lis = [0 for i in range(N)]
store = [0 for i in range(N-1)]
store2 = [0 for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    store[i]=max(lis[a-1],lis[b-1])+1
    lis[a-1]=store[i]
    lis[b-1]=store[i]
    store2[a-1]+=1
    store2[b-1]+=1

print(max(store2))
for i in range(N-1):
    tmp = store[i]%max(store2)
    if tmp==0:
        tmp = max(store2)
    print(tmp)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
g = [[] for _ in range(n)]

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

q = deque([0])

chk = [False] * n
chk[0] = True

res = [0] * n

while q:
    x = q.popleft()
    cnt = 1
    for y in g[x]:
        if chk[y]:
            continue
        if res[x] == cnt:
            cnt += 1
        res[y] = cnt
        chk[y] = True
        cnt += 1
        q.append(y)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
g = [[] for _ in range(n)]

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

q = deque([0])

chk = [False] * n
chk[0] = True

res = [1] * n
res[0] = 0

while q:
    x = q.popleft()
    ng = res[x]
    cnt = 1
    for y in g[x]:
        if chk[y]:
            continue
        elif cnt == ng:
            cnt += 1
        res[y] = cnt
        chk[y] = True
        cnt += 1
        q.append(y)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import heapq
def main():
    N = int(input())
    graph = {}
    for i in range(1, N+1):
        graph[i] = set()
    ans_order = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
        ans_order.append((a, b))
    K = 0
    for i in range(1, N+1):
        K = max(K, len(graph[i]))
    available_colors = [i for i in range(1, K+1)]
    seen = [0 for _ in range(N)]
    seen[0] = 1
    ans = {i: {} for i in range(1, N+1)}
    que = deque([])
    que.append(1)
    grand_parents = deque([])
    while len(que) != 0:
        v = que.popleft()
        for node in graph[v]:
            if seen[node-1] == 1:continue
            seen[node-1] = 1
            col = heapq.heappop(available_colors)
            ans[v][node] = col
            grand_parents.append(v)
            que.append(node)
        if len(grand_parents) > 1:
            grand_parent = grand_parents.popleft()
            for parent in ans[grand_parent]:
                heapq.heappush(available_colors, ans[grand_parent][parent])
    print(K)
    for pair in ans_order:
        a, b = pair
        print(ans[a][b])
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    graph = {}
    for i in range(1, N+1):
        graph[i] = set()
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
    K = 0
    for i in range(1, N+1):
        K = max(K, len(graph[i]))
    colors = deque([i for i in range(1, K+1)])
    seen = [0 for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    que = deque([])
    que.append(1)
    while len(que) != 0:
        v = que.popleft()
        if v > 1:
            col = colors.popleft()
            ans[v-2] = col
            colors.append(col)
        for node in graph[v]:
            if seen[node-1] == 1:continue
            seen[node-1] = 1
            que.append(node)
    print(K)
    for color in ans:
        print(color)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    graph = {}
    for i in range(1, N+1):
        graph[i] = set()
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
    K = 0
    for i in range(1, N+1):
        K = max(K, len(graph[i]))
    colors = deque([i for i in range(1, K+1)])
    seen = [0 for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    que = deque([])
    que.append(1)
    while len(que) != 0:
        v = que.popleft()
        col = colors.popleft()
        if v-1 < N-1:
            ans[v-1] = col
        colors.append(col)
        for node in graph[v]:
            if seen[node-1] == 1:continue
            seen[node-1] = 1
            que.append(node)
    print(K)
    for color in ans:
        print(color)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b = ab[i]
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    index = -1
    MAX = 0
for i in range(N):
    li = tree[i]
    n = len(li)
    if n > MAX:
        MAX = n
        index = i
d = defaultdict(int)

def dfs(cur,parent,prevcolor):
    li = tree[cur]
    n = len(li)
    if n == 0:
        return
    for i in range(n):
        chi = li[i]
        if chi == parent:
            continue
        d[(cur,chi)] = (prevcolor+1+i)%MAX
        d[(chi,cur)] = (prevcolor+1+i)%MAX
        dfs(chi,cur,(prevcolor+1+i)%MAX)
dfs(index,-1,0)
print(MAX)
for i in range(N-1):
    a,b = ab[i]
    ans = d[(a-1,b-1)]+1
    print(ans)

Submission status: Wrong Answer

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)
col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k
        print(col[c]+1)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        par = [-1]*N
        while todo:
            u = todo.pop()
            k = 1
            c = edge[(par[u], u)] if u != 0 else 0
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                par[v] = u
                if u < v:
                    edge[(u, v)] = k
                else:
                    edge[(v, u)] = k
                k += 1
                if k == c:
                    k += 1
                    if max_g < k:
                        k = 1

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        par = [-1]*N
        while todo:
            u = todo.pop()
            k = 1
            c = edge[(par[u], u)] if u != 0 else 0
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                par[v] = u
                if u < v:
                    edge[(u, v)] = k
                else:
                    edge[(v, u)] = k
                k += 1
                if k == c:
                    k += 1

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()