我们将图的生成树定义为以顶点 $$$s$$$ 为根的 BFS 树,当且仅当对于每个节点 $$$t$$$,图中 $$$s$$$ 和 $$$t$$$ 之间的最短距离等于生成树中 $$$s$$$ 和 $$$t$$$ 之间的最短距离。
给定一个图,我们将 $$$f(x,y)$$$ 定义为该图的生成树的数量,这些生成树是同时以顶点 $$$x$$$ 和 $$$y$$$ 为根的 BFS 树。
给你一个无向连通图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。通过模 $$$998\,244\,353$$$ 计算所有 $$$i$$$、$$$j$$$ 的 $$$f(i,j)$$$。
输入
第一行包含两个整数 $$$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 < b_i$$$),表示连接 $$$a_i$$$ 和 $$$b_i$$$ 的边。
保证所有边都是不同的并且图是连通的。
输出
打印 $$$n$$$ 行,每行由 $$$n$$$ 整数组成。
在 $$$i$$$ 行和 $$$j$$$ 列中打印的整数应该是 $$$f(i,j) \bmod 998\,244\,353$$$。
示例
输入 #1
4 4 1 2 2 3 3 4 1 4
输出 #1
2 1 0 1 1 2 1 0 0 1 2 1 1 0 1 2
输入 #2
8 9 1 2 1 3 1 4 2 7 3 5 3 6 4 8 2 3 3 4
输出 #2
1 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 1 0 1 1 0 0 0 0 0 2 0 0 0 2 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 2
注意
下图描述了第一个示例。
带有红色边缘的树是一个以 $$$1$$$ 和 $$$2$$$ 为根的 BFS 树。
类似地,其他相邻顶点对的BFS树也可以通过这种方式生成。