Будем говорить, что остовное дерево некоторого графа является деревом поиска в ширину с корнем в вершине \(s\), если и только если для всех вершин \(t\) кратчайшее расстояние между вершинами \(s\) и \(t\) в графе равно кратчайшему расстоянию между \(s\) и \(t\) в этом остовном дереве.
Для фиксированного графа можно определить \(f(x,y)\) как число остовных деревьев в данном графе таких, что они являются деревьями поиска в ширину как с корнем в \(x\), так и с корнем в \(y\).
Вам дан неориентированный связный граф с \(n\) вершинами и \(m\) ребрами. Вычислите \(f(i,j)\) для всех \(i\), \(j\) по модулю \(998\,244\,353\).
Выходные данные
Выведите \(n\) строк, каждая из которых содержит \(n\) целых чисел.
Число в строке \(i\) на позиции \(j\) должно быть равно \(f(i,j) \bmod 998\,244\,353\).
Примечание
Изображения ниже описывают первый пример.
Дерево из красных ребер является деревом поиска в ширину с корнем как в \(1\), так и в \(2\).
Похожим образом можно построить деревья поисков в ширину для любой пары соседних вершин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
2 3
3 4
1 4
|
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
|
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
|