Programacion Competitiva Bolivia

Hay un rumor de que en tu ciudad existe un tesoro enterrado desde hace siglos. Muchas personas venden mapas diciendo que te llevara directo al tesoro, lamentablemente no puedes saber si un mapa es verdadero o falso pero existe otra curiosidad más, se dice que el camino al tesoro tiene forma de zig zag.

Como deseas encontrar el tesoro mas antes que otros has comprado todos los distintos mapas que están a la venta, pero son realmente muchos, tu tarea es identificar que mapas contienen un camino con forma de zig zag.

Entrada

Un mapa se ha divido en pequeños sectores cuadrados, por lo tanto tienes como entrada dos números enteros n y m (3 ≤ n, m ≤ 100) y (n ≤ m), donde n es el alto total del mapa y m el el ancho total del mapa. Luego n filas siguen conteniendo m números donde 0 representa la ausencia de un camino y 1 la presencia de un camino en el mapa, un camino puede estar unido de forma vertical horizontal y diagonal.

Salida

Imprimir 'YES' si el camino tiene forma de zig zag y recorre todo el mapa empezando siempre desde la esquina superior izquierda, caso contrario imprimir 'NO'.

Ejemplo

Input:
3 10
1 0 0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 0 1 0 0 0

Output:
YES

Input:
3 5
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0


Output:
NO

Input:
3 5
1 1 1 0 1
0 1 0 1 0
1 0 1 0 0

Output:
YES

Input:
3 3
0 0 0
1 1 1
0 0 0

Output:
NO

Input:
3 9
1 0 0 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0
0 0 1 0 1 0 1 0 0
Output:
NO