Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

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

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

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

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

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

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:
from collections import deque

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

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	color = 1
	used_colors = [edges[tuple(sorted((ni, e)))] for e in nodes[ni]]
	unused = [c for c in range(1, n + 1) if not c in used_colors]
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		# print(a, b)
		if edges[(a, b)] == 0:
			# print(ni, unused)
			edges[(a, b)] = unused[0]
			unused = unused[1:]
		que.append(node)

	used[ni] = True

print(max(edges.values()))
print(*edges.values(), sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	color = 1
	used_colors = []
	unused = []
	for e in nodes[ni]:
		[a, b] = sorted([e, ni])
		used_colors.append(edges[(a, b)])
	unused = [c for c in range(1, n + 1) if not c in used_colors]
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		# print(a, b)
		if edges[(a, b)] == 0:
			# print(ni, unused)
			edges[(a, b)] = unused[0]
			unused = unused[1:]
		que.append(node)

	used[ni] = True

print(max(edges.values()))
print(*edges.values(), sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	color = 1
	used_colors = []
	unused = []
	for e in nodes[ni]:
		[a, b] = sorted([e, ni])
		used_colors.append(edges[(a, b)])
	unused = [c for c in range(1, n + 1) if not c in used_colors]
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		# print(a, b)
		if edges[(a, b)] == 0:
			# print(ni, unused)
			color = min(unused)
			edges[(a, b)] = color
			unused = unused[1:]
		que.append(node)

	used[ni] = True

print(max(edges.values()))
print(*edges.values(), sep='\n')

Submission status: Wrong Answer

Solution code:
import queue

N = int(input())

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

q = queue.Queue()
q.put(ki[0])

ans = 0
isVisited = [False]*N
while not q.empty():
    ki_elms = q.get()
    ans =  max(ans, len(ki_elms[0]))
    isVisited[ki_elms[1]] = True
    for child in ki_elms[0]:
        if isVisited[child]:
            continue
        else:
            q.put(ki[child])

print(ans)

q.put(ki[0])
ans = 0
isVisited = [False]*N
par_num = [-1]*N
par_num[ki[0][1]] = -1
while not q.empty():
    ki_elms = q.get()
    isVisited[ki_elms[1]] = True
    i = 1
    for child in ki_elms[0]:
        if isVisited[child]:
            continue
        else:
            if i == par_num[ki_elms[1]]:
                i += 1
            print(i)
            par_num[child] = i
            i += 1
            q.put(ki[child])

Submission status: Wrong Answer

Solution code:
s=int(input())
P=[]
Q=[]
for _ in range(s-1):
  t,u=map(int,input().split())
  P.append(int(t))
  Q.append(int(u))
R=[0 for j in range(s)]
R[0]-=1
for i in range(s-1):
  R[P[i]-1]+=1
a=max(R)+1
print(a)
R=[0 for l in range(s)]
for i in range(s-1):
  if R[P[i]-1]>=a:
    print(1)
    R[P[i]-1]=1
    R[Q[i]-1]=1
    continue
  else:
    print(R[P[i]-1]+1)
    R[P[i]-1]+=1
    R[Q[i]-1]=R[P[i]-1]

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=[i for i in range(1,n)]
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a,b=map(int,input().split())
        #heapq.heappush(w,(a,b,i))
        for j in range(1,n):
            if j not in x[a] and j not in x[b]:
                ans[i]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    print(*ans)
if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    z=[i for i in range(1,n)]
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a,b=map(int,input().split())
        heapq.heappush(w,(a,b,i))
    p=0
    q=1
    for hhh in range(len(w)):
        a,b,h=heapq.heappop(w)
        if a!=p:
            for i in z:
                if i not in x[a]:
                    q=i
                    p=a
                    break
        for j in range(q,n):
            if j not in x[a] and j not in x[b]:
                ans[h]+=j
                x[a].add(j)
                x[b].add(j)
                break
    print(max(ans))
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a2,b2=map(int,input().split())
        #a2,b2=max(a,b),min(a,b)
        if a2 not in d:
            d[a2]=set([(b2,i)])
        else:
            d[a2].add((b2,i))
    for i in d:
        heapq.heappush(w,(-len(d[i]),i))
    for hhh in range(len(w)):
        h1,a=heapq.heappop(w)
        for b,h in d[a]:
            for j in range(1,n):
                if j not in x[a] and j not in x[b]:
                    ans[h]+=j
                    x[a].add(j)
                    x[b].add(j)
                    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a2,b2=map(int,input().split())
        #a2,b2=max(a,b),min(a,b)
        if a2 not in d:
            d[a2]=set([(b2,i)])
        else:
            d[a2].add((b2,i))
    for i in d:
        heapq.heappush(w,(-len(d[i]),i))
    #for a,b,p in w:
    while len(w):
        h1,a=heapq.heappop(w)
        for b,h in d[a]:
            for j in range(1,n):
                if j not in x[a] and j not in x[b]:
                    ans[h]+=j
                    x[a].add(j)
                    x[b].add(j)
                    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a2,b2=min(a,b),max(a,b)
        #a2,b2=max(a,b),min(a,b)
        if a2 not in d:
            d[a2]=set([(b2,i)])
        else:
            d[a2].add((b2,i))
    for i in d:
        heapq.heappush(w,(-len(d[i]),i))
    #for a,b,p in w:
    while len(w):
        h1,a=heapq.heappop(w)
        for b,h in d[a]:
            for j in range(1,n):
                if j not in x[a] and j not in x[b]:
                    ans[h]+=j
                    x[a].add(j)
                    x[b].add(j)
                    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ab2=[0]*(n-1)
x=[[0]*(n-1) for i in range(n)]

l=1
for i in range(n-1):
    k=0
    c,d=ab[i][0]-1,ab[i][1]-1
    if ab[i][0]==1:
        ab2[i]=l
        x[c][l-1]=1
        x[d][l-1]=1
        l+=1
    else:
        for j in range(n):
            if x[c][j]==0 and x[d][j]==0:
                x[c][j]=1
                x[d][j]=1
                ab2[i]=j+1
                break
print(max(ab2))
for i in range(n-1):
    print(ab2[i])

Submission status: Wrong Answer

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

K=1
for i in range(1,N-1):
    x0,y0=AB[i-1][0],AB[i-1][1]
    x1,y1=AB[i][0],AB[i][1]
    if len(set([x0,y0,x1,y1]))!=4:
        K+=1
    else:
        K=1
    L.append(K)
    
print(max(L))
for i in L:
    print(i)

Submission status: Wrong Answer

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

for i in range(N-1):
    a, b = map(int, input().split())
    l[a-1] += 1
    l[b-1] += 1
print(max(l))
for i in range(N-1):
    print(i % max(l) + 1)

Submission status: Wrong Answer

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

for i in range(N-1):
    a, b = map(int, input().split())
    l[a-1] += 1
    l[b-1] += 1
print(max(l))
for i in range(N-1):
    print(i % max(l) + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
l = [deque() for i in range(N)]
ans = [0 for i in range(N-1)]
li = [[0,0] for i in range(N-1)]
for i in range(N-1):
    li[i][0], li[i][1] = map(int, input().split())
li.sort()
for i in range(N-1):
    a, b = li[i][0], li[i][1]
    j = 1
    while j in l[a-1] or j in l[b-1]:
        j += 1
    ans[i] = j
    l[a-1].append(j)
    l[b-1].append(j)
print(max(ans))
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input=sys.stdin.readline
def sol():
    n=int(input())
    x=[set([]) for i in range(n+1)]
    #z=[i for i in range(1,n)]
    #hhh=[1]*(n+1)
    ans=[0]*(n-1)
    w=[]
    d={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a2,b2=min(a,b),max(a,b)
        if a2 not in d:
            d[a2]=set([(b2,i)])
        else:
            d[a2].add((b2,i))
    for i in d:
        heapq.heappush(w,(-len(d[i]),i))
    y=[0]*2
    #for a,b,p in w:
    while len(w):
        h1,a=heapq.heappop(w)
        for b,h in d[a]:
            c=x[a]|x[b]
            #if y[0]!=a:
            #    for i in z:
            #        if i not in c:
            #            y[0]=a
            #            y[1]=i
            #            break
            #for j in range(y[1],n+1):
            for j in range(1,n+1):
                if j not in c:
                    ans[h]+=j
                    x[a].add(j)
                    x[b].add(j)
                    #if y[1]+1==j: y[1]+=1
                    break
    print(max(ans))
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
l = [deque() for i in range(N)]
ans = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    j = 1
    while j in l[a-1] or j in l[b-1]:
        j += 1
    ans[i] = j
    l[a-1].append(j)
    l[b-1].append(j)
print(max(ans))
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('input.txt')
input = sys.stdin.readline

def dfs(G, C, v):
	seen[v] = True
	global colors

	for idx, next in enumerate(G[v]):
		# print('今の状態',v, next, seen[next])
		if seen[next]:
			# print('色だけつけてスキップ')
			color_idx = G[next].index(v)
			C[v][idx] = C[next][color_idx]
			continue

		# color の割り当て
		# colors でループし、C[v]およびC[next]のなかで使われていなければセット
		for color in colors:
			# print('チェックするcolor',color)
			# print('対象の辺で使われているcolor', C[v], C[next])

			# どちらもで使われていない色であればセット
			if not C[v].count(color) and not C[next].count(color):
				# print('既存の', color, 'の色をセット')
				C[v][idx] = color
				break
			
		# colors 全てC[v]で使用済みであれば、新しいものを払い出し
		if C[v][idx] == 0:
			# print('新しい', colors[-1]+1, 'の色をセット')
			C[v][idx] = colors[-1]+1
			colors.append(C[v][idx])

		dfs(G, C, next)

N = int(input())
G = [[] for _ in range(N)]
O = []
for _ in range(N-1):
	a,b = MAP()
	G[a-1].append(b-1)
	G[b-1].append(a-1)
	O.append([a-1,b-1])

C = [[0]*len(g) for g in G]
seen = [False for _ in range(N)]
colors = [1]
dfs(G, C, 0)

print(len(colors))
for o in O:
	i = o[0]
	j = G[i].index(o[1])
	print(C[i][j])

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
#import bisect
#import math
#import heapq
#import sys
#input = sys.stdin.readline

#inf = float("inf")
#mod = 10**9 + 7
#mod = 998244353

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

N = int(input())
AB = [list(map(int,input().split())) for i in range(N-1)]
K = [0]*N
for ab in AB:
    a,b = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)

C = [0]*N
D = deque(AB)
flag = 0
visited = [-1]*N
#print(D)
while D:
    a,b = D.popleft()
    if visited[a-1] == -1 and visited[b-1] == -1:
        if flag == 0:
            flag = 1
            visited[a-1] = 0
            visited[b-1] = 0
            print(1)
            C[a-1] = 1
            C[b-1] = 1
        else:
            D.append([a,b])
    else:
        if visited[b-1] == -1:
            if C[a-1] == k:
                print(1)
                C[a-1] = 1
                C[b-1] = 1
            else:
                print(C[a-1]+1)
                C[a-1]+=1
                C[b-1] = C[a-1]
            visited[b-1] = 0
        else:
            visited[a-1] = 0
            if C[b-1] == k:
                print(1)
                C[a-1] = 1
                C[b-1] = 1
            else:
                print(C[b-1]+1)
                C[b-1]+=1
                C[a-1] = C[b-1]

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
import bisect
import math
import heapq
#import sys
#input = sys.stdin.readline

inf = float("inf")
mod = 10**9 + 7
#mod = 998244353

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

N = int(input())
AB = [list(map(int,input().split())) for i in range(N-1)]
K = [0]*N
for ab in AB:
    a,b = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)

C = [0]*N
D = deque(AB)
flag = 0
visited = [-1]*N
#print(D)
while D:
    a,b = D.popleft()
    if visited[a-1] == -1 and visited[b-1] == -1:
        if flag == 0:
            flag = 1
            visited[a-1] = 0
            visited[b-1] = 0
            print(1)
            C[a-1] = 1
            C[b-1] = 1
        else:
            D.append([a,b])
    else:
        m = max(C[a-1],C[b-1])
        C[a-1] = (m)%(k)+1
        C[b-1] = (m)%(k)+1
        print((m)%(k)+1)
        visited[a-1] = 0
        visited[b-1] = 0

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
import bisect
import math
import heapq
#import sys
#input = sys.stdin.readline

inf = float("inf")
mod = 10**9 + 7
#mod = 998244353

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

N = int(input())
AB = [list(map(int,input().split())) for i in range(N-1)]
K = [0]*N
for ab in AB:
    a,b = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)

C = [-1]*N
D = deque(AB)
flag = 0
#print(D)
while D:
    a,b = D.popleft()
    if C[a-1] == -1 and C[b-1] == -1:
        if flag == 0:
            flag = 1
            C[a-1] = 1
            C[b-1] = 1
            print(1)
        else:
            D.append([a,b])
    else:
        m = max(C[a-1],C[b-1])
        C[a-1] = (m)%k+1
        C[b-1] = (m)%k+1
        print((m)%k+1)

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[] for j in range(n)]

t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1

    k=int(0)
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1

    t.append(k+1)

print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
class node():
    def __init__(self,item):
        self.item = None
        self.parent = []
        self.children = []
        self.color = []

class tree():
    def __init__(self):
        self.nodes = []
        self.node_item = {}

    def add(self,item):
        self.nodes.append(item)
        self.node_item[item] = node(item)

    def describe(self,item,parent=None,children=None):
        if parent:
            self.node_item[item].parent.append(parent)
        if children:
            self.node_item[item].children.append(children)

    def print_TREE(self):
        for i in range(len(self.nodes)):
            print("item:{},parent:{},children{},color:{}".\
            format(self.nodes[i],self.node_item[self.nodes[i]].parent,\
            self.node_item[self.nodes[i]].children,self.node_item[self.nodes[i]].color))

    def CountColor(self):
        ans = 0
        for i in self.nodes:
            temp = len(self.node_item[i].parent) + len(self.node_item[i].children)
            ans = temp if ans < temp else ans
        return ans

    def paint(self,a_,b_):
        ans = []
        colorlist = [i for i in range(self.CountColor())]
        idx = 0
        for i in range(len(a_)):
            a,b = a_[i],b_[i]
            if colorlist[idx] not in self.node_item[a].color \
            and colorlist[idx] not in self.node_item[b].color:
                pass
            else:
                idx += 1
                if idx > len(colorlist)-1:
                    idx = 0

            self.node_item[a].color.append(colorlist[idx])
            self.node_item[b].color.append(colorlist[idx])
            ans.append(colorlist[idx] + 1)
        return ans





N = int(input())
TREE = tree()
a_ = []
b_ = []
for _ in range(N-1):

    a, b = map(int,input().split())
    a_.append(a)
    b_.append(b)
    if a in TREE.nodes:
        #TREE.add(a)
        TREE.describe(a,children=b)
    else:
        TREE.add(a)
        TREE.describe(a,children=b)
    TREE.add(b)
    TREE.describe(b,parent=a)
# print("here")
# TREE.print_TREE()

colorsum = TREE.CountColor()
print(colorsum)
a = TREE.paint(a_,b_)
for i in a:
    print(i)
# print(TREE.paint(a_,b_))
#TREE.print_TREE()

Submission status: Wrong Answer

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

edge = [0] * n #ans
visit = [False] * (n+1) #vert
color = [set() for i in range(n+1)]
visit[1] = True
q = [1]
edge[1] = 1
color[1].add(1)

while q:
    now = q.pop()
    c = 1
    for next, num in tree[now]:
        if not visit[next]:
            while c in color[now]:
                c += 1
            edge[num] = c
            color[next].add(c)
            visit[next] = True
            q.append(next)
            c += 1
    before = now

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

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
    m[a] +=1
    m[b] +=1
    k=1
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
    m[a] +=1
    m[b] +=1
    k=1
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a-1].append(k)
            l[b-1].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    m[a-1] +=1
    m[b-1] +=1
    k=1
    while True:

        if (k in l[a-1])==False and (k in l[b-1])==False:
            l[a-1].append(k)
            l[b-1].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]
w=[]
for p in range(n-1):
    e = list(map(int, input().split()))
    w.append(e)

for i in range(n-1):
    a=w[i][0]-1
    b=w[i][1]-1
    m[a] +=1
    m[b] +=1
    k=1
    while True:

        if (k in l[a])==False and (k in l[b])==False:
            l[a].append(k)
            l[b].append(k)
            break
        else:
            k +=1

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[] for j in range(n)]
m=[0]*n
t=[]
w=[]
for p in range(n-1):
    e = list(map(int, input().split()))
    w.append(e)

for i in range(n-1):
    a=w[i][0]-1
    b=w[i][1]-1
    m[a] +=1
    m[b] +=1
    k=1
    while True:

        if (k in l[a])==True:

            k +=1
        else:
            if (k in l[b])==True:
                k +=1
            else:
                l[a].append(k)
                l[b].append(k)
                break

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0] for j in range(n)]
m=[0]*n
t=[]
w=[]
for p in range(n-1):
    e = list(map(int, input().split()))
    w.append(e)

for i in range(n-1):
    a=w[i][0]-1
    b=w[i][1]-1
    m[a] +=1
    m[b] +=1
    k=1
    while True:

        if (k in l[a])==True:

            k +=1
        else:
            if (k in l[b])==True:
                k +=1
            else:
                l[a].append(k)
                l[b].append(k)
                break

    t.append(k)

c=max(m)
print(c)
for g in range(n-1):
    print(t[g])

Submission status: Wrong Answer

Solution code:
s=int(input())
P=[]
Q=[]
for _ in range(s-1):
  t,u=map(int,input().split())
  P.append(int(t))
  Q.append(int(u))
R=[0 for j in range(s)]
R[0]-=1
for i in range(s-1):
  R[P[i]-1]+=1
a=max(R)+1
print(a)
R=[0 for l in range(s)]
for i in range(s-1):
  if R[P[i]-1]>=a:
    print(1)
    R[P[i]-1]=0
    R[Q[i]-1]=0
    continue
  else:
    print(R[P[i]-1]+1)
    R[P[i]-1]+=1
    R[Q[i]-1]=R[P[i]-1]

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, id, max_node_num):
        self.parent_id = 0
        self.id = id
        self.color_id_flag = [0]*max_node_num

    def get_next_color_id(self):
        for num, i in enumerate(self.color_id_flag):
            if i == 0:
                return num+1

    def set_color_id(self, color_id):
        self.color_id_flag[color_id-1] = 1

    def set_parent_id(self, parent_id):
        self.parent_id = parent_id


def main():
    N = int(input())
    a_b_list = []
    node_dict = {}
    ans = []

    for i in range(N):
        node_dict[i + 1] = Node(i + 1, N)
        if i == N-1:
            break
        a, b = map(int, input().split())
        a_b_list.append([a, b])

    for a_b in a_b_list:
        a = a_b[0]
        b = a_b[1]

        node_dict[b].parent_id = a

        color_id = node_dict[a].get_next_color_id()
        node_dict[a].set_color_id(color_id)
        node_dict[b].set_color_id(color_id)

        ans.append(color_id)

    print(max(ans))
    print(*ans, sep="\n", end="")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 0)])

while(len(queue)):
    q, c = queue.popleft()
    k = 0
    for v in edges[q]:
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        k += 1
        print(a, b, c)
        data[(a, b)] = c+k
        queue.append((v, c+k))
print(maxColor)
for i in range(N-1):
    print((data[inputData[i]]-1)%maxColor+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB =[]
V = [[] for _ in range(N)]
Edict = dict()
for _ in range(N-1):
    a,b = map(int,input().split())
    AB.append((a-1,b-1))
    V[a-1].append(b-1)
    V[b-1].append(a-1)
K = min(len(V[i]) for i in range(N))
for i in V:
    i.sort()
for i,v in enumerate(V[0]):
    Edict[(0,v)] = i
for i in range(1,N): # 2(N-1)
    color = 0
    for j in V[i]:
        if j < i: # unique per V and first
            parent_color = Edict[(j,i)]
        else:
            if color == parent_color:
                color += 1
            Edict[(i,j)] = color
            color += 1
print(K)
for i in AB:
    print(Edict[i]+1)

Submission status: Wrong Answer

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 1)])

while(len(queue)):
    q, c = queue.popleft()
    for i, v in enumerate(edges[q]):
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        data[(a, b)] = c+i
        queue.append((v, c+i))
print(maxColor)
for i in range(N-1):
    print((data[inputData[i]]-1)%maxColor+1)

Submission status: Wrong Answer

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 1)])

while(len(queue)):
    q, c = queue.popleft()
    for i, v in enumerate(edges[q]):
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        data[(a, b)] = c+i
        queue.append((v, c+i))
print(data)
print(maxColor)
for i in range(N-1):
    print((data[inputData[i]]-1)%maxColor+1)

Submission status: Wrong Answer

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 1)])
while(len(queue)):
    q, c = queue.popleft()
    for i, v in enumerate(edges[q]):
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        data[(a, b)] = c+i
        queue.append((v, c+i))

print(maxColor)
for i in range(N-1):
    print(data[inputData[i]]%maxColor+1)

Submission status: Wrong Answer

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    ipt = []
    tree = []
    colors = [0] * (N-1)
    [tree.append([]) for x in range(N)]

    for _ in range(N-1):
        ipt.append(list(map(int, input().split())))
    ipt = sorted(ipt)

    for o in range(len(ipt)):
        a, b = ipt[o][0], ipt[o][1]

        for i in range(1, 10**5+1):
            if i in tree[a-1] or i in tree[b-1]:
                continue

            tree[a-1].append(i)
            tree[b-1].append(i)
            colors[o] = i
            break


    # for _ in range(N-1):
    #     a, b = map(int, input().split())
    #     for i in range(1, 10**5+1):
    #         if i in tree[a-1] or i in tree[b-1]:
    #             continue
    #
    #         tree[a-1].append(i)
    #         tree[b-1].append(i)
    #         colors.append(i)
    #         break

    print(len(set(colors)))
    
    for c in colors:
        print(c)

    # f = open('lll', 'w', encoding='utf-8')
    # f.write('\n'.join([ str(c) for c in colors]))
    # f.close()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    tree = []
    colors = []
    [tree.append([]) for x in range(N)]

    for _ in range(N-1):
        a, b = map(int, input().split())
        for i in range(1, 10**5+1):
            if i in tree[a-1] or i in tree[b-1]:
                continue

            tree[a-1].append(i)
            tree[b-1].append(i)
            colors.append(i)
            break

    print(len(set(colors)))

    for c in colors:
        print(c)


if __name__ == '__main__':
    main()