N * N 크기 지도의 서로 다른 위치에 M 명의 죄수들이 있다. 이 죄수들을 무사히 밖으로 탈출시키고자 한다. 죄수들의 탈출은 , 지도의 맨 가장자리로 이동시키는 것을 의미한다. 각 죄수들은 동,서,남,북 어느 쪽이든 이동할 수 있지만 , 다른 죄수들이 거쳤던 곳으로는 움직이지 못한다.

N=6 이고 M=10 일 때 죄수들을 탈출시키는 방법의 예이다. 모든 죄수들을 각자의 경로로 무사히 (맨 가장자리로) 탈출 시켰다. 입력데이터가 주어질 때 모든 죄수들을 탈출 시키는 것이 가능한지 불가능한지를 검사하는 프로그램을 작성하라.

입력 방법

• 첫 줄에는 지도의 크기 N(10 이하의 정수), 죄수들의 수(100 이하의 정수)가 주어진다.
• 둘째 줄부터는 각 죄수들의 위치가 주어진다.

출력 방법

입력과 출력의 예

입력

6 11
0 0 0 0 0 0
0 1 0 1 0 1
1 1 0 1 1 1
0 1 0 1 0 1
0 0 0 0 0 0
0 0 0 0 0 0

출력

0

출처:유명한 문제 + www.koi4u.net