시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB53013310424.074%

문제

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을 출력한다.

예제 입력 1

5
NYYNN
YNYNN
YYNNN
NNNNY
NNNYN

예제 출력 1

1

예제 입력 2

2
NY
YN

예제 출력 2

0

예제 입력 3

7
NYYNNNN
YNYNNNN
YYNNNNN
NNNNYYN
NNNYNYY
NNNYYNY
NNNNYYN

예제 출력 3

1

예제 입력 4

12
NYNYNNNNNNNN
YNYNNNNNNNNN
NYNYYNNNNNNN
YNYNNNNNNNNN
NNYNNYYNNNNN
NNNNYNYNNNNN
NNNNYYNNNNNN
NNNNNNNNYYNN
NNNNNNNYNYNN
NNNNNNNYYNNN
NNNNNNNNNNNY
NNNNNNNNNNYN

예제 출력 4

2

예제 입력 5

6
NYNNNN
YNYNNN
NYNYNN
NNYNNN
NNNNNY
NNNNYN

예제 출력 5

-1

출처

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: koosaga