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: Time Limit Exceeded

Solution code:

N = int(input())
A = [[-1 for j in range(N+1)] for i in range(N+1)]
ans = [-1 for i in range(N-1)]
edges = [[] for i in range(N+1)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a,i))
 
def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1
 
  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"
 
    next = 1
    for (v, i) in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        ans[i] = next
        next += 1
  
  return mcolor
 
print(dfs(root))
 
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

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

def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"

    next = 1
    for v in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(root))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

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

def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"

    next = 1
    for v in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

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

def dfs(u):
  visited = set()
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited.add(u)

    next = 1
    for v in edges[u]:
      if v != p and v not in visited:
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

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

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()

    next = 1
    for v in edges[u]:
      if v != p and v not in visited:
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        visited.add(v)
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]
colors = [set() for i in range(N+1)]

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

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [(u, -1)]
  mcolor = -1

  while stack:
    u, p = stack.pop()
  
    for v in edges[u]:
      if v != p and v not in visited:
        c = colors[u] | colors[v]
        next = 1
        while next in c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        colors[u].add(next)
        colors[v].add(next)
        visited.add(v)
        stack.append((v, u))
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]
colors = [set() for i in range(N+1)]

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

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [u]
  mcolor = -1

  while stack:
    u = stack.pop()
  
    for v in edges[u]:
      if v not in visited:
        c = colors[u] | colors[v]
        next = 1
        while next in c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        colors[u].add(next)
        colors[v].add(next)
        visited.add(v)
        stack.append(v)
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]
colors = [[] for i in range(N+1)]

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

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [u]
  mcolor = -1

  while stack:
    u = stack.pop()
  
    for v in edges[u]:
      if v not in visited:
        c = colors[u] + colors[v]
        next = 1
        while next in c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        colors[u].append(next)
        colors[v].append(next)
        visited.add(v)
        stack.append(v)
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    y = G[x]
    k = D[x] + 1
    if k > K:
        k -= K
    while y:
        z = y.pop(0)
        if z not in list:
            if z not in sumi:
                list.append(z)
                d[(x,z)] = k
                D[z] = k
                k += 1
                if k > K:
                    k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    y = G[x]
    k = D[x] + 1
    if k > K:
        k -= K
    while y:
        z = y.pop(0)
        if z not in list:
            if z not in sumi:
                list.append(z)
                d[(x,z)] = k
                D[z] = k
                k += 1
                if k > K:
                    k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
C = [[i for i in range(1,K+1)] for j in range(N+1)]
import copy 
w = copy.deepcopy(W)
d = {}
w.sort()
for i in range(N-1):
    a,b = w[i]
    x = C[a].pop(0)
    C[b].remove(x)
    d[a+b*N] = x
for i in range(N-1):
    a,b = W[i]
    print(d[a+b*N])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
#COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])
while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[na][nb] == None:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[na][nb] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(COLOR[a][b])

print("\n".join(map(str, clr)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])
while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


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

while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(str(COLOR[(a, b)]))

print("\n".join(clr))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


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

while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

for a, b in PATH:
    print(COLOR[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
#COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)


q = deque([(1, 0)])
cmax = 1
while(q):
    a, ca = q.popleft()
    bs = PT[a]

    if len(bs) > cmax:
        cmax = len(bs)

    c = list(range(1, cmax+1))
    for b in bs:
        if COLOR[a][b] != None:
            continue

        clr = c.pop()
        if clr == ca:
            clr = c.pop()
        COLOR[a][b] = clr
        COLOR[b][a] = clr
        q.append((b, clr))

print(cmax)

for a, b in PATH:
    print(COLOR[a][b])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
#COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)


q = deque([1])
cmax = 1
while(q):
    # print(q)
    a = q.popleft()
    bs = PT[a]

    if len(bs) > cmax:
        cmax = len(bs)

    c = list(range(1, cmax+1))
    for b in bs:
        #print("a", a, "b", b)
        # print(COLOR[a][b])
        if COLOR[a][b] != None:
            c.remove(COLOR[a][b])

    for b in bs:
        if COLOR[a][b] != None:
            continue

        clr = c.pop()
        COLOR[a][b] = clr
        COLOR[b][a] = clr
        q.append(b)

print(cmax)

for a, b in PATH:
    print(COLOR[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node,max_val=0):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

max_val = bfs(0)
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
ans = []
for a, b in input_list:
    ans.append(visited_edge[a][b])
max_val = 0
for row in visited_edge:
    row.sort()
    tmp_max = row[-1]
    if tmp_max > max_val:
        max_val = tmp_max
print(max_val)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
ans = []
for a, b in input_list:
    ans.append(visited_edge[a][b])
max_val = 0
for row in visited_edge:
    row = list(map(lambda x: -1 * x, row))
    heapq.heapify(row)
    tmp_max = heapq.heappop(row) * (-1)
    if tmp_max > max_val:
        max_val = tmp_max
print(max_val)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
max_val = 0
for row in visited_edge:
    tmp_max = max(row)
    if max_val < tmp_max:
        max_val = tmp_max
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)

# print(tree)

# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.popleft()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] == 0:
                if now_color != before_color:
                    visited_edge[now_node][next_node] = now_color
                    visited_edge[next_node][now_node] = now_color
                else:
                    now_color += 1
                    visited_edge[next_node][now_node] = now_color
                    visited_edge[now_node][next_node] = now_color
                # print("next_node : ",next_node)
                # print("before_color : ",before_color)
                queue.append([tree[next_node], now_color, next_node])
                now_color += 1

bfs(0)
max_val = 0
for row in visited_edge:
    tmp_max = max(row)
    if max_val < tmp_max:
        max_val = tmp_max
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

Submission status: Time Limit Exceeded

Solution code:
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append(sorted([a, b]))
    tree[a].append(b)
    tree[b].append(a)

# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]
dict = {}

# bfsによる色付けを行う
def bfs(now_node):
    queue = [[tree[now_node], 0, now_node]]
    while queue:
        next_nodes, before_color, now_node = queue.pop(0)
        now_color = 1

        for next_node in next_nodes:
            if dict.get(tuple(sorted([now_node, next_node]))) is None:
                # if now_color != before_color:
                #     dict[tuple(sorted([now_node, next_node]))] = now_color
                #     visited_edge[now_node][next_node] = now_color
                #     visited_edge[next_node][now_node] = now_color
                # else:
                #     now_color += 1
                #     visited_edge[next_node][now_node] = now_color
                #     visited_edge[now_node][next_node] = now_color
                if now_color == before_color:
                    now_color += 1
                dict[tuple(sorted([now_node, next_node]))] = now_color
                queue.append([tree[next_node], now_color, next_node])
                now_color += 1


bfs(0)

# 出力
# max_val = 0
# for row in visited_edge:
#     tmp_max = max(row)
#     if max_val < tmp_max:
#         max_val = tmp_max
# print(max_val)
# for a, b in input_list:
#     print(visited_edge[a][b])

print(max(dict.values()))
for val in input_list:
    print(dict[tuple(val)])

Submission status: Time Limit Exceeded

Solution code:
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)

# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = [[tree[now_node], 0, now_node]]
    while queue:
        next_nodes, before_color, now_node = queue.pop(0)
        now_color = 1
        for next_node in next_nodes:
            if not visited_edge[now_node][next_node]:
                if now_color != before_color:
                    visited_edge[now_node][next_node] = now_color
                    visited_edge[next_node][now_node] = now_color
                else:
                    now_color += 1
                    visited_edge[next_node][now_node] = now_color
                    visited_edge[now_node][next_node] = now_color
                queue.append([tree[next_node], now_color, next_node])
                now_color += 1


bfs(0)
max_val = 0
for row in visited_edge:
    tmp_max = max(row)
    if max_val < tmp_max:
        max_val = tmp_max
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

Submission status: Time Limit Exceeded

Solution code:
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)

# print(tree)

# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]

# print(visited_edge)
# bfsによる色付けを行う
def bfs(now_node):
    queue = [[tree[now_node], 0, now_node]]
    while queue:
        next_nodes, before_color, now_node = queue.pop(0)
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] == 0:
                if now_color != before_color:
                    visited_edge[now_node][next_node] = now_color
                    visited_edge[next_node][now_node] = now_color
                else:
                    now_color += 1
                    visited_edge[next_node][now_node] = now_color
                    visited_edge[now_node][next_node] = now_color
                # print("next_node : ",next_node)
                # print("before_color : ",before_color)
                queue.append([tree[next_node], now_color, next_node])
                now_color += 1


# for i in range(N - 1):
#     if len(tree[i]) == 1:
#         start = i
#         break

# for i in tree[0]:
#     visited_edge[0][i] = 1
bfs(0)
# print(visited_edge)
# print(max(visited_edge))
max_val = 0
for row in visited_edge:
    tmp_max = max(row)
    if max_val < tmp_max:
        max_val = tmp_max
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

Submission status: Time Limit Exceeded

Solution code:
# for sure, need num colours at least as much as
# the num connections of any node
# maybe that is enough for a tree?

class Node:
    def __init__(self, index, in_colour):
        self.child_list = list()
        self.index = index
        self.in_colour = in_colour


def assign_children(current_node, list_edges, num_colours):
    colour = current_node.in_colour
    for edge in list_edges:
        edge_index = edge[0]-1
        if edge_index == current_node.index:
            colour = (colour + 1)%num_colours
            new_node = Node(edge[1]-1, colour)
            current_node.child_list.append(new_node)
            assign_children(new_node, list_edges, num_colours)


def get_list_colours(current_node, list_colours):
    for child in current_node.child_list:
        list_colours[child.index-1] = child.in_colour
        get_list_colours(child, list_colours)


def convert_order(converted, list_edges, list_colours):
    for idx, edge in enumerate(list_edges):
        edge_in_index = edge[1]-2
        converted[idx] = list_colours[edge_in_index]


def get_num_connections(node, list_edges):
    count_connections = 0
    for i, j in list_edges:
        if i == node or j == node: count_connections += 1
    return count_connections


def get_least_num_colours(num_vertices, list_edges):
    max_needed_colours=0
    for node in range(num_vertices):
        colours = get_num_connections(node, list_edges)
        max_needed_colours = max(max_needed_colours, colours)
    return max_needed_colours


if __name__ == "__main__":
    test1 = \
"""3
1 2
2 3"""
    test2 = \
"""8
1 2
2 3
2 4
2 5
4 7
5 6
6 8"""
    test3 = \
"""6
1 2
1 3
1 4
1 5
1 6"""
    customtest1 = \
"""5
1 2
1 3
3 4
1 5"""
    """current_test = test1
    lines = current_test.split("\n")
    num_vertices = int(lines.pop(0))
    list_edges = [list(map(int, line.split())) for line in lines]"""
    num_vertices = int(input())
    list_edges = list()
    for _ in range(num_vertices-1):
        list_edges.append(list(map(int, input().split())))

    num_colours = get_least_num_colours(num_vertices, list_edges)
    print(num_colours)
    # create tree recursively, assigning a colour for the in-edge of each node
    root = Node(0, -1)
    assign_children(root, list_edges, num_colours)

    # now tree is created, need to output the colours of each edge
    list_colours = [-1]*(num_vertices-1)
    get_list_colours(root, list_colours)
    # list_colours is the colours in order of node from 2 to...
    # but the required output is in order of the edges that were input
    # so, need to convert
    converted = [-1]*(num_vertices-1)
    convert_order(converted, list_edges, list_colours)
    # also seems like all colour values should be 1 or over
    [print(str(value+1)) for value in converted]

Submission status: Time Limit Exceeded

Solution code:
from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=deque(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                colar.appendleft(ckamo)
                ckamo=colar.pop()
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])