Ratsun reitit

import time
from collections import deque

n = int(input())

d = {}
dx = [1,2,-1,-2,1,2,-1,-2]
dy = [2,1,2,1,-2,-1,-2,-1]

timenow = time.perf_counter()

for y in range(n):
    for x in range(n):
        for z in range(8):
            if x+dx[z] >= 0 and y+dy[z] >= 0 and x+dx[z] < n and y+dy[z] < n:
                if f"{x},{y}" in d:
                    d[f"{x},{y}"].append(f"{x+dx[z]},{y+dy[z]}")
                else:
                    d[f"{x},{y}"] = [f"{x+dx[z]},{y+dy[z]}"]

def bfs(graph, start, end):
    queue = deque([(start,0)])
    seen = set()
    while queue:
        node, distance = queue.popleft()
        if node in seen:
            continue
        seen.add(node)
        if node == end:
            return distance
        for adjacent in graph.get(node, []):
            queue.append((adjacent, distance+1))
                
table = [[bfs(d, f"{str(x)},{str(y)}", "0,0") for y in range(n)] for x in range(n)]

resulttime = f"({round(time.perf_counter()-timenow,4)}s)"
"""
for y in range(n):
    for x in range(n):
        print(d[str(x)+","+str(y)])
"""
for x in table:
    print(*x, sep=" ")
    
#print("\nDone!",resulttime)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED