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 fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    ab = [list(map(int, input().split())) for i in range(n-1)]

    e = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = ab[i]
        e[a].append(b)

    d = defaultdict(int)
    for i in range(n-1):
        a, b = ab[i]
        d[a] += 1
        d[b] += 1
    ans = 0
    for i in d.keys():
        ans = max(ans, d[i])
    print(ans)
    # print(d.values())
    # ansl = [0 for i in range(n + 1)]
    # dd = defaultdict(int)
    # for i in range(n - 1):
    #     a, b = ab[i]
    #     c = max(dd[a], dd[b]) + 1
    #     ansl[i] = c
    #     dd[a] += c + 1
    #    dd[b]+=c + 1
        

        
    ansl = [0 for i in range(n+1)]
    col = [-1 for i in range(n+1)]
    def f(v, c):
        col[v] = 1
        t = 1
        for i in e[v]:
            if col[i] == -1:
                if t == c:
                    t+=1
                ansl[i] = t
                f(i, t)
                t+=1
    f(1,0)
    #print(*ansl)
    for i in range(2,len(ansl)):
        print(ansl[i])



    

    

    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
ed = []
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  if v < u: u, v = v, u
  ed.append((u, v))
de = dd(set)
d = [0] * (N + 1)
res = 0
for k in e.keys():
  res = max(len(e[k]), res)
print(res)
for i in range(N - 1):
  u, v = ed[i]
  d[u] += 1
  d[v] += 1
  if d[u] > d[v]:
    d[v] -= 1
  elif d[v] < d[u]:
    d[u] -= 1
  print(max(d[u], d[v]))

Submission status: Wrong Answer

Solution code:
from queue import  Queue
n = int(input())


class uf_tree():

  def __init__(self, n):
    self.n = n
    self.par = [i for i in range(n)]
    self.rank = [0 for i in range(n)]

  def indep(self):
    dep = 0
    for i in range(self.n):
      if i == self.par[i]:
        dep += 1

    return dep

  def unite(self, x, y):
    if self.root(x) == self.root(y):
      return
    else:
      rootx = self.root(x)
      rooty = self.root(y)
      if self.rank[rootx] < self.rank[rooty]:
        self.par[rootx] = rooty
      else:
        self.par[rooty] = rootx
        if self.rank[rootx] == self.rank[rooty]:
          self.rank[rootx] += 1

  def root(self, i):
    if self.par[i] == i:
      return i
    else:
      self.par[i] = self.root(self.par[i])
      return self.par[i]

  def same(self, x, y):
    return self.root(x) == self.root(y)

tree = uf_tree(n)

edges = {}
arr = [0 for i in range(n-1)]
dic = {}

for i in range(n-1):
  a,b = map(int,input().split())
  dic[str(a-1)+","+str(b-1)] = i
  if a-1 in edges:
    edges[a-1].append(b-1)
  else:
    edges[a-1] = [b-1]
  tree.unite(a-1,b-1)

root = tree.root(0)
que = []
que.append([root,0])
# print(root)
# print(edges)
while not len(que)==0:
  top = que[-1]
  que.pop()
  v = top[0]
  col = top[1]
  color = 1
  if v in edges:
    nex = edges[v]
  else:
    continue
  nc = []
  # print(v)
  # print(nex)
  for i in range(len(nex)):
    if col != color:
      # nc.append(color)
      que.append([nex[i],color])
      arr[dic[str(v)+","+str(nex[i])]] = color
      color += 1
    else:
      # nc.append(color+1)
      arr[dic[str(v)+","+str(nex[i])]] = color+1
      que.append([nex[i],color+1])
      color += 2

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

Submission status: Wrong Answer

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

for i in range(n-1):
    col[a[i]-1] += 1
for i in range(n-1):
    col[b[i]-1] += 1

k = max(col)
print(k)

for i in range(n-1):
    color = 1
    while color in x[a[i]-1] or color in x[b[i]-1]:
        color += 1
    else:
        x[a[i]-1].append(color)
        x[b[i]-1].append(color)
        print(color)

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

Submission status: Wrong Answer

Solution code:
#D
N = int(input())
AB = [list(map(int,input().split())) for i in range(N-1)]
C = [0]*N
for ab in AB:
    a,b = ab
    C[a-1]+=1
    C[b-1]+=1
    
M = max(C)
D = [[0 for i in range(M)] for j in range(N)]
print(M)
for i in range(N-1):
    a,b = AB[i]
    d1,d2 = D[a-1],D[b-1]
    #print(d1,d2)
    for j in range(M):
        if d1[j] == d2[j] and d1[j] == 0:
            ans = j+1
            break
    print(ans)
    D[a-1][j] = 1
    D[b-1][j] = 1

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])
    print(max(cur))
    for v in cur:
        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:
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])

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 = K
    for p in s[j]:
        if ans[p] == 0:
            ans[p] = L
            L -= 1
print(K)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

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

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=[[0] for _ in range(n)]
for i in range(n-1):
	a=ab[i][0]
	b=ab[i][1]
	t=max(max(x[a-1]),max(x[b-1]))+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:
from sys import setrecursionlimit

setrecursionlimit(100000)

N = int(input())

adj = [list() for _ in range(N)]

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


res = [None]*(N-1)

C = max(len(l) for l in adj)

def rec(v, used):
    global res
    c = 0
    for u,i in adj[v]:
        if c == used:
            c += 1
            c %= C
        if res[i] is None:
            res[i] = c
            rec(u, c)
        c += 1
        c %= C
rec(0, -1)
print(C)
for c in res:
    print(c+1)

Submission status: Wrong Answer

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

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

degree_max = max([len(tree[i]) for i in range(n)])
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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    ed = [[] for i in range(n)]
    edg = defaultdict(int)
    ans = [None] * (n - 1)
    for i in range(n - 1):
        a, b = LI_()
        ed[a].append((b, i))
        ed[b].append((a, i))
        edg[a] += 1
        edg[b] += 1
    ma = max(edg.values())
    print(ma)
    for num, a in enumerate(ed):
        if len(a) == ma:
            break
    q = deque([num])
    while q:
        a = q.pop()
        o = 1
        for b, i in ed[a]:
            if ans[i] == None:
                ans[i] = o
                o += 1
                q.appendleft(b)
            else:
                o += 1
    for i in ans:
        print(i)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for i in range(N)]
D = {}

for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)
    
    u,v = min(u,v),max(u,v)
    D[str(u)+str(v)] = 0

colors = [0]*N

res = 0

for e in edges :
    res = max(res, len(e))

c = 1
colors[0] = 1
from collections import deque
q = deque([0])
while q :
    now = q.popleft()
    Z = []
    for nxt in edges[now] :
        if colors[nxt] != 0 :
            Z.append(colors[nxt])
        else :
            for i in range(1,N+1) :
                if i not in Z :
                    colors[nxt] = i
                    Z.append(i)
                    D[str(min(now,nxt))+str(max(now,nxt))] = i
                    q.append(nxt)
                    break

print(res)
for k in D :
    print(D[k])

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit

setrecursionlimit(100000)

N = int(input())

adj = [list() for _ in range(N)]

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

C,s = max((len(l),v) for v,l in enumerate(adj))

res = [None]*(N-1)

def rec(v, used):
    global res
    c = 0
    for u,i in adj[v]:
        if c == used:
            c += 1
        if res[i] is None:
            res[i] = c
            rec(u, c)
        c += 1
rec(s, -1)
print(C)
for c in res:
    print(c+1)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for i in range(N)]
    e_index = []
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
        e_index.append((a,b))
    queue = deque()
    queue.append((0,0))
    ans_col = {}
    visited = set()
    K=1
    while queue:
        from_,col = queue.popleft()
        if from_ in visited:
            continue
        visited.add(from_)
        now = 1
        for to in edge[from_]:
            if to in visited:
                continue
            if now == col:
                now += 1
            ans_col[from_,to] = now
            ans_col[to,from_] = now
            print(from_,to,now)
            queue.append((to,now))
            K = max(now,K)
            now += 1
    print(K)
    for a,b in e_index:
        print(ans_col[a,b])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = rils(n - 1)
edges = collections.defaultdict(list)
for a, b in ls:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = [-1] * n
colors[0] = 0

q = collections.deque()
q.append(0)
while q:
    node = q.popleft()
    c = 1
    for next_ in edges[node]:
        if colors[next_] >= 0:
            continue
        if colors[node] == c:
            c += 1
            colors[next_] = c
        else:
            colors[next_] = c
        c += 1
        q.append(next_)
print(max(colors))
print(*colors[1:], sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[i] = [min(a,b),max(a,b)]
  g[a].append(b)
  g[b].append(a)
m = 0
for i in g:
  m = max(m,len(i))
print(m)
g2 = [set() for i in range(n)]
for i,j in l:
  cur = g2[i]|g2[j]
  for k in range(1,m+1):
    if k in cur:
      continue
    else:
      g2[i].add(k)
      g2[j].add(k)
      print(k)
      break

Submission status: Wrong Answer

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

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

degree_max = max([len(tree[i]) for i in range(n)])
color = [set() for _ in range(n)]
print(degree_max)
for i in range(n - 1):
    for c in range(degree_max):
        if c not in color[edge[i][0]] and c not in color[edge[i][1]]:
            color[edge[i][0]].add(c)
            color[edge[i][1]].add(c)
            print(c + 1)
            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=[[0] for _ in range(n)]
for i in range(n-1):
	a=ab[i][0]
	b=ab[i][1]
	t=max(x[a-1][-1],x[b-1][-1])+1
	if 1<=t<=k:
		x[a-1].append(t)
		x[b-1].append(t)
	else:
		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)
	#print(x)
	print(t)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1<<32|i)
    g[b-1].append(a-1<<32|i)
    # g[a-1].append((b-1, i))
    # g[b-1].append((a-1, i))

def dfs(cur, pre, g, colors):
    skip = colors[pre] if pre != -1 else 0
    gen = 1
    for e in g[cur]:
        if e>>32 != pre:
            if gen == skip:
                gen += 1
            colors[e&(1<<32)-1] = gen
            gen += 1
            dfs(e>>32, cur, g, colors)

colors = [0] * (n-1)
dfs(0, -1, g, colors)

print(max(colors))
for v in colors:
    print(v)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = defaultdict(lambda : -1)
def solve():
    global d
    def dfs(x,pre,k,m):
        global d
        p = 1
        if pre != -1:
            if x < pre:
                d[(x,pre)] = k
            else:
                d[(pre,x)] = k
        for y in v[x]:
            if p == k:
                p += 1
            if m[y]:continue
            m[y] = 1
            dfs(y,x,p,m)
            p += 1
    n = I()
    v = [[] for i in range(n)]
    e = []
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        e.append((a,b))
        f[a] += 1
        f[b] += 1
    if n == 2:
        print(1)
        print(1)
        return
    m = [0]*n
    m[0] = 1
    dfs(0,-1,0,m)
    for x,y in e:
        print(d[(x,y)])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

degree_max = max([len(tree[i]) for i in range(n)])
color = [[] for _ in range(n)]
print(degree_max)
for i in range(n - 1):
    for c in range(degree_max):
        if c not in color[edge[i][0]] and c not in color[edge[i][0]]:
            color[edge[i][0]].append(c)
            color[edge[i][1]].append(c)
            print(c + 1)
            break

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [[] for _ in range(n)]
e=[]
for _ in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    k = 1
    while k in ab[a] or k in ab[b]:
        k += 1
    e.append(k)
    ab[a].append(k)
    ab[b].append(k)
print(max(e))
for i in e:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
b = []
L = [0]*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
    output[j]=max(L[a[j]-1],L[b[j]-1])
    if L[a[j]-1]>L[b[j]-1]:
        L[b[j]-1]-=1
    elif L[a[j]-1]<L[b[j]-1]:
        L[a[j]-1]-=1

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append((b-1, i))
    g[b-1].append((a-1, i))

def dfs(cur, pre, g, colors):
    skip = colors[pre] if pre != -1 else 0
    gen = 1
    for e in g[cur]:
        if e[0] != pre:
            if gen == skip:
                gen += 1
            colors[e[1]] = gen
            gen += 1
            dfs(e[0], cur, g, colors)

colors = [0] * (n-1)
dfs(0, -1, g, colors)

print(max(colors))
for v in colors:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge_to_id = dd(int)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
    edge_to_id[(min(a, b), max((a, b)))] = i

stack = [1]
visited = set()
color_on_node = dd(set)
color_num = max([len(val) for val in tree.values()])
full = set(list(range(1, color_num+1)))
ans = [0] * (n-1)
while stack != []:
    temp = []
    for node in stack:
        colors = full - color_on_node[node]
        for next_node in (tree[node] - visited):
            edge = (min(node, next_node), max(node, next_node))
            for color in colors:
                if color not in color_on_node[next_node]:
                    break
            colors.remove(color)
            """
            else:
                color_num += 1
                color = color_num
            """
            idx = edge_to_id[edge]
            ans[idx] = color
            color_on_node[node].add(color)
            color_on_node[next_node].add(color)
            temp.append(next_node)
        visited.add(node)
    stack = temp

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge_to_id = dd(int)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
    edge_to_id[(min(a, b), max((a, b)))] = i

stack = [1]
visited = set()
color_on_node = dd(set)
color_num = 1
ans = [0] * (n-1)
while stack != []:
    temp = []
    for node in stack:
        for next_node in (tree[node] - visited):
            edge = (min(node, next_node), max(node, next_node))
            for color in range(1, color_num+1):
                if color not in color_on_node[node] and color not in color_on_node[next_node]:
                    break
            else:
                color_num += 1
                color = color_num
            idx = edge_to_id[edge]
            ans[idx] = color
            color_on_node[node].add(color)
            color_on_node[next_node].add(color)
            temp.append(next_node)
        visited.add(node)
    stack = temp

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge_to_id = dd(int)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
    edge_to_id[(min(a, b), max((a, b)))] = i

stack = [1]
visited = set()
color_on_node = dd(set)
color_num = 1
ans = [0] * (n-1)
while stack != []:
    temp = []
    for node in stack:
        for next_node in tree[node]:
            if next_node not in visited:
                edge = (min(node, next_node), max(node, next_node))
                for color in range(1, color_num+1):
                    if color not in color_on_node[node] and color not in color_on_node[next_node]:
                        break
                else:
                    color_num += 1
                    color = color_num
                idx = edge_to_id[edge]
                ans[idx] = color
                color_on_node[node].add(color)
                color_on_node[next_node].add(color)
                temp.append(next_node)
        visited.add(node)
    stack = temp

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n = int(input())
tree = dd(set)
edge_to_id = dd(int)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
    edge_to_id[(min(a, b), max((a, b)))] = i

stack = [1]
visited = set()
color_on_node = dd(set)
color_num = 1
ans = [0] * (n-1)
while stack != []:
    temp = []
    for node in stack:
        for next_node in tree[node]:
            if next_node not in visited:
                edge = (min(node, next_node), max(node, next_node))
                for color in range(1, color_num+1):
                    if color not in color_on_node[node] and color not in color_on_node[next_node]:
                        break
                else:
                    color_num += 1
                    color = color_num
                idx = edge_to_id[edge]
                ans[idx] = color
                color_on_node[node].add(color)
                color_on_node[next_node].add(color)
                temp.append(next_node)
        visited.add(node)
    stack = temp

print(max([len(val) for val in color_on_node.values()]))
for i in range(n-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True
        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True
        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = min(residual)
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)