一道挺有意思的题，并且感觉有点诈骗的成分在内（
首先考虑分析三种字符的性质：
- 显然任意两点 \(i,j\) 之间要么 \(i\) 可以到达 \(j\)，要么 \(j\) 可以到达 \(i\)，否则 A O X 三个一个都不能满足。
- 如果两点间的状态是 A，那么这两点必须在同一强连通分量内。
- 如果两点间的状态是 X，那么这两点必须不能在同一强连通分量内。
- 如果两点间的状态是 O，那么只要满足第一点的大前提，这两点就符合条件。
显然 A 描述的是一个传递闭包关系。因此先用并查集维护一波必须在同一强连通分量的点集，如果一个等价类中存在两点间的状态为 X，那么答案显然 \(-1\)，先判掉这一种 trivial 的情况。
先考虑如果我们确定了强连通分量的划分情况，如何求解答案，显然对于每个 \(siz\ge 2\) 的强连通分量我们只用用 \(siz\) 条边连成一个环，而为了满足条件一的大前提，我们还需要 \(\text{强连通分量个数}-1\) 条边将它们连成一颗树，加起来发现是 \(n-1+\text{大小大于等于 2 的强连通分量个数}\)，因此我们只需要最小化后者即可。
考虑如何求解这种情况。显然对 A 进行连边之后，大小为 \(1\) 的强连通分量就不用管它了，剩下 \(\ge 2\) 的强连通分量个数最多只有 \(23\) 个，刚好可以状压。考虑 X 的限制描述的什么——等价于一些强连通分量不能和别的强连通分量合并，我们先预处理 \(ok_S\) 表示 \(S\) 中的强连通分量是否能合并成一个大强连通分量——这显然有 trivial 的 \(2^{23}\) 的处理。由于答案不会很大，因此考虑最优化转计数，即设 \(dp_{i,S}\) 表示将 \(S\) 中的强连通分量划分成 \(i\) 个大强连通分量的方案数，这样有转移 \(dp_{i,S}=\sum\limits_{S_1\cup S_2=S,S_1\cap S_2=\varnothing}dp_{i-1,S_1}·ok_{S_2}\)。这样看似要子集卷积，\(2^{23}·23^2\) 似乎是似了，但是我们冷静一波，其实 \(S_1\cup S_2=\varnothing\) 这个条件是不必要的，因为如果一个集合的 \(dp_{i,S}>0\)，那么其任意子集的 \(dp_{i,S}\) 也是 \(>0\) 的，因此只用异或卷积即可。对 \(ok\) 数组 FWTor，然后 \(dp_{j,2^m-1}=\sum\limits_{i=0}^{2^m-1}ok_i^j(-1)^{m-\text{popcount}(i)}\)，这样复杂度少了个 \(23\)，就稳了。
const int MAXN=47;
const int MAXP=1<<23;
int n,m,f[MAXN+5],siz[MAXN+5],id[MAXN+5];char s[MAXN+5][MAXN+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x^y)f[x]=y,siz[y]+=siz[x];}
int lg[MAXP+5],coef[MAXP+5],ban[MAXP+5];
ll ok0[MAXP+5],dp[MAXP+5],v[MAXP+5];
int main(){
for(int i=1;i<=23;i++)lg[1<<i]=i;
scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)siz[i]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(s[i][j]=='A')merge(i,j);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(s[i][j]=='X'&&find(i)==find(j))return puts("-1"),0;
for(int i=1;i<=n;i++)if(siz[i]>=2&&find(i)==i)id[i]=++m;
if(!m)return printf("%d\n",n-1),0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(s[i][j]=='X'){
int fi=find(i),fj=find(j);
if(siz[fi]>=2&&siz[fj]>=2)ban[id[fi]]|=(1<<id[fj]-1);
}
ok0[0]=1;
for(int i=1;i<(1<<m);i++){
int lw=lg[i&(-i)]+1;
ok0[i]=ok0[i&(i-1)]&((ban[lw]&i)==0);
}
if(ok0[(1<<m)-1])return printf("%d\n",n),0;
for(int i=0;i<m;i++)for(int j=0;j<(1<<m);j++)if(j>>i&1)ok0[j]+=ok0[j^(1<<i)];
for(int i=0;i<(1<<m);i++)dp[i]=ok0[i];
for(int i=0;i<(1<<m);i++)coef[i]=((m-__builtin_popcount(i))&1)?-1:1;
int res=n;
while(1){
res++;
for(int i=0;i<(1<<m);i++)dp[i]*=ok0[i];
ll sum=0;for(int i=0;i<(1<<m);i++)sum+=dp[i]*coef[i];
if(sum)return printf("%lld\n",res),0;
}
return 0;
}
/*
4
-AXX
A-XX
XX-A
XXA-
*/