你的朋友有一个有 n 个节点的隐藏有向图。
如果存在从节点 u 到节点 v 的有向路径,则令 f(u, v) 为真,否则为假。对于每对不同的节点 u、v,您知道以下三个陈述中至少有一个为真:
1. $$f(u,v) \text{ AND } f(v,u)$$
2. $$f(u,v) \text{ 或 } f(v,u)$$
3. $$f(u,v) \text{ 异或 } f(v,u)$$
这里AND、OR和XOR分别表示AND、OR和异或运算。
给定一个 n × n 矩阵,说明对于每对顶点,三个语句中的哪一个成立。第 u 行第 v 列中的条目有一个字符。
1. 如果第一个语句成立,则由字符“A”表示。
2. 如果第二个成立,则用字符“O”表示。
3. 如果第三个成立,则用字符“X”表示。
4. 该矩阵的对角线仅包含字符“-”。
请注意,一对节点可能满足多个语句,在这种情况下,给定的字符将代表该对的真实语句之一。该矩阵也保证是对称的。
您想知道是否存在与该矩阵一致的有向图。如果不可能,则打印整数-1。否则,打印与此信息一致的最小边数。
输入
第一行将包含一个整数 n (1 ≤ n ≤ 47),即节点数。
接下来的 n 行每行将包含 n 个字符:以语句中描述的格式表示您所了解的图形连通性的矩阵。
输出
打印与给定信息一致的最小边数,如果不可能则打印-1。
示例
输入 #1
4 -AAA A-AA AA-A AAA-
输出 #1
4
输入 #2
3 -XX X-X XX-
输出 #2
2
注意
示例 1:隐藏图是强连通图。我们可以将所有四个节点放在一个循环中。
示例 2:一个有效图为 3 → 1 → 2。对于每一对不同的图,f(u, v)、f(v, u) 中恰好有一个成立。