New Year and Boolean Bridges

당신의 친구는 n개의 노드를 가진 숨겨진 유향 그래프를 가지고 있다.

노드 u에서 노드 v로 가는 유향 경로가 있으면 f(u, v)는 참이고, 그렇지 않으면 거짓이다. 서로 다른 각 노드 쌍 u, v에 대해, 다음 세 명제 중 적어도 하나가 참임을 알고 있다:

Here AND, OR and XOR은 각각 AND, OR 및 배타적 OR 연산을 의미한다.

각 정점 쌍에 대해 세 명제 중 어느 것이 성립하는지를 나타내는 n행 n열 행렬이 주어진다. u-th 행과 v-th 열의 원소에는 문자 하나가 들어 있다.

1. 첫 번째 명제가 성립하면 문자 'A'로 나타낸다.
2. 두 번째 명제가 성립하면 문자 'O'로 나타낸다.
3. 세 번째 명제가 성립하면 문자 'X'로 나타낸다.
4. 이 행렬의 대각선에는 문자 '-'만 들어 있다.

하나의 노드 쌍이 여러 명제를 만족할 수도 있으며, 이 경우 주어진 문자는 그 쌍에 대해 참인 명제 중 하나를 나타낸다는 점에 유의한다. 또한 이 행렬은 대칭임이 보장된다.

이 행렬과 일치하는 유향 그래프가 존재하는지 알고자 한다. 불가능하면 정수 -1을 출력한다. 그렇지 않으면 이 정보와 일치할 수 있는 최소 간선 수를 출력한다.

첫 번째 줄에는 노드의 수를 나타내는 정수 n (1 ≤ n ≤ 47)이 주어진다.

다음 n개의 줄에는 각각 n개의 문자가 주어지며, 이는 문제에서 설명한 형식으로 그래프의 연결성에 관해 알고 있는 내용을 나타내는 행렬이다.

주어진 정보와 일치하는 최소 간선 수를 출력하고, 불가능하면 -1을 출력한다.

예제 1: 숨겨진 그래프는 강하게 연결된 그래프이다. 네 노드를 모두 하나의 사이클에 배치할 수 있다.

예제 2: 가능한 그래프 중 하나는 3 → 1 → 2이다. 서로 다른 각 노드 쌍에 대해 f(u, v)와 f(v, u) 중 정확히 하나가 성립한다.