시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 45 10 10 37.037%

문제

N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이 때, 도로를 수정하는 회수를 최소로 하려고 한다. 도로를 수정하는 방법은 다음과 같다.

1. A와 B가 연결되어 있고, C와 D가 연결되어 있으면서, A와 C, A와 D, B와 C, B와 D가 연결되어 있지 않은 4개의 도시 A, B, C, D를 선택한다.

2. A와 B를 연결하는 도로와 C와 D를 연결하는 도로를 없앤다.

3. A와 C, B와 D를 연결하거나 A와 D, B와 C를 연결한다.

다음 그림을 살펴보자.
 

위와 같은 도로가 있을 때 이것을 다음에 보이는 둘 중에 하나로 바꿀 수 있다.

N이 주어지고, 각 도로의 정보가 주어진다. 이 때, 몇 개의 도로를 수정해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다 N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 도로의 정보가 주어진다. 인접행렬형식으로 표현되어 있다. 예제를 보면 된다. g[i][j] = g[j][i]이고, g[i][i] = N이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능  할 때는 -1을 출력한다.

예제 입력

5
NYYNN
YNYNN
YYNNN
NNNNY
NNNYN

예제 출력

1

힌트

출처