BFS Trees
We define a spanning tree of a graph to be a BFS tree rooted at vertex $$$s$$$ if and only if for every node $$$t$$$ the shortest distance between $$$s$$$ and $$$t$$$ in the graph is equal to the shortest distance between $$$s$$$ and $$$t$$$ in the spanning tree. Given a graph, we define $$$f(x,y)$$$ to be the number of spanning trees of that graph that are BFS trees rooted at vertices $$$x$$$ and $$$y$$$ at the same time.You are given an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. Calculate $$$f(i,j)$$$ for all $$$i$$$, $$$j$$$ by modulo $$$998\,244\,353$$$.
The following picture describes the first example.The tree with red edges is a BFS tree rooted at both $$$1$$$ and $$$2$$$.Similarly, the BFS tree for other adjacent pairs of vertices can be generated in this way.
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 400$$$, $$$0 \le m \le 600$$$) — the number of vertices and the number of edges in the graph.The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i < b_i$$$), representing an edge connecting $$$a_i$$$ and $$$b_i$$$.It is guaranteed that all edges are distinct and the graph is connected.
Print $$$n$$$ lines, each consisting of $$$n$$$ integers.The integer printed in the row $$$i$$$ and the column $$$j$$$ should be $$$f(i,j) \bmod 998\,244\,353$$$.
import io
import os
from collections import deque

def solve(N, M, edges):
    graph = [[] for i in range(N)]
    for (u, v) in edges:
        graph[u].append(v)
        graph[v].append(u)

    def bfs(source):
        q = deque([source])
        dist = [-1] * N
        dist[source] = 0
        while q:
            node = q.popleft()
            d = dist[node]
            for nbr in graph[node]:
                if dist[nbr] == -1:
                    q.append(nbr)
                    dist[nbr] = d + 1
        return dist
    dists = [bfs(u) for u in range(N)]
    MOD = 998244353
    ans = [[0 for i in range(N)] for j in range(N)]
    for x in range(N):
        for y in range(x, N):
            onPath = 0
            for i in range(N):
                if dists[x][i] + dists[y][i] == dists[x][y]:
                    onPath += 1
            numVertices = dists[x][y] + 1
            ways = 1
            if onPath > numVertices:
                ways = 0
            else:
                for i in range(N):
                    if dists[x][i] + dists[y][i] != dists[x][y]:
                        count = 0
                        for j in graph[i]:
                            if dists[x][i] == dists[x][j] + 1 and dists[y][i] == dists[y][j] + 1:
                                count += 1
                        ways = ways * count % MOD
                        if not ways:
                            break
            ans[x][y] = ways
            ans[y][x] = ways
    return '\n'.join((' '.join(map(str, row)) for row in ans))
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    TC = 1
    for tc in range(1, TC + 1):
        (N, M) = [int(x) for x in input().split()]
        edges = [[int(x) - 1 for x in input().split()] for i in range(M)]
        ans = solve(N, M, edges)
        print(ans)
import os
import sys
from io import BytesIO, IOBase

def main():
    (n, m) = map(int, input().split())
    MOD = 998244353
    adjList = []
    dist = []
    ans = []
    for _ in range(n):
        adjList.append([])
    for _ in range(m):
        (a, b) = map(int, input().split())
        adjList[a - 1].append(b - 1)
        adjList[b - 1].append(a - 1)
    for i in range(n):
        curDist = [-1] * n
        curDist[i] = 0
        bfsQueue = [i]
        bfsIndex = 0
        while len(bfsQueue) > bfsIndex:
            c = bfsQueue[bfsIndex]
            bfsIndex += 1
            for elem in adjList[c]:
                if curDist[elem] == -1:
                    curDist[elem] = curDist[c] + 1
                    bfsQueue.append(elem)
        dist.append(curDist)
    for _ in range(n):
        ans.append([0] * n)
    for i in range(n):
        for j in range(i, n):
            isCovered = [False] * n
            isCovered[i] = True
            isCovered[j] = True
            jCpy = j
            flag = True
            while jCpy != i:
                cnt = 0
                cntIndex = -1
                for elem in adjList[jCpy]:
                    if dist[i][elem] == dist[i][jCpy] - 1:
                        cnt += 1
                        cntIndex = elem
                if cnt >= 2:
                    flag = False
                    break
                else:
                    isCovered[cntIndex] = True
                    jCpy = cntIndex
            if not flag:
                ans[i][j] = 0
                ans[j][i] = 0
            else:
                curAns = 1
                for k in range(n):
                    if isCovered[k]:
                        continue
                    cnt = 0
                    for elem in adjList[k]:
                        if dist[i][elem] == dist[i][k] - 1 and dist[j][elem] == dist[j][k] - 1:
                            cnt += 1
                    curAns *= cnt
                    curAns %= MOD
                ans[i][j] = curAns
                ans[j][i] = curAns
    for elem in ans:
        print(' '.join(map(str, elem)))
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()
import sys, os
from collections import defaultdict, deque
if os.environ['USERNAME'] == 'kissz':
    inp = open('in2.txt', 'r').readline

    def debug(*args):
        print(*args, file=sys.stderr)
else:
    inp = sys.stdin.readline

    def debug(*args):
        pass

def solve():
    (n, m) = map(int, inp().split())
    G = defaultdict(list)
    for i in range(m):
        (u, v) = map(int, inp().split())
        G[u - 1] += [v - 1]
        G[v - 1] += [u - 1]
    combs = [[-1] * n for _ in range(n)]

    def bfs(i):
        Q = deque([i])
        D = [-1] * n
        D[i] = 0
        while Q:
            node = Q.pop()
            for neighbor in G[node]:
                if D[neighbor] == -1:
                    Q.appendleft(neighbor)
                    D[neighbor] = D[node] + 1
        return D
    dists = [bfs(i) for i in range(n)]
    for i in range(n):
        for j in range(i + 1):
            node = j
            failed = False
            while node != i:
                c = 0
                next_node = -1
                for neighbor in G[node]:
                    if dists[i][neighbor] < dists[i][node]:
                        c += 1
                        next_node = neighbor
                if c == 1:
                    node = next_node
                else:
                    failed = True
                    break
            call = 1
            if failed:
                combs[i][j] = combs[j][i] = 0
            else:
                for k in range(n):
                    if dists[i][k] + dists[j][k] > dists[i][j]:
                        c = 0
                        for l in G[k]:
                            if dists[i][l] + 1 == dists[i][k] and dists[j][l] + 1 == dists[j][k]:
                                c += 1
                        call = call * c % 998244353
                combs[i][j] = combs[j][i] = call
    for i in range(n):
        print(*combs[i])
solve()