시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 85 57 48 65.753%

문제

Professor Kim is in the process of developing a new fabric material such that the electrical current percolates. The cross section of the new fabric can be shown in the two-dimensional M × N grid. We assume that the top of the grid is the outer side of the fabric and the bottom is the inner side. The black colored cell insulates the current while the white cell conducts the current. The current travels from the outer side to the inner side of the fabric only through the white cells that are adjacent to each other. When the white cells are connected diagonally, the current cannot flow (see Figure 1). The professor wants to test whether the current could percolate from the outer side to the inner side through the material or not.

For example, the following Figure 1(a) shows that the current percolates through the material but Figure 1(b) does not:

(a) The current percolates. (b) The current does not percolate.

Figure 1. Two examples.

When the information on each cell is given, write a program that computes whether the current can pass through the material or not.

입력

Your program is to read from standard input. The first line of the input contains two integers M (2 ≤ M ≤ 1,000) and N (2 ≤ N ≤ 1,000) which represent the size of the fabric. In the following M lines, the information about each cell is given. Each line consists of N characters which composed by ‘0’ or ‘1’. The character ‘0’ represents the conduct cell and ‘1’ represents the insulate cell.

출력

Your program is to write to standard output. If the current can pass through the material from the top to the bottom, print YES. If not, print NO.

예제 입력

5 6
010101
010000
011101
100011
001011

예제 출력

NO

예제 입력 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

힌트