这说明你那破子集卷积不是万能的。
显然题目要求的图 \(G'\) 是弱联通的，考虑给出的图 \(G\) 中两个点 \(i,j\) 之间 \(G_{i,j}\) 的条件转化为：
- \(G_{i,j}=\mathtt A\)，说明 \(i\) 能到 \(j\) 且 \(j\) 能到 \(i\)，则 \(i,j\) 在 \(G'\) 的同一个强连通分量中。
- \(G_{i,j}=\mathtt O\)，说明 \(i\) 能到 \(j\) 或者 \(j\) 能到 \(i\)，由于 \(G_{i,j}=\mathtt A/\mathtt X\) 是严格强于这个限制的，所以可以转换为 \(G'\) 中任意两点 \(u,v\) 之间至少存在一条路径从 \(u\) 到 \(v\) 或从 \(v\) 到 \(u\)。
- \(G_{i,j}=\mathtt X\)，说明只能从 \(i\) 到 \(j\) 或从 \(j\) 到 \(i\)，这要求 \(i,j\) 不在 \(G'\) 的同一个强连通分量中。
考虑仅由 \(\mathtt A\) 边构成的极大导出子图 \(G_\mathtt A\subseteq G\)，显然图 \(G_\mathtt A\) 中同一个弱连通块内的任意两点 \(u,v\) 在图 \(G'\) 中强连通，于是如果 \(G_{u,v}=\mathtt X\) 就矛盾了，先判掉这种情况，答案为 \(-1\)。
否则的话必然有解，存在一种构造：考虑 \(G_{\mathtt A}\) 中的某个大小 \(\ge 2\) 的弱联通块，将内部的点拿出来，在 \(G'\) 中单独组成一个环；然后 \(G'\) 中就变成了若干个环加上若干孤立点，把它们串成一条链即可满足所有 \(\mathtt O\) 边的性质。
于是每个环（\(G_{\mathtt A}\) 中的弱连通块） \(C\) 内部有 \(|V_C|\) 条边，然后会连出去一条边；每个孤立点连出去一条边；最后有一个部分不用连出去边。设环集合为 \(\operatorname{cyc}\)，那么总边数就是 \(\sum\limits_{C\in \operatorname {cyc}}(|V_C|+1)+(n-\sum|V_C|)-1=n-1+|\operatorname{cyc}|\)。
但是我们发现图 \(G_{\mathtt A}\) 中的两个大小 \(\ge 2\) 的弱联通块是可以合并的，因为两个弱联通块内的点在 \(G'\) 中可以属于同一个强连通分量，那么 \(|\operatorname{cyc}|\) 就会减少 \(1\)，边数就会变少。所以我们希望能够合并尽可能多的弱连通块，使得最后弱联通块总数最少。注意到 \(G_{u,v}=\mathtt X\) 的限制相当于 \(u\) 所在的弱联通块不能和 \(v\) 所在的弱连通块合并。
由于我们考虑的弱联通块大小 \(\ge 2\)，所以弱联通块数 \(m\le\frac{n}{2}\le 23\)。考虑状压 dp，\(f_{i,S}\) 表示能否将弱联通块集合 \(S\) 全部合并成 \(i\) 个块。那么 \(\text{ans}=n-1+\min\limits_{f_{i,U}=1}i\)，\(U\) 为弱联通块全集。
首先 \(f_{1,S}\) 是易求的，预处理 \(w_i\) 表示第 \(i\) 个弱联通块不能合并的弱联通块集合即可。然后考虑判定性问题转计数问题，\(f_{i,S}\) 表示合并方案数，对于 \(i\ge 2\)：
不难发现这就是个子集卷积，但是复杂度 \(O(m^32^m)\)，拿头跑都过不了。但是由于我们不关心 \(f_{i,S}\) 的具体值，对同一个方案可以算重，而且若 \(f_{i,S}\neq 0\) 必然有 \(f_{i,T}\neq 0,T\subseteq S\)。所以我们就可以直接把 \(S_1\cap S_2=\varnothing\) 的限制去掉了。最后相当于一个或卷积，复杂度 \(O(m^22^m)\)，好像已经可以过了，但是能做到更优。
考虑到进行 FWT 或变换（高维前缀和）后 \([x^S]\operatorname{FWT}(F_{i-1})\) 到 \([x^S]\operatorname{FWT}(F_{i})\) 的转移系数固定为 \([x^S]\operatorname{FWT}(F_1)\)，于是我们可以预先求出 \(f_{1}\) 的集合幂级数 \(F_1\) 后进行 FWT，于是 \([x^S]\text{FWT}(F_{i})=([x^S]\operatorname{FWT}(F_1))^i\)。
最后的问题就是如何求出 \([x^U]F_i\)。根据高维前缀和的性质有：
子集反演得：
所以：
可以 \(O(2^m)\) 求出，而 \(i\) 的上界为 \(m\)，所以复杂度就是 \(O(m2^m)\)。
// Problem: New Year and Boolean Bridges
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF908H
// Memory Limit: 500 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int N = 50;
const int T = (1 << 23) + 100;
int n, m, S, fa[N], sz[N], w[N], id[N];
ll op[T], f[T], c[T];
char s[N][N];
int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
void mrg(int x, int y) {
if ((x = gf(x)) == (y = gf(y))) return;
fa[x] = y, sz[y] += sz[x];
}
void FWT(ll *f) {
for (int o = 2, k = 1; o <= S; o <<= 1, k <<= 1)
for (int i = 0; i < S; i += o)
for (int j = 0; j < k; j++)
f[i + j + k] += f[i + j];
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) sz[fa[i] = i] = 1;
for (int i = 1; i <= n; i++) {
cin >> (s[i] + 1);
for (int j = 1; j < i; j++)
if (s[i][j] == 'A') mrg(i, j);
}
for (int i = 1; i <= n; i++) {
if (gf(i) == i && sz[i] >= 2) id[i] = ++m;
id[i] = id[gf(i)];
}
if (!m) return cout << n - 1 << '\n', void();
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (s[i][j] == 'X') {
if (id[i] && id[i] == id[j]) return cout << -1 << '\n', void();
else if (id[i] && id[j]) w[id[i]] |= (1 << id[j] - 1), w[id[j]] |= (1 << id[i] - 1);
}
}
}
S = (1 << m), op[0] = 1;
for (int i = 1; i < S; i++) {
int j = __lg(i & -i);
op[i] = op[i ^ (1 << j)] & (!(w[j + 1] & (i ^ (1 << j))));
}
if (op[S - 1]) return cout << n << '\n', void();
FWT(op), memcpy(f, op, sizeof(ll) * (S + 5));
for (int i = 0; i < S; i++) c[i] = (m - __builtin_popcount(i) & 1) ? -1 : 1;
for (int r = 2; ; r++) {
ll res = 0;
for (int i = 0; i < S; i++) f[i] *= op[i], res += f[i] * c[i];
if (res) return cout << n - 1 + r << '\n', void();
}
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}