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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=mxd-1
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=mxd-1
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col and c!=x:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Wrong Answer

Solution code:
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex==0)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
k = max(map(len, con))
print(k)
for a, b in zip(*[iter(L)] * 2):
	print((label[a - 1] + label[b - 1]) % (k + 1))

Submission status: Wrong Answer

Solution code:
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex==0)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
k = max(label) + 1
print(k)
for a, b in zip(*[iter(L)] * 2):
	print((label[a - 1] + label[b - 1]) % (k + 1))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=inf
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col and c!=x:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            try: 
                if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                    tmp_color += 1
                colors[edge[1]] = tmp_color
                paint(edge[0], edge[1])
            except Exception as e:
                print(0)
                exit(0)
            tmp_color += 1

    

paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())

edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append(i)
    edges[to].append(i)

edges.sort(key=lambda A: len(A), reverse=True)
ans = [-1] * (N - 1)
for es in edges:
    canUse = set(range(1, len(es) + 1))
    for i in es:
        if ans[i] in canUse:
            canUse.remove(ans[i])
    canUse = list(canUse)
    for i in es:
        if ans[i] == -1:
            ans[i] = canUse.pop()

print(max(ans))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque


N = int(input())
branch = [[0] + list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
branch_color = [0] * (N - 1)
vertex = [False] * N


def bfs():
    max_color = 0
    q = deque()
    v = 0
    bc = 0
    q.append((v, bc))

    while len(q):
        v, bc = q.popleft()
        vertex[v] = True
        b_list = [c for c in branch if v in c[1:]]

        color = 1
        for c in b_list:
            if color == bc:
                color += 1
            if (c[0] == 0):
                c[0] = color
                color += 1

        max_color = max(max_color - 1, color)

        for c in b_list:
            nv = c[1] if c[2] == v else c[2]
            if vertex[nv] is False:
                q.append((nv, c[0]))
    
    return max_color


print(bfs())
for b in branch:
    print(b[0])

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = []
for i in range(n-1):
    x,y = map(int,input().split())
    edge.append((x,y))

e = sorted(edge)
ex = []
for i in range(n):
    ex.append(set())

colors = dict()
count = [0]*n
num_color = 0
for l,r in e:
    count[l-1] += 1
    count[r-1] += 1
    cand = 1
    while cand in ex[l-1] or cand in ex[r-1]:
        cand += 1
    ex[l-1].add(cand)
    ex[r-1].add(cand)
    colors[(l,r)] = cand
print(max(count))
for a in e:
    print(colors[a])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=mxd
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
e = []
for i in range(n-1):
    x,y = map(int,input().split())
    e.append((x,y))

e.sort()
ex = []
for i in range(n):
    ex.append(set())

colors = dict()
count = [0]*n
num_color = 0
for l,r in e:
    count[l-1] += 1
    count[r-1] += 1
    cand = 1
    while cand in ex[l-1] or cand in ex[r-1]:
        cand += 1
    ex[l-1].add(cand)
    ex[r-1].add(cand)
    colors[(l,r)] = cand
print(max(count))
for edge in e:
    print(colors[edge])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=inf
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())

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


ans = [[0 for _ in range(n)] for __ in range(n)]
visited = [False]*n

q = deque([(0,0)])
visited[0] = True

mx = 0
while q:
    key,v = q.popleft()
    i = 1
    for x in edges[v]:
        if not visited[x]:
            if key != i:
                visited[x] = True
                ans[v][x] = i
                ans[x][v] = i
                q.append((i,x))
                mx = max(mx,i)
                i += 1
            else:
                visited[x] = True
                i += 1
                ans[v][x] = i
                ans[x][v] = i
                mx = max(mx,i)
                i += 1
                q.append((i,x))

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

Submission status: Wrong Answer

Solution code:
# import sys
MOD = 10 ** 9 + 7
# input = sys.stdin.readline
import math


# import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def kingaku(a, b, n):
    keta = len(str(n))
    return a * n + b * keta


def main():
    #    h,w,a,b = map(int, input().split())
    n = int(input())
    b = [[] for i in range(n)]
    c = [[0 for j in range(n)] for i in range(n)]
    d = []
    for i in range(n - 1):
        x, y = map(int, input().split())
        c[x - 1][y - 1] = -1
        c[y - 1][x - 1] = -1
        b[x-1].append(y-1)
        b[y-1].append(x-1)
        d.append([x, y])
    #    print(c)

    for i in range(n):
        temp = []
        for j in b[i]:
            if c[i][j] == -1:
                for l in range(1, n):
                    if l not in temp:
                        c[i][j] = l
                        c[j][i] = l
                        temp.append(l)
                        break
            elif c[i][j] != 0:
                temp.append(c[i][j])
    #    print(c)
    e = []
    for i in range(n):
        e.append(max(c[i]))
    print(max(e))
    for i in range(n - 1):
        print(c[d[i][0] - 1][d[i][1] - 1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5 + 10)

N = int(input())

branch = [[0] + list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
branch_color = [0] * (N - 1)
vertex = [False] * N


def bfs():
    q = deque()
    v = 0
    bc = 0
    q.append((v, bc))

    while len(q):
        v, bc = q.popleft()
        vertex[v] = True
        b_list = [c for c in branch if v in c[1:]]

        color = 1
        for c in b_list:
            if color == bc:
                color += 1
            if (c[0] == 0):
                c[0] = color
                color += 1

        for c in b_list:
            nv = c[1] if c[2] == v else c[2]
            if vertex[nv] is False:
                q.append((nv, c[0]))


bfs()
for b in branch:
    print(b[0])

Submission status: Wrong Answer

Solution code:
N=int(input())
li=[list(map(int,input().split())) for _ in range(N-1)]
tanten=[0]*N
tanten2=[0]*N
for i in range(N-1):
  tanten[li[i][0]-1]+=1
  tanten2[li[i][1]-1]+=1
c=[x+y for (x, y) in zip(tanten, tanten2)]
print(max(c))
for j in range(N-1):
  if c[tanten[j]]>0:
    print(c[tanten[j]])
    c[tanten[j]]-=1
  else:
    print(c[tanten2[j]])
    c[tanten2[j]]-=1

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=v[col]
                dc[(c,i)]=col
                col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
e = []
for i in range(n-1):
    x,y = map(int,input().split())
    e.append((x,y))

e.sort()
ex = []
for i in range(n):
    ex.append(set())

colors = []
count = [0]*n
num_color = 0
for l,r in e:
    count[l-1] += 1
    count[r-1] += 1
    cand = 1
    while cand in ex[l-1] or cand in ex[r-1]:
        cand += 1
    ex[l-1].add(cand)
    ex[r-1].add(cand)
    colors.append(cand)
print(max(count))
for c in colors:
    print(c)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def main():
#    h,w,a,b = map(int, input().split())
    n=int(input())
    b = [[] for i in range(n)]
    c = [[] for i in range(n)]
    d=[]
    e = [[0 for i in range(n)] for j in range(n)]
    for i in range(n-1):
        x,y=map(int,input().split())
        c[x-1].append(y)
        c[y-1].append(x)
        d.append([x,y])
 #   print(c,d)
#    print(e)

    for i in range(n-1):
        temp=[]
        for j in c[i]:
            if e[i][j-1]!=0:
                temp.append(e[i][j-1])
            else:
                for l in range(1,n-1):
                    if l not in temp:
                        e[i][j-1]=l
                        e[j-1][i]=l
                        temp.append(l)
                        break
#    print(e)
    f=[]
    for i in range(n):
        f.append(max(e[i]))
    print(max(f))
    for i in range(n-1):
        print(e[d[i][0]-1][d[i][1]-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	pp_list=[]
	for i in range(n-1):
		a, b = map(int, input().split())
		if b < a:
			a,b = b,a
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
		pp_list.append([a,b,i])
	
	bb=max([len(t) for t in ttt])
	
	print(bb)
	
	ret_ll=[0]*(n-1)
	count_st=[0]*n
	ss_stack=[(0,-1, bb+1)]
	#state, parent, parent_path_color
	while len(ss_stack)>0:
		st, parent, pp_color = ss_stack.pop()
		
		pp_flag=0
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to==parent:
				pp_flag=1
				continue
			
			c_color = i + 1 + (1 if i >= pp_color else 0) - pp_flag
			
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [set() for _ in range(N+1)]

    for i in range(N-1):
        h[a[i]].add(i)
        h[b[i]].add(i)

    max_color = 0
    for hh in h:
        max_color = max(len(hh),max_color)
    color = list(range(1,max_color+1))

    # colorList[i]が辺iのいろ
    colorList = [0]*(N-1)

    h.sort(key=lambda x: -len(x))
    for i in range(0,N):
        color_index = 0
        cur = [colorList[b] for b in h[i] if colorList[b]>0] ##塗ってある色リスト
        for hh in h[i]:
            if i == 0:
                colorList[hh] = color[color_index]
                color_index+=1
            if colorList[hh] > 0: 
                continue
            else:            
                while color[color_index] in cur:
                    color_index+=1

                colorList[hh] = color[color_index]

    print(max_color)
    for c in colorList:
        print(c)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[c]==col:col+=1
            if v[i]==-1:
                p.append(i)
                v[i]=v[col]
                dc[(c,i)]=col
            col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)

Submission status: Wrong Answer

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


_n = int(input())
_edges = [list(map(int, input().split())) for _ in range(0, _n - 1)]


def chker(n, edges):
    fe = [item for edge in edges for item in edge]
    c = collections.Counter(fe)
    print(c.most_common()[0][1])

    cnts = [0] * n
    for n1, n2 in edges:
        cnts[n1 - 1] += 1
        cnts[n2 - 1] += 1

        print(cnts[n1 - 1])


chker(_n, _edges)

Submission status: Wrong Answer

Solution code:
N = int(input())
a=[]
b=[]
counts = [0 for i in range(N)]
colors = [[0] for i in range(N)]
K=[0 for i in range(N-1)]
for i in range(N-1):
    s = input().split(" ")
    a.append(int(s[0]))
    b.append(int(s[1]))

for i in range(N-1):
    counts[a[i]-1] += 1
    counts[b[i]-1] += 1

M = max(counts)
flag = True
for i in range(N-1):
    flag = True
    for j in range(1,M+1):
        if (not j in colors[a[i]-1]) and (not j in colors[b[i]-1]) and flag:
            colors[a[i]-1].append(j)
            colors[b[i]-1].append(j)
            K[i] = j
            flag = False
print(M)
for i in range(N-1):
    print(K[i])

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	pp_list=[]
	for i in range(n-1):
		a, b = map(int, input().split())
		if b < a:
			a,b = b,a
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
		pp_list.append([a,b,i])
	
	bb=max([len(t) for t in ttt])
	
	print(bb)
	
	ret_ll=[0]*(n-1)
	count_st=[0]*n
	ss_stack=[(0,-1, bb+1)]
	#state, parent, parent_path_color
	while len(ss_stack)>0:
		st, parent, pp_color = ss_stack.pop()
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to==parent:
				continue
			
			c_color = i + 1 + (1 if i >= pp_color else 0)
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
N=int(input())
li=[list(map(int,input().split())) for _ in range(N-1)]
tanten=[0]*N
tanten2=[0]*N
for i in range(N-1):
  tanten[li[i][0]-1]+=1
  tanten2[li[i][1]-1]+=1
c=[x+y for (x, y) in zip(tanten, tanten2)]
print(max(c))
for i in range(N-1):
  print(tanten[c[i]]+1)

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())

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

eda = [set() for i in range(N)]

for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda) == max_e:
        id = i

ans = [1]*(N-1)
q = collections.deque()
q.append(id)
print(max_e)
eda2 = [set() for i in range(N)]
for a, b in ab:
    for i in range(1, max_e+1):
        if i not in eda2[a-1] and i not in eda2[b-1]:
            ans = i
            break
    print(ans)
    eda2[a-1].add(i)
    eda2[b-1].add(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[]
d={}
s=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  d[min(a,b)*1000000+max(a,b)]=0
  r.append((a,b))
  s[a-1].append(b-1)
  s[b-1].append(a-1)
Q=[(0,i)for i in s[0]]
co=[10**6]*n
while Q:
  P=[]
  j=0
  for i in range(len(Q)):
    a,b=Q[i]
    j+=1
    if j==co[a]:j+=1
    d[min(a+1,b+1)*1000000+max(a+1,b+1)]=j
    co[b]=j
    for ii in s[b]:
      if a!=ii:P.append((b,ii))
  Q=P.copy()
print(max(len(s[i])for i in range(n)))
for a,b in r:print(d[min(a,b)*1000000+max(a,b)])

Submission status: Wrong Answer

Solution code:
N = int(input())
a=[]
b=[]
counts = [0 for i in range(N)]
colors = [[0] for i in range(N)]
K=[0 for i in range(N-1)]
for i in range(N-1):
    s = input().split(" ")
    a.append(int(s[0]))
    b.append(int(s[1]))

for i in range(N-1):
    counts[a[i]-1] += 1
    counts[b[i]-1] += 1

M = max(counts)
flag = True
for i in range(N-1):
    flag = True
    for j in range(1,M+1):
        if (not j in colors[a[i]-1]) and (not j in colors[b[i]-1]) and flag:
            colors[a[i]-1].append(j)
            colors[b[i]-1].append(j)
            K[i] = j
            flag = False
            
for i in range(N-1):
    print(K[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

if __name__ == "__main__":
	N = int(input())
	AB = []
	for _ in range(N - 1):
		a, b = map(int, input().split())
		AB.append((a, b))

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

	root = 1
	parent = [0] * (N + 1)
	order = []
	Stack = deque()
	# make ordered tree
	while Stack:
		x = Stack.pop()
		order.append(x)
		for y in graph[x]:
			if parent[x] == y:
				continue
			parent[y] = x
			Stack.append(y)

	# assign color
	color = [-1] * (N + 1)
	for x in order:
		ng = color[x] # cannot assign the color of edge(x, parent[x])
		c = 1
		for y in graph[x]:
			if parent[x] == y:
				continue
			if c == ng:
				c += 1
			color[y] = c
			c += 1

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
E_n = {k: 0 for k in ab}
for i in range(1,N+1):
    items = {k:v for k,v in E_n.items() if i in k}
    c = 1
    if reduce(mul, items.values()) == 0:
      for k in items.keys():
        if items[k] != 0: continue
        while True:
          if c not in items.values():
            items[k] = c
            break
          else: c += 1
      for k,v in items.items(): E_n[k] = v
    if reduce(mul, E_n.values()) != 0: break

print(len(set(E_n.values())))
for k in sorted(E_n.keys()): print(E_n[k])