-
핫도그 도난 사건
문제
알고리즘 랩스의 사무실에는 긴장감이 감돌고 있습니다. 많던 핫도그가 어느 날 한순간에 없어진 사실에 경악을 금치 못했습니다. 그 사건의 용의자를 찾으려 했으나 쉽지 않았습니다. 이후 이러한 문제가 재발 하지않기 위해 알고리즘 랩스의 직원들은 각 담당 부서별 움직임을 파악할 수 있는 카메라를 만들어 설치를 하는 것이 좋겠다고 합의했습니다. 카메라가 설치되면 직원들의 움직임이 파악되어 냉장고의 음식을 한 사람이 독차지하는 것이 아닌 모두가 즐길 수 있게 될 것이라 믿었습니다. 카메라를 만드는 비용과 시간이 적지않게 들 것으로 예상되어 이를 절감하기 위해 개발팀은 최소한의 카메라로 사무실 인원의 움직임을 파악할 수 있도록 사무실 구조를 파악해야된다고 말했습니다.
알고리즘 랩스의 여러 부서는 직접적인 벽으로 나눠져있지않지만 보이지 않는 길을 만들어서 구분되어있습니다. 한 부서에 카메라가 설치되면 바로 옆에 있는 부서들까지 녹화할 수 있다고 합니다. 모든 부서들의 인원 움직임을 파악하기 위해서는 최소 몇 개의 카메라가 필요할까요? 입구에서 먼 부서를 가기 위해서는 여러 부서들을 통과해서 지나가야합니다. 또한 부서들이 모두 연결되어 있지 않을 수도 있습니다.
입력
첫 줄에는 알고리즘 랩스에 존재하는 부서의 수 D (1 <= D <= 1000) 와 각 부서 사이에 존재하는 보이지않는 통로의 수 P (0 <= P < D) 가 주어집니다. 각 부서는 편의상 0번부터 D-1 번으로 부릅니다. 두 번째 줄부터 각 줄에 부서들의 연결 상태가 주어집니다.
출력
한 줄에 필요한 최소 카메라 개수를 출력합니다.
예제 입력 1
6 5 0 1 1 2 1 3 2 5 0 4예제 출력 1
3예제 입력 2
4 2 0 1 2 3예제 출력 2
2예제 입력 3
1000 1 0 1예제 출력 3
999