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

문제

세준이의 나라에는 N개의 도시가 있다. 몇몇 도시들은 양방향 도로로 서로 연결되어 있다. 그리고, 모든 도시는 서로에게 가는 경로가 존재한다.

세준이는 어느날 이렇게 많은 도로를 관리하는 것이 너무 비싸다고 생각했기 때문에, 몇 개의 도로를 폐쇄해 버리려고 한다. 세준이는 되도록 많은 도로를 폐쇄하려고 한다. 그러나, 세준이는 모든 도시가 서로에게 가는 경로가 존재해야 한다고 생각한다.

종점이란 것은 어떤 도시가 단 하나의 도시와 연결되어 있을 때, 종점이라고 한다. 현재 도로가 연결된 상태가 주어질 때, 종점의 개수를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N이 주어진다. N은 15보다 작거나 같다. 둘째 줄부터 N개의 줄에 인접행렬이 주어진다.

출력

종점의 최대 개수를 출력한다.

예제 입력

5
01000
10100
01010
00101
00010

예제 출력

2

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kesakiyo