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())
dp = [0] * n
a, b = map(int, input().split())
dp[a - 1] = 1
dp[b - 1] = 1

ans = list()
ans.append(1)
for i in range(1, n - 1):
    a, b = map(int, input().split())
    dp[a - 1] += 1
    dp[b - 1] += 1
    ans.append(max(dp[a - 1], dp[b - 1]))

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = [[] for i in range(N+2)]
    for i in range(N-1):
        g[a[i]].append(b[i])
        g[b[i]].append(a[i])

    gc = [len(i) for i in g]
    k = max(gc)
    
    ans = []
    for i in range(N-1):
        # print(gc, gc[a[i]])
        ans.append(gc[a[i]])
        gc[a[i]] -= 1
        gc[b[i]] -= 1

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



    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:
import collections
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
a = []
b = []
for i in range(N-1):
    a.append(ab[i][0])
for i in range(N-1):
    b.append(ab[i][1])
    
ab_max = []
for i in range(N-1):
    ab_max.append(a[i])
    ab_max.append(b[i])
c = collections.Counter(ab_max)    
    
ans = max(c.values())

print(ans)

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

for i in range(N-1):
    print(ans - max(ndic[a[i]], ndic[b[i]]))
    ndic[a[i]] += 1
    ndic[b[i]] += 1

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 
def findCol(d,x,y,c):
	for i in range(1,c+1):
		if i not in d[x] and i not in d[y]:
			d[x].append(i)
			d[y].append(i)
			return i

n = int(input())
d = [0]*(n+1)
E = []
for i in range(n-1):
	x,y = map(int,input().split())
	E.append([x,y])
	d[x]+=1
	d[y]+=1
c = 0
c = max(d)
print(c)
od = defaultdict(list) 
for e in E:
	col = findCol(od,e[0],e[1],c)
	print(col)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    to=defaultdict(list)
    n=int(input())
    etoi={}
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append(b)
        to[b].append(a)
        etoi[(a,b)]=etoi[(b,a)]=i
    #print(etoi)
    color=[-1]*(n-1)
    deg_u=[[len(vv),u] for u,vv in to.items()]
    deg_u.sort()
    #print(deg_u)

    while deg_u:
        _,u=deg_u.pop()
        used=set()
        for v in to[u]:
            i=etoi[(u, v)]
            c=color[i]
            if c==-1:continue
            used.add(c)
        c=1
        for v in to[u]:
            i=etoi[(u, v)]
            if color[i]!=-1:continue
            while c in used:
                c+=1
            color[i]=c
            c+=1
    #print(color)
    print(max(color))
    print(*color,sep="\n")

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    v = -1
    for k in g:
        if len(g[k]) == 1:
            v = k
            break
    
    s = [(v, -1)]
    done = set([v])
    K = 0
    ans = {}
    while s:
        u, c = s.pop()
        used = set([c])
        c = 1
        for v in g[u]:
            if v in done:
                continue
            while c in used:
                c += 1 
                K = max(K, c)
            used.add(c)
            s.append((v, c))
            i, j = min(u, v), max(u, v)
            ans[(i, j)] = c
            done.add(v)
    print(K)
    for a, b in AB:
        print(ans[(a, b)])
    # return ans


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
b = []
L = [0]*N
D = [4]*N
output = [0]*(N-1)
for i in range(N-1):
    [atemp,btemp] = list(map(int,input().split()))
    a.append(atemp)
    b.append(btemp)

for j in range(N-1):
    L[a[j]-1]+=1
    L[b[j]-1]+=1
K = max(L)

D = [K]*(N)

for j in range(N-1):
    output[j]=min(D[a[j]-1],D[b[j]-1])
    D[a[j]-1]-=1
    D[b[j]-1]-=1

print(K)
for out in output:
    print(out)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
es = [[] for _ in range(n + 1)]
counter = [0 for _ in range(n + 1)]
for _ in range(n - 1):
	a, b = list(map(int, input().split()))
	es[a].append(b)
	counter[a] += 1
	counter[b] += 1

#print(counter)
max_e = collections.Counter(counter).most_common()[0][1]
colors = [0 for _ in range(n + 1)]
colors[1] = 1


nums = [i + 1 for i in range(max_e)] * 2

# print(max_e)
# print(es)
# print(nums)

for i in range(1, n + 1):
	#print(colors)
	j = nums.index(colors[i])
	for e in es[i]:
		j += 1
		colors[e] = nums[j]

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

Submission status: Wrong Answer

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
K = d[-1][1]
ans = [None] * (N - 1)
while d:
    p, _ = d.pop()
    L = 1
    used = set()
    for i in s[p]:
        if ans[i] is None:
            while L in used:
                L += 1
            ans[i] = L
        used.add(ans[i])
        assert L <= K
print(K)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n=int(input())

ans=[]
inp_list=[]
G=[0 for i in range(n+1)]
T=[0 for i in range(n+1)]
for i in range(n-1):
    #print(G)
    a,b=map(int,input().split())
    jud=max(G[a],G[b])+1
    ans.append(jud)
    G[a]=jud
    G[b]=jud
    T[a]+=1
    T[b]+=1

mod=max(T)
print(max(T))
for o in range(n-1):
    outp=ans[o] % mod
    if outp==0:
        outp=mod
    print(outp)

Submission status: Wrong Answer

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

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))

print(edges)

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

q = [0]
visit = [False] * n
visit[0] = True

while q:
    l = q.pop(-1)
    li = []
    for i,j in edges[l]:
        if not visit[i]:
            q.append(i)
            visit[i] = True
        li.append(j)
    li = list(set(li))
    li2 = []
    for i in li:
        li2.append(ans[i])
    li2.sort()
    if li2[0] == -1:
        li2 = li2[1:]
    count = 1
    for i in li:
        while ans[i] == -1:
            if count not in li2:
                ans[i] = count
            count += 1

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

Submission status: Wrong Answer

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

nodes = [[] for _ in range(N)]
for a, b in ab:
  nodes[a-1].append(b-1)
  nodes[b-1].append(a-1)

used = [set() for _ in range(N)]
K = max(len(nodes[i]) for i in range(N))
print(K)
for a, b in ab:
  for i in range(1, K + 1):
    if (i not in used[a - 1]) and (i not in used[b - 1]):
      print(i)
      used[a - 1].add(i)
      used[b - 1].add(i)
      break

Submission status: Wrong Answer

Solution code:
N = int(input())
ABs = []
for i in range(N - 1):
    ABs.append(tuple(map(int, input().split())))

Cs = [0] * (N + 1)
for i in range(N - 1):
    Cs[ABs[i][0]] += 1
    Cs[ABs[i][1]] += 1
K = max(Cs)
print(K)

ABsc = [[False] * (K + 1) for _ in range(N + 1)]


def minC(i):
    for j in range(1, K + 1):
        if not ABsc[i][j]:
            return j


for i in range(N - 1):
    c = max(minC(ABs[i][0]), minC(ABs[i][1]))
    print(c)
    ABsc[ABs[i][0]][c] = True
    ABsc[ABs[i][1]][c] = True

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N+1)] #graph[0]は使わない
edges = [list(map(int, input().split())) for _ in range(N-1)]

for i in range(N-1):
    a, b = edges[i]
    graph[a].append(b)
    graph[b].append(a)

colors = 1

#colorsの数は決定
#print(colors)

used = [set() for i in range(N+1)]
answer = []

for a, b in edges:
    cur = 1
    while cur in used[a] or cur in used[b]:
        cur += 1
    answer.append(cur)
    used[a].add(cur)
    used[b].add(cur)

print(max(answer))
for i in range(N-1):
    print(answer[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#str 注意
def main():
    n = int(input())

    ans = [0 for _ in range(n)]
    ls = []
    for _ in range(n-1):
        a,b = map(int,input().split())
        ls.append([a-1,b-1])
        ans[a-1]+= 1
        ans[b-1]+= 1
    
    cnt = 0
    for i in ans:
        if i==1:
            cnt+=1
        else:
            pass
    print(ans.count(1))
    j = 1
    for ls_ in ls:
        if ans[ls_[0]]==1 or ans[ls_[1]]==1:
            print(j)
            j +=1
        else:
            print(j)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
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())
import bisect
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    else:
        return False
#index(lst, 12)  # False
lists=[0 for i in range(n-1)]
for i in range(n-1):
    A=list(map(int,input().split()))
    a=A[0]
    b=A[1]    
    lists[i]=(a,b)
counter=[0 for i in range(n+1)]
for some in lists:
    a=some[0]
    b=some[1]
    counter[a]+=1
    counter[b]+=1
uselist=[]
for j in range(1,n+1):
    if counter[j]==1:
        uselist.append(j)
uselist=sorted(uselist)
anslist=[]
counter=0
for i in range(n-1):
    a,b=lists[i][0],lists[i][1]
    if index(uselist,a) or index(uselist,b):
        counter+=1
        anslist.append(counter)
    else:
        anslist.append(1)
print(counter)
for some in anslist:
    print(some)

Submission status: Wrong Answer

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

n = int(input())
edge = []
tree = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a] += 1
    tree[b] += 1
    edge.append((a, b))

degree_max = max(tree)
color = [set() for _ in range(n)]
print(degree_max)
for a, b in edge:
    for c in range(degree_max):
        if c not in color[a] and c not in color[b]:
            color[a].add(c)
            color[b].add(c)
            print(c + 1)
            break

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]
cnt = [0] * (N + 1)

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

color = [0] * (N + 1)
root = cnt.index(1)
queue = deque([root])
color[root] = 1

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if color[v] == 0:
            while number == color[V]:
                number += 1
            color[v] = number
            queue.append(v)

print(max(color))
print('\n'.join(map(str, color[1:-1])))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.buffer.readline())

neighbor = [[] for _ in range(N)]
edge = []
for _ in range(N-1):
    a, b = map(int, sys.stdin.buffer.readline().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)
    edge.append([min(a-1, b-1), max(a-1, b-1)])

edge = sorted(edge, key=lambda x:x[0])
K = len(max(neighbor, key=len))
print(K)
color = [set(range(1,K+1)) for _ in range(N)]

for x in edge:
    c = (color[x[0]] & color[x[1]]).pop()
    print(c)
    color[x[0]].remove(c)
    color[x[1]].remove(c)

Submission status: Wrong Answer

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
K = d[-1][1]
ans = [None] * (N - 1)
while d:
    p, _ = d.pop()
    L = 1
    used = set()
    for i in s[p]:
        if ans[i] is None:
            while L in used:
                L += 1
            ans[i] = L
        used.add(ans[i])
print(K)
print('\n'.join(map(str, ans)))
assert None not in ans

Submission status: Wrong Answer

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
rec = []
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
  rec.append([a,b])
can = []
for i in range(n):
  can.append(len(peer[i]))
#print(peer)
#print(can)
ans = max(can)
now = [0]
clr = [0 for _ in range(n)]
ok = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
clr[0] = 1
ok[0] = 2
r = 0
while now:
  r += 1
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y] == 0:
        now.append(y)
        clr[y] = ok[x]
        rank[y] = r
        ok[x] = ok[x] % ans + 1
        ok[y] = clr[y] % ans + 1
print(ans)
#print(clr)
for w in rec:
  a,b = w
  if rank[a] > rank[b]:
    m = a
  else:
    m = b
  print(clr[m])
#print(rank)

Submission status: Wrong Answer

Solution code:
N = int(input())

G = [[] for _ in range(N)]
AB = []
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)
    AB.append([a, b])

K = max([len(g) for g in G])
print(K)

for a, b in AB:
    if len(G[a]) > len(G[b]):
        print(G[a].index(b) + 1)
    else:
        print(G[b].index(a) + 1)

Submission status: Wrong Answer

Solution code:
import sys #追加
sys.setrecursionlimit(10**9) #追加

n = int(input())

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

m_node = 0
for e in nodes:
    m_node = max(len(e), m_node)

use_node = [0 for i in range(n)]
dic = {}
def dfs(node, start_color):
    use_node[node] = 1
    for e in nodes[node]:
        if use_node[e] == 0:
            dic[(node,e)] = (start_color%m_node)+1
            dic[(e,node)] = (start_color%m_node)+1
            dfs(e, (start_color%m_node)+1)
            start_color += 1

dfs(0,0)

for a,b in abl:
    print(dic[(a-1,b-1)])

Submission status: Wrong Answer

Solution code:
N=int(input())

L=[{}for i in range(N+1)]
ans=[]
for i in range(N-1):
    a,b=map(int,input().split())
    for j in range(1,N):
        if j not in L[a] and j not in L[b]:
            L[a][j]=1
            L[b][j]=1
            ans.append(j)
            break
print(max(ans))
for i in range(N-1):
    print(ans[i])
#print(L)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[{} for _ in range(n+1)]
ans=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    c=1
    while True:
        if c not in l[a] and c not in l[b]:
            ans.append(c)
            l[a][c]=1
            l[b][c]=1
            break
        else:
            c+=1
print(max(ans))
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import time
t1=time.time()
n=int(input())
kind=[0]*n
aa=[]
bb=[]
for _ in range(n-1):
	a,b=map(int,input().split())
	aa.append(a)
	bb.append(b)
	kind[a-1]+=1
	kind[b-1]+=1
print(max(kind))
p=[[set()]for _ in range(n)]
for i in range(n-1):
	t2=time.time()
	if t2-t1<=0.5:
		for j in range(max(kind),0,-1):
			if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
				p[aa[i]-1][0].add(j)
				p[bb[i]-1][0].add(j)
				print(j)
				break
	else:
		for j in range(1,max(kind)+1):
			if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
				p[aa[i]-1][0].add(j)
				p[bb[i]-1][0].add(j)
				print(j)
				break

Submission status: Wrong Answer

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

t=[0 for _ in range(n)]
for a,b in ab:
	t[a-1]+=1
	t[b-1]+=1
k=max(t)

print(k)

x=[[] for _ in range(n)]
for i in range(n-1):
	a=ab[i][0]
	b=ab[i][1]
	for t in range(1,k+1):
		if t not in x[a-1] and t not in x[b-1]:
			x[a-1].append(t)
			x[b-1].append(t)
			break
	#print(x)
	print(t)

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
V = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
for i, e in enumerate(E):
  a, b = e
  c = 1
  while c in V[a]:
    c += 1
  V[a].append(c)
  V[b].append(c)
  V[a] = list(set(V[a]))
  V[b] = list(set(V[b]))
  ans[i] = c
print(len(set(ans)))
for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
nl = [[] for _ in range(N + 1)]
max_node = -1
i = 0
for a, b in [tuple(map(int, input().split())) for _ in range(N - 1)]:
    nl[a].append((b, i))
    nl[b].append((a, i))
    if len(nl[a]) > max_node:
        max_node = a
    if len(nl[b]) > max_node:
        max_node = b
    i += 1

c = len(nl[max_node])
print(c)

ans = [-1 for _ in range(N - 1)]
stack = [(max_node, -1, -1)]
while len(stack) > 0:
    v, p, pc = stack.pop()
    color = 1
    for next_v, i in nl[v]:
        if next_v == p:
            continue
        if color == pc:
            color += 1
        ans[i] = color
        stack.append((next_v, v, color))
        color += 1
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[[]for _ in range(n)]
c=[0]*n
d={}
f=[]
for i in range(n-1):
  a,b=map(int,input().split())
  d[min(a,b)*1000000+max(a,b)]=0
  f.append((a,b))
  s[a-1].append(b-1)
  s[b-1].append(a-1)
  c[a-1]+=1
  c[b-1]+=1
mc=max(c)
si=c.index(mc)
se={si}
c=[10**6]*n
Q=[(si,i)for i in s[si]]
while Q:
  P=[]
  for i in range(len(Q)):
    a,b=Q[i]
    se.add(a)
    ii=1+i+(i+1>=c[a])
    d[min(a+1,b+1)*1000000+max(a+1,b+1)]=ii
    c[b]=ii
    for j in s[b]:
      if j not in se:P.append((b,j))
  Q=P
print(mc)
for a,b in f:print(d[min(a,b)*1000000+max(a,b)])

Submission status: Wrong Answer

Solution code:
# ABC146d
ans = 1


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())

    n = int(input())

    edges = [list() for _ in range(n)]
    colors = [-1]*(n-1)

    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))

    def dfs(i, color, pre):
        for e in edges[i]:
            if e[0] == pre:
                continue
            global ans
            if ans < len(edges[i]):
                ans = len(edges[i])
            nc = 0
            for j in range(ans):
                if j == color:
                    continue
                nc = j
            colors[e[1]] = nc
            dfs(e[0], nc, i)
    dfs(0, 0, -1)
    print(ans)
    for i in colors:
        print(i+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]

memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].append(b)
    E[b].append(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

K = max(len(e) for e in E)

A = [0] * (N - 1)

visited = [False] * (N + 1)

Q = deque([1])
visited[1] = True
while Q:
    a = Q.popleft()
    c, v = divmod(a, N + 1)
    C = (i for i in range(1, K + 1) if i != c)
    for u in E[v]:
        if visited[u]:
            continue
        visited[u] = True
        c = next(C)
        Q.append(c * (N + 1) + u)
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

edge = sorted(edge, key=lambda x:x[0])
K = len(max(neighbor, key=len))
color = [set(range(1,K+1)) for _ in range(N)]

for x in edge:
    c = (color[x[0]] & color[x[1]]).pop()
    print(c)
    color[x[0]].remove(c)
    color[x[1]].remove(c)

Submission status: Wrong Answer

Solution code:
def examD():
    N = I()
    cur = [0]*(N-1)
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        d[a] +=1; d[b] +=1
        cur[i] = max(d[a],d[b])
    ans = max(cur)
    print(ans)
    for v in cur:
        if v>ans:
            v -=ans
        print(v)


def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]
cnt = [0] * (N + 1)

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

color = [0] * (N + 1)
root = cnt.index(1)
queue = deque([root])
color[root] = 1

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if color[v] == 0:
            while number == color[V]:
                number += 1
            color[v] = number
            queue.append(v)

print('\n'.join(map(str, color[1:])))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    colors = [1]*(n+1)
    ans = []
    for i in range(n-1):
        a,b = map(int,input().split())
        ans.append(max(colors[a],colors[b]))
        colors[a] += 1
        colors[b] += 1
        
    k = max(colors)
    print(k-1)
    for i in ans:
        print(i)


main()

Submission status: Wrong Answer

Solution code:
N = int(input())
tree=[0 for _ in range(N)]
nodes=[]
for _ in range(N-1):
    m = list(map(int, input().split()))
    tree[m[0]-1]+=1
    tree[m[1]-1]+=1
    nodes.append(m)
print(max(tree))
tree_col = [0 for _ in range(N)]
for i in nodes:
    if tree[i[0]-1]>tree[i[1]-1]:
        tree_col[i[0]-1]+=1
        tree_col[i[1]-1]+=1
        print(tree_col[i[0]-1])
    else:
        tree_col[i[0]-1]+=1
        tree_col[i[1]-1]+=1
        print(tree_col[i[1]-1])

Submission status: Wrong Answer

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

N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

BAN=[set() for i in range(N+1)]
ANS=[]

for x,y in E:
    for j in range(1,N+1):
        if j in BAN[x] or j in BAN[y]:
            continue
        ANS.append(j)
        BAN[x].add(j)
        BAN[y].add(j)
        break

print(max(ANS))
for a in ANS:
    print(a)

Submission status: Wrong Answer

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

V = [{} for _ in range(N)]
    
for i in range(N-1):
    a = L[i][0]
    b = L[i][1]
    for i in range(1, K+1):
        if i not in V[a] and i not in V[b]:
            V[a][i] = 1
            V[b][i] = 1
            print(i)
            break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    v = -1
    for k in g:
        if len(g[k]) == 1:
            v = k
            break
    
    s = [(v, 1)]
    done = set([v])
    K = 0
    ans = {}
    while s:
        u, c = s.pop()
        used = set([c])
        for v in g[u]:
            if v not in done:
                c = 1
                while c in used:
                    c += 1 
                    K = max(K, c)
                used.add(c)
                s.append((v, c))
                i, j = min(u, v), max(u, v)
                ans[(i, j)] = c
                done.add(v)
    print(K)
    for a, b in AB:
        print(ans[(a, b)])
    # return ans


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def bfs(i, V, E, Ec):
    V[i] = 1
    Q = [(i, 1)]
    while(True):
        Qi = []
        for q, cq in Q:
            c = 1
            if cq == c:
                c += 1
            for j, idx in E[q]:
                if V[j] == 0:
                    V[j] = 1
                    Qi.append((j, c))
                    Ec[idx] = c
                    if c + 1 == cq:
                        c += 2
                    else:
                        c += 1
        if len(Qi) == 0:
            break
        else:
            Q = Qi
    return V, Ec


n = int(input())
E = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
Ec = [None for _ in range(n - 1)]
V = [0 for _ in range(n + 1)]
_, Ec = bfs(1, V, E, Ec)
print(max(Ec))
for c in Ec:
    print(c)

Submission status: Wrong Answer

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
K = d[-1][1]
ans = [0] * (N - 1)
while d:
    j, _ = d.pop()
    L = 1
    used = set()
    for p in s[j]:
        if ans[p] == 0:
            while L in used:
                L += 1
            ans[p] = L
            used.add(L)
        else:
            used.add(ans[p])
print(K)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[[] for _ in range(n+1)]
from collections import defaultdict
d=defaultdict(int)
ab=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    ab.append((a,b))


cm=1
for ll in l:
    cm=max(len(ll),cm)
ll=[[] for _ in range(n+1)]
lll=[[] for _ in range(n+1)]
for a in range(1,n+1):
    c=1
    for b in l[a]:
        if b in lll[a]:
            continue
        if c in ll[a]:
            c+=1
        d[(a,b)]=c
        ll[a].append(c)
        ll[b].append(c)
        lll[b].append(a)

print(cm)
for i in range(n-1):
    a,b=ab[i]
    print(d[(a,b)])