영선이의 생일
시간 제한2초메모리 제한512 MB
n×m 격자의 일곱 칸에 초 한 개, 체리 세 개, 딸기 세 개가 놓여 있을 때, 초가 있는 조각에는 과일이 없고 나머지 세 조각이 각각 체리와 딸기를 하나씩 갖도록 격자를 네 개의 연결된 조각으로 나눌 수 있는지 판정한다.
문제
오늘은 영선이의 생일이다. 친구들이 직사각형 모양의 생일 케이크를 하나 준비했다.
케이크의 윗면은 개의 칸으로 나누어져 있다. 왼쪽 위 칸의 좌표는 , 오른쪽 위 칸의 좌표는 , 오른쪽 아래 칸의 좌표는 이다. 좌표 에서 는 왼쪽에서 센 열 번호, 는 위에서 센 행 번호다.
일곱 개의 칸에는 장식이 하나씩 놓여 있다.
- 에는 초가 놓여 있다.
- , , 에는 체리가 놓여 있다.
- , , 에는 딸기가 놓여 있다.
영선이는 케이크를 네 조각으로 나누려고 한다. 한 조각은 영선이가 먹고, 나머지 세 조각은 친구들이 먹는다.
네 조각은 모두 칸으로 이루어져야 하고, 모든 칸은 정확히 한 조각에 속해야 한다. 또 네 조각은 모두 연결되어 있어야 한다. 변을 맞대고 있는 두 칸은 서로 이웃하고, 한 조각에 속한 어떤 두 칸이든 그 조각 안의 이웃한 칸만 밟아서 오갈 수 있으면 그 조각은 연결되어 있다.
영선이는 초가 놓인 조각을 먹어야 하고, 나머지 세 조각에는 딸기 하나와 체리 하나가 들어 있어야 한다.
과 , 초와 체리와 딸기의 위치가 주어졌을 때, 조건에 맞게 케이크를 나눌 수 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 과 이 주어진다. ()
둘째 줄부터 일곱 개의 줄에 , , ..., 이 한 줄에 하나씩 주어진다. (, )
칸이 일곱 개 이상인 케이크만 입력으로 주어진다. 일곱 좌표는 서로 다르다.
출력
첫째 줄에 문제의 조건에 맞게 케이크를 네 조각으로 나눌 수 있으면 "Yes"를, 나눌 수 없으면 "No"를 출력한다.
힌트
다음 그림은 세 번째 예제의 케이크를 조건에 맞게 나눈 한 가지 방법이다. 색이 같은 칸이 한 조각이다. 그림은 첫 번째 좌표가 세로 방향, 두 번째 좌표가 가로 방향이 되도록 그려져 있다.
