CF908H.New Year and Boolean Bridges

Your friend has a hidden directed graph with n nodes.

Let f(u, v) be true if there is a directed path from node u to node v, and false otherwise. For each pair of distinct nodes, u, v, you know at least one of the three statements is true:

1. 
2. 
3. 

Here AND, OR and XOR mean AND, OR and exclusive OR operations, respectively.

You are given an n by n matrix saying which one of the three statements holds for each pair of vertices. The entry in the u-th row and v-th column has a single character.

1. If the first statement holds, this is represented by the character 'A'.
2. If the second holds, this is represented by the character 'O'.
3. If the third holds, this is represented by the character 'X'.
4. The diagonal of this matrix will only contain the character '-'.

Note that it is possible that a pair of nodes may satisfy multiple statements, in which case, the character given will represent one of the true statements for that pair. This matrix is also guaranteed to be symmetric.

You would like to know if there is a directed graph that is consistent with this matrix. If it is impossible, print the integer -1. Otherwise, print the minimum number of edges that could be consistent with this information.

你的朋友有一个隐藏的有向图，包含 $n$ 个节点。

令 $f(u, v)$ 表示从节点 $u$ 到节点 $v$ 是否存在一条有向路径：若存在则为真（true），否则为假（false）。对于每一对互异的节点 $u, v$，以下三条陈述中至少有一条为真：

1. 
2. 
3. 

其中 AND、OR 和 XOR 分别表示逻辑与、逻辑或、异或运算。

你被给定一个 $n \times n$ 的矩阵，它指明了每一对顶点 $(u, v)$ 满足上述三条陈述中的哪一条。该矩阵第 $u$ 行第 $v$ 列的元素是一个单字符：

1. 若第一条陈述成立，则用字符 'A' 表示；
2. 若第二条陈述成立，则用字符 'O' 表示；
3. 若第三条陈述成立，则用字符 'X' 表示；
4. 该矩阵的对角线元素（即 $u = v$ 的位置）均固定为字符 '-'。

注意：某一对节点可能同时满足多条陈述，此时矩阵中给出的字符只需代表其中一条成立的陈述即可。此外，该矩阵保证是对称的（即第 $u$ 行第 $v$ 列的字符与第 $v$ 行第 $u$ 列的字符相同）。

你希望判断是否存在一个有向图，使得其可达性函数 $f$ 与该矩阵完全一致。若不存在这样的图，请输出整数 $-1$；否则，请输出满足条件的有向图的最少边数。

The first line will contain an integer n (1 ≤ n ≤ 47), the number of nodes.

The next n lines will contain n characters each: the matrix of what you know about the graph connectivity in the format described in the statement.

第一行包含一个整数 $n$（$1 \leq n \leq 47$），表示节点数量。

接下来的 $n$ 行，每行包含 $n$ 个字符：即题目描述中所述格式的、关于图连通性信息的矩阵。

Print the minimum number of edges that is consistent with the given information, or -1 if it is impossible.

输出与给定信息一致的最少边数；若不可能，则输出 $-1$。

Sample 1: The hidden graph is a strongly connected graph. We can put all four nodes in a cycle.

Sample 2: One valid graph is 3 → 1 → 2. For each distinct pair, exactly one of f(u, v), f(v, u) holds.

样例 1：隐藏图是一个强连通图。我们可以将全部四个节点放入一个环中。

样例 2：一个合法的图是 $3\to 1\to 2$。对于每一对互异的节点 $(u,v)$，$f(u,v)$ 与 $f(v,u)$ 恰好有一个成立。