← 返回题目列表

Codeforces · 1495/D

D. BFS 树

中文机器翻译题面 查看原题

我们将图的生成树定义为以顶点 $$$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树也可以通过这种方式生成。