← 返回题目列表

Codeforces · 1268/D

D. 锦标赛中的反转

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

您将获得一场锦标赛 - 完整的有向图。

在一项操作中,您可以选取任何顶点 $$$v$$$ 并在一端使用 $$$v$$$ 更改所有边的方向(即所有边 $$$u \to v$$$ 将其方向更改为 $$$v \to u$$$,反之亦然)。

如果可能的话,您希望通过尽可能少的此类操作使锦标赛紧密相连。

另外,如果可能的话,您需要找到使该数量的操作使图强连通的方法数量(如果对于我们在第 $$$i$$$ 操作中以一种方式选择的某个 $$$i$$$ 顶点与我们在第 $$$i$$$ 操作中以另一种方式选择的顶点不同,则两种方法是不同的)。您只需找到该值对 $$$998\,244\,353$$$ 取模即可。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2000$$$):锦标赛中的顶点数。

接下来的 $$$n$$$ 行包含给定锦标赛的描述,每行都包含长度为 $$$n$$$ 的二进制字符串。如果第 $$$i$$$ 字符串的第 $$$j$$$ 个字符等于“1”,则该图有一条边 $$$i \to j$$$。

保证不存在边 $$$i \to i$$$,并且对于不同的 $$$i$$$ 和 $$$j$$$,图在 $$$i \to j$$$ 和 $$$j \to i$$$ 之间恰好有一条边。

输出

如果无法通过给定操作将锦标赛转换为强连接,则输出“-1”。

否则,输出两个整数:使给定图强连通所需的最小操作数以及执行此操作数以使图强连通的方法数,模 $$$998\,244\,353$$$。

示例

输入 #1

3
010
001
100

输出 #1

0 1

输入 #2

4
0010
1000
0100
1110

输出 #2

-1

输入 #3

6
010000
001000
100000
111001
111100
111010

输出 #3

2 18