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:
#!/usr/bin/env python3
#ABC146 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edge = [[] for _ in range(n)]
lst = []
for _ in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    lst.append((a,b))

cnt = 0
for i in range(n):
    cnt = max(cnt,len(edge[i]))
#print(cnt)

ans = [None]*n

que = deque()
que.append((0,1,-1))
tmp = 1
ans[0] = 1
while que:
    v,color,p = que.popleft()
    if ans[v] == None:
        if tmp == color:
            if tmp == cnt:
                ans[v] = 1
                tmp = ans[v]
            else:
                if p == 0:
                    ans[v] = color
                else:
                    ans[v] = color + 1
                tmp = ans[v]
        else:
            ans[v] = tmp
        tmp += 1
    #print(v,color,ans[v],tmp,ans)
    if tmp > cnt:
        tmp = 1
    x = 1
    for u in edge[v]:
        if ans[u] == None:
            que.append((u,ans[v],v))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N=int(input());AB=[list(map(int,input().split())) for _ in range(1,N)]
nd=[0 for _ in range(N)]
table = [[] for _ in range(N)]
for a,b in AB:
  table[a-1].append(b)
  nd[a-1]+=1
  nd[b-1]+=1

K=max(nd)
print(K)
co=[0 for _ in range(N)]
for a,li in enumerate(table,1):
  c=[i for i in range(1,K+1) if i != co[a-1]]
  for b,y in zip(li,c):
    co[b-1]=y
    print(y)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
D=collections.Counter([i[0] for i in AB]+[i[1] for i in AB]).most_common()
M=D[0][1]
print(M)
data=[set() for i in range(N+1)]
for a,b in AB:
    #print(a,b,"a,b")
    for m in range(1,M+1):
        if m not in data[a] and m not in data[b]:
            data[a].add(m)
            data[b].add(m)
            print(m)
            break

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ab = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n-1)]
    tmd = collections.defaultdict(list)
    tmdd = collections.defaultdict(int)
    m_in = 0
    m_no = -1
    for a, b in ab:
        tmd[a] += [b]
        tmd[b] += [a]
        tmdd[a] += 1
        tmdd[b] += 1
    cnt = 0
    for k, v in tmdd.items():
        if v > m_in:
            m_in = v
            m_no = k
        elif v == m_in:
            cnt += 1
    m_in = m_in if cnt != len(tmd) - 1 else m_in + 1

    ql = [[0, m_no]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[m_no]
    aq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            ls = []
            limit = tmdd[tmp]
            for i in range(1, m_in + 1):
                if i != cost:
                    ls.append(i)
                if len(ls) >= limit:
                    break
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    p = ls.pop()
                    ql.append([p, tmv])
                    fq[tmv]
                    aq[tmp, tmv] = p
                    aq[tmv, tmp] = p
        else:
            break
    print(m_in)
    for a, b in ab:
        print(aq[a, b])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

tmp = {x: [] for x in range(1, n+1)}
ans = []
for a, b in v:
    c = 1
    while True:
        if c not in tmp[a] and c not in tmp[b]:
            ans.append(c)
            tmp[a].append(c)
            tmp[b].append(c)
            break
        else:
            c += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
for i in range(N-1):
    AB[i][0] = AB[i][0]-1
    AB[i][1] = AB[i][1]-1
Edges =[[] for _ in range(N)]
for i in range(N-1):
    Edges[AB[i][0]].append(AB[i][1])
    Edges[AB[i][1]].append(AB[i][0])
c = 0
for i in range(N):
    if c < len(Edges[i]):
        c = len(Edges[i])

usedColors = [len(Edges[i]) for i in range(N)]
for i in range(N-1):
    a,b = AB[i][0],AB[i][1]
    print(max(usedColors[a],usedColors[b]))
    if usedColors[a] > usedColors[b]:
        usedColors[a] = usedColors[a]-1
    elif usedColors[a] < usedColors[b]:
        usedColors[b] = usedColors[b]-1
    else:
        usedColors[a] = usedColors[a]-1
        usedColors[b] = usedColors[b]-1

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
e = [list(map(int, input().split())) for _ in range(n-1)]
c = [0 for _ in range(n-1)]
e.sort()
cmap = [[0 for _ in range(n-i)] for i in range(n)]
for l in e:
    idx2 = l[1]-l[0]-1
    cmap[l[0]-1][idx2]=-1
    
d = deque()
d.append(1)
itr = 0
while(d):
    ed = d.popleft() -1
    clist = list()
    usedc = set()
    try:
        while(1):
            if e[itr][0]-1 == ed:
                i = e[itr][1]-1
                clist.append([i, cmap[ed][i-ed-1]])
                itr += 1
            else:
                break
    except:
        pass

    for i in range(ed):
        usedc.add(cmap[i][ed-i-1])
    for color in clist:
        if color[1] == -1:
            d.append(color[0]+1)
            cn = 1
            while(1):
                if cn in usedc:
                    cn+=1
                else:
                    usedc.add(cn)
                    break
            cmap[ed][color[0]-ed-1] = cn

for i in range(n-1):
    idx2 = e[i][1]-e[i][0]-1
    c[i] = cmap[e[i][0]-1][idx2]

print(max(c))
for num in c:
    print(num)

Submission status: Wrong Answer

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


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
#    print(K)
    for a, b in E2:
        for c in range(1, K+1):
            if c not in C[a] and c not in C[b]:
                print(c)
                C[a].add(c)
                C[b].add(c)
                break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ex = []
for i in range(n):
    ex.append(set())
    
color = [0]*(n-1)
count = [0]*n
for i in range(n-1):
    count[a[i]-1] += 1
    count[b[i]-1] += 1
    cand = 1
    while cand in ex[a[i]-1] or cand in ex[b[i]-1]:
        cand += 1
    ex[a[i]-1].add(cand)
    ex[b[i]-1].add(cand)
    color[i] = cand
print(max(count))
for c in color:
    print(c)

Submission status: Wrong Answer

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


def main():
    N = int(input().strip())
    each_edge = [set() for i in range(N)]
    ans = []

    for i in range(N-1):
        a, b = map(int, input().strip().split())
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        if len(aset) == 0 and len(bset) == 0:
            tmp = 1
        else:
            outlist = aset | bset
            for i in range(N-1):
                if i+1 in outlist:
                    continue
                else:
                    tmp = i+1
                    break
        each_edge[a-1].add(tmp)
        each_edge[b-1].add(tmp)
        ans.append(tmp)

    K = 1
    for i in each_edge:
        K = max(K, len(i))
    print(K)
    for line in ans:
        print(line)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
sind = sorted(range(len(ab)),key=lambda k:ab[k])

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
# anslist = [[0]*N for i in range(N)]
anslist = []
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			anslist.append(kk)
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

ans = []
for i in range(N-1):
	ans.append(anslist[sind[i]])

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

Submission status: Wrong Answer

Solution code:
N=int(input()) 
G  = [[] for _ in range(N)]

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

L = [len(i) for i in G]
L[0]-=1

K = max(L)+1
print(K)
c =[0]*N
 
def rot(n):
  if n>K:
    return n-K
  else:
    return n
  
queue =[]
c[0] = 0
start = 1
queue.append(start)

while len(queue)!=0:
   target = queue.pop(0)
   iro = c[target-1]
   for i in G[target-1]:
     c[i-1] =rot(iro+1)
     iro +=1
     queue.append(i)
    
c.pop(0)
    
for i in c:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
D = [deque([]) for _ in range(N)]
MAP = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a, b)
    D[a-1].append(b-1)
    D[b-1].append(a-1)

maxc = 0

for i, d in enumerate(D):
    c = len(d)
    if c > maxc:
        maxc = c
        maxi = i

#print('max color = {}'.format(maxc))
q = deque([])
c = 1
for n in D[maxi]:
    #print('max index = {}, next node = {}'.format(maxi, n))
    MAP[maxi][n] = c
    MAP[n][maxi] = c
    c += 1
    q.append(n)
FIN = [0] * N
FIN[maxi] = 1
while q:
    ind = q.popleft()
    FIN[ind] = 1
    c = 1
    for n in D[ind]:
        if MAP[ind][n] != 0:
            continue
        while c in D[ind]:
            c += 1
        MAP[ind][n] = c
        MAP[n][ind] = c
        c += 1
        if FIN[n] == 0 and n not in q:
            q.append(n)

print(maxc)
for a, b in AB:
    print(MAP[a-1][b-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
K = 1
ans = []
G = [1] * (N+1)
G2 = [set() for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    mab = max(G[a], G[b])
    # print(G[a], G[b], G2[4])
    K = max(K, mab)
    ans += [mab]
    G2[a].add(mab)
    G2[b].add(mab)
    while G[a] in G2[a]:
        G[a] += 1
    while G[b] in G2[b]:
        G[b] += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
basho = {}
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    s = str(a) + '-' + str(b)
    basho[s] = i
#print(basho)
#print(graph)
maxi = 0
for i in range(N):
    leni = len(graph[i])
    maxi = max(leni, maxi)
K = maxi
color = [0 for i in range(N-1)]
for i in range(N):
    v = graph[i]
    colk = [False for i in range(K)]
    for j in v:
        if i < j:
            n = str(i) + '-' + str(j)
        else:
            n = str(j) + '-' + str(i)
        #print(n)
        if color[basho[n]] == 0:
            ind = colk.index(False)
            color[basho[n]] = ind + 1
            colk[ind] = True
        else:
            colk[color[basho[n]]-1] = True
print(K)
for i in range(N-1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
L=[[] for _ in range(n)]
M=[0 for _ in range(n-1)]
c=1
for i in range(n-1):
  s,t=map(int,input().split())
  for j in range(1,c+1):
    if j not in L[s-1] and j not in L[t-1]:
      L[s-1].append(j)
      L[t-1].append(j)
      M[i]=j
      break
  else:
    c+=1
    L[s-1].append(c)
    L[t-1].append(c)
    M[i]=c
print(c)
for m in M:print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [0]*(N-1)
cho = [0]*(N+1) #cho[i]にi番目の頂点の根元の色
res = [0]*(N-1) #枝の色
for i in range(0,N-1):
    di = list(map(int, input().split()))
    di.append(i)
    data[i] = di

data = sorted(data)
print(data)
for i in range(0,N-1):
    if i != 0 and data[i][0] == data[i-1][0]:
        cur += 1
    else:
        cur = 1
    if cur == cho[data[i][0]]: cur += 1
    res[data[i][2]] = cur
    cho[data[i][1]] = cur

print(max(cho))
for item in res:
    print(item)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)


class Node:

    def __init__(self, _id):
        self.id = _id
        self.children = []
        self.color = None

    def add(self, node):
        self.children.append(node)

    def __len__(self):
        return len(self.children)

    def coloring(self):
        if not self.children:
            return
        for i, child in enumerate(self.children):
            if i < self.color or self.color == -1:
                child.color = i
                child.coloring()
            else:
                child.color = i+1
                child.coloring()


def main():
    n = int(input())

    nodes = [Node(i) for i in range(n)]

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

    nodes[0].color = -1
    nodes[0].coloring()
    del nodes[0]
    nodes.sort(key=lambda n: n.id)

    print(max([n.color for n in nodes])+1)
    for n in nodes:
        print(n.color+1)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

graph = [[] for _ in range(n)]

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

print(graph)

stack = [(0, -1)]
visited = [-1]*n

k = 0
while stack:
    node, color = stack.pop()
    visited[node] = 1

    if k < len(graph[node]):
        k = len(graph[node])
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):
        if visited[child] == 1:

            continue
        if child_color == -1:
            if tmp == color:
                tmp += 1
            graph[node][i] = (child, tmp)
            stack.append((child, tmp))
            tmp +=1

print(k)
for a, b in ab:
    print(list(filter(lambda x: x[0]==(b-1), graph[a-1]))[0][1])

Submission status: Wrong Answer

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

d = {x: [] for x in range(1, n+1)}

for a, b in v:
    d[a].append(b)
    d[b].append(a)

tmp = {x: [] for x in range(1, n+1)}
ans = []
for a, b in v:
    c = 1
    while True:
        if c not in tmp[a] and c not in tmp[b]:
            ans.append(c)
            tmp[a].append(c)
            tmp[b].append(c)
            break
        else:
            c += 1

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

Submission status: Wrong Answer

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())

vs = [[] for i in range(n)]
for i in range(n-1):
    s,e = words(int)
    vs[s-1].append(e-1)

import queue
q = queue.Queue()
q.put(0)
color = [0] * n
color[0] = 1
while not q.empty():
    v = q.get()
    cur_c = 1
    for c in vs[v]:
        if color[v] == cur_c:
            cur_c +=1
        color[c] = cur_c
        cur_c += 1
        q.put(c)

for i in range(n):
    print(color[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = [[] for i in range(N)]
basho = {}
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    s = str(a) + '-' + str(b)
    basho[s] = i
#print(basho)
#print(graph)
maxi = 0
for i in range(N):
    leni = len(graph[i])
    maxi = max(leni, maxi)
K = maxi
color = [0 for i in range(N-1)]
for i in range(N):
    v = graph[i]
    colk = [False for i in range(K)]
    for j in v:
        if i < j:
            n = str(i) + '-' + str(j)
        else:
            n = str(j) + '-' + str(i)
        print(n)
        if color[basho[n]] == 0:
            ind = colk.index(False)
            color[basho[n]] = ind + 1
            colk[ind] = True
        else:
            colk[color[basho[n]]-1] = True
print(K)
for i in range(N-1):
    print(color[i])

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-1)
for i in range(N):
    node = tmp[i][0]
    #print ("node:" , node, colors)
    tmp_color = 1
    used_color = [False] * (tmp[0][1]+2)
    #print(used_color)
    for edge in n_list[node]:
        used_color[colors[edge[1]]] = True
    #print(used_color, tmp_color)
    while used_color[tmp_color]:
        tmp_color+=1
    for edge in n_list[node]:
        if colors[edge[1]] == 0:
            colors[edge[1]] = tmp_color
            tmp_color += 1
            #print(tmp_color, used_color)
            while used_color[tmp_color]:
                tmp_color+=1

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(input())
E = [tuple(i.split()) for i in sys.stdin.readlines()]

ADJ = {}
visited = {}
colored = {}
mn = ('', 0)
for e in E:
    if not ADJ.get(e[0]):
        ADJ[e[0]] = []
    ADJ[e[0]].append(e[1])
    if not ADJ.get(e[1]):
        ADJ[e[1]] = []
    ADJ[e[1]].append(e[0])
    if len(ADJ[e[0]]) > mn[1]:
        mn = (e[0], len(ADJ[e[0]]))
    if len(ADJ[e[1]]) > mn[1]:
        mn = (e[1], len(ADJ[e[1]]))

print(mn[1])
Q = deque([mn[0]])
while len(Q) > 0:
    n = Q.popleft()
    visited[n] = True
    used_color = set()
    ptr = 1
    for v in ADJ[n]:
        e = (n, v) if n < v else (v, n)
        if not visited.get(v):
            Q.append(v)
        if not colored.get(e):
            while ptr in used_color:
                ptr += 1
            colored[e] = ptr
            used_color.add(ptr)
            print(ptr)
        else:
            used_color.add(colored[e])

Submission status: Wrong Answer

Solution code:

n = int(input())
color = [None for i in range(n)]
tree = {}
res = 0
for i in range(n-1):
    u, v = [int(x) for x in input().strip().split()]
    if u not in tree:
        tree[u] = []
    if v not in tree:
        tree[v] = []
    tree[u].append(v)
    tree[v].append(u)
    res = max(res, len(tree[u]),len(tree[v]))

# for i in range(1,n+1):
#     if i not in tree:
#         tree[i] = []

edge = []
color[0] = 0

for i in range(1,n+1):
    for v in tree[i]:
        if v>i:
            tc = color[i-1]+1
            if tc>res:
                tc = tc%res
            color[i-1] = tc
            color[v-1] = tc
            edge.append(tc)

# res = max(edge)
print(res)
for e in edge:
    print(e)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def p(tt, parent):
    children = tt[parent]
    res = {parent: children}
    for c, ii in children:
        res.update(p(tt, c))
    return res


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tt = defaultdict(list)

    for i, (a, b) in enumerate(ab):
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa

    tree = p(tt, 0)
    # print(tree)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    # res = [None] * (N - 1)
    # 
    # def solve(pos, parentcol):
    #     children = tt[pos]
    #     for iii, (c, i) in enumerate(children):
    #         res[i] = (parentcol + 1 + iii) % colors
    #         solve(c, res[i])
    # 
    # solve(0, -1)
    # 
    # for i in range(N - 1):
    #     print(res[i] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)
    colors[(a, b)] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, set()]]
while Q:
    cur, prev, NG = Q.pop()
    for nex in adj[cur]:
        c = list(cand-NG)
        if nex == prev:
            continue
        p = c.pop()
        colors[(min(cur, nex), max(cur, nex))] = p
        Q.append([nex, cur, {p}])
print(col)
for a, b in ed:
    print(colors[(a, b)])

Submission status: Wrong Answer

Solution code:
N = int(input())

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

for _ in range(N - 1):
  a, b = (int(i) for i in input().split(' '))
  
  if not(b in lst[a]):
    lst[a].append(b)
  
  if not(a in lst[b]):
    lst[b].append(a)
  
  ans.append(max(len(lst[a]), len(lst[b])))

#print('ans:{}'.format(ans))
ans.insert(0, max(ans))
#print('ans:{}'.format(ans))
for i in ans:
  print(str(i))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
ColorV = [0]*(N)

L = []
n = 1
maxn = 1

for i in range(N-1):
    if i == 0:
        ColorV[0] = 0
        ColorV[1] = 1
        L.append(1)
    else:
        if a[i] == a[i-1]:
            if n + 1 != ColorV[a[i]-1]:
                ColorV[b[i]-1] = n+1
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
            else:
                ColorV[b[i]-1] = n+2
                L.append(n+2)
                n = n+2
                if n >= maxn:
                    maxn = n
        else:
            n = 1
            if n != ColorV[a[i]-1]:
                ColorV[b[i]-1] = n
                L.append(n)
                n = n
                if n >= maxn:
                    maxn = n
            else:
                ColorV[b[i]-1] = n
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
print(maxn)
for i in range(N-1):
    print(L[i])

Submission status: Wrong Answer

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


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
    print(K)
    for a, b in E2:
        for i in range(1, K+1):
            if i not in C[a]:
                print(i)
                C[a].add(i)
                C[b].add(i)
                break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
tree=[[] for i in range(n)]
for i in l:
  tree[i[0]-1].append(i[1])
  tree[i[1]-1].append(i[0])
ans=0
for i in tree:
    ans=max(ans,len(i))
print(ans)
c=[1 for i in range(n+1)]
for i in l:
    x=i[0]
    y=i[1]


    if c[x]>c[y]:
        print(c[x])
        c[x]+=1
    elif c[x]<c[y]:
        print(c[y])
        c[y]+=1
    else:
        print(c[x])
        c[x]+=1
        c[y]+=1

Submission status: Wrong Answer

Solution code:
N = int(input())

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

for _ in range(N - 1):
  a, b = (int(i) for i in input().split(' '))
  
  if not(b in lst[a]):
    lst[a].append(b)
  
  if not(a in lst[b]):
    lst[b].append(a)
  
  ans.append(max(len(lst[a]), len(lst[b])))

print('ans:{}'.format(ans))
ans.insert(0, max(ans))
print('ans:{}'.format(ans))
for i in ans:
  print(str(i))

Submission status: Wrong Answer

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

d = {x: [] for x in range(1, n+1)}

for a, b in v:
    d[a].append(b)
    d[b].append(a)

res = 0
for key, value in d.items():
    res = max(res, len(value))

tmp = {x: [] for x in range(1, n+1)}
ans = []
for a, b in v:
    c = 1
    while True:
        if c not in tmp[a] and c not in tmp[b]:
            ans.append(c)
            tmp[a].append(c)
            tmp[b].append(c)
            break
        else:
            c += 1

print(res)
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [[] for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  for i in range(1, K+1):
    if not (i in V[a]):
      if not (i in V[b]):
        c = i
        req_K = False
        break
  if req_K:
    K += 1
    c = K
    V[a].append(c)
  V[b].append(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
from copy import deepcopy
input = sys.stdin.readline

N = int(input())
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 0
color_set = set([i for i in range(1, 10**5)])

q = [(0, None)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.pop()
            if c != color:
                color_dict[(u, v)] = c
                color_dict[(v, u)] = c
                q.append((v, c))
            else:
                c = c_set.pop()
                color_dict[(u, v)] = c
                color_dict[(v, u)] = c
                q.append((v, c))
            K = max(K, c)

print(K)
for pair in edge:
    print(color_dict[pair])

Submission status: Wrong Answer

Solution code:
from collections import deque

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)]
q = deque()
q.append((max_node, -1, -1))
while len(q) > 0:
    v, p, pc = q.popleft()
    color = 1
    for next_v, i in nl[v]:
        if next_v == p:
            continue
        if color == pc:
            color += 1
        ans[i] = color
        q.append((next_v, v, color))
        color += 1
for a in ans:
    print(a)

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

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

color = [0] * (N + 1)
queue = deque([1])
color_v = [[] for _ in range(N + 1)]

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

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
li=[0]*(n+1)
for i in range(n-1):
    li[ab[i][0]]+=1
    li[ab[i][1]]+=1
print(max(li))
ma=max(li)
li2=[1]*(n+1)

for i in range(n-1):
    iro=li2[ab[i][0]]
    print(iro)
    
    if iro+1>ma:
        iro=0
    li2[ab[i][1]]=iro+1
    li2[ab[i][0]]=iro+1

Submission status: Wrong Answer

Solution code:
N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = list(set(graph[i])&set(graph[j]))
    a_list.append(ans[0])
    graph[i].remove(ans[0])
    graph[j].remove(ans[0])
print(max(a_list))
for i in a_list:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=[0]*n
cnt=1
ans[0]=10**5+1
top=1
for i in range(n-1):
    a,b=map(int,input().split())
    if a!=top:
        top=a
        cnt=1
    if ans[top-1]==cnt:
        cnt=ans[top-1]+1
    ans[b-1]=cnt
    cnt+=1
ans[0]=max(ans[1:])
for i in range(n):
    print(ans[i])