도로 그래프 연결하기

N개의 도시가 있는 나라가 있다. 몇몇 도시 쌍은 양방향 도로로 연결되어 있다. 은진이는 도로 몇 개를 수정해서 모든 도시가 서로 연결되도록 만들고 싶다. 이때 도로를 수정하는 횟수를 최소로 하려고 한다.

도로 한 번의 수정은 다음과 같이 한다.

1. A와 B가 도로로 연결되어 있고, C와 D도 도로로 연결되어 있으며, A-C, A-D, B-C, B-D 사이에는 도로가 없는 네 도시 A, B, C, D를 고른다.
2. A-B 도로와 C-D 도로를 없앤다.
3. A-C와 B-D를 연결하거나, A-D와 B-C를 연결한다.

N과 도로 정보가 주어졌을 때, 필요한 도로 수정 횟수의 최솟값을 구하라.

첫째 줄에 N이 주어진다. N은 50 이하인 자연수이다.

둘째 줄부터 N개의 줄에 도로 정보가 인접 행렬 형태로 주어진다. i행 j열의 문자가 Y이면 도시 i와 도시 j가 도로로 연결되어 있고, N이면 연결되어 있지 않다. 행렬은 대칭이므로 g[i][j] = g[j][i]이고, 모든 대각 원소는 N이다.

도로 수정 횟수의 최솟값을 출력한다. 불가능하면 -1을 출력한다.