CF1495D.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$.

我们定义图的一棵生成树为以顶点 $s$ 为根的 BFS 树，当且仅当对每个顶点 $t$，$s$ 与 $t$ 在原图中的最短距离等于 $s$ 与 $t$ 在该生成树中的最短距离。

给定一个图，我们定义 $f(x,y)$ 为该图中同时是以顶点 $x$ 和顶点 $y$ 为根的 BFS 树的生成树的数量。

你将得到一个包含 $n$ 个顶点和 $m$ 条边的无向连通图。请对所有 $i$、$j$ 计算 $f(i,j)$，结果对 $998\,244\,353$ 取模。

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 \lt b_i$), representing an edge connecting $a_i$ and $b_i$.

It is guaranteed that all edges are distinct and the graph is connected.

第一行包含两个整数 $n$、$m$（$1 \le n \le 400$，$0 \le m \le 600$）—— 分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$，$a_i \lt b_i$），表示一条连接顶点 $a_i$ 和 $b_i$ 的边。

保证所有边互不相同，且该图是连通的。

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$.

输出 $n$ 行，每行包含 $n$ 个整数。

第 $i$ 行第 $j$ 列所输出的整数应为 $f(i,j) \bmod 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.

下图描述了第一个示例。

带红色边的树是一棵以顶点 $1$ 和 $2$ 为根的 BFS 树。

类似地，其他相邻顶点对的 BFS 树也可通过这种方式生成。