Two Snakes In A Grid

Given an rectangular grid of N rows and M columns, each cell can be labeled black (Yin) or white (Yang). Two cells are neighbors if they share a common unit-length edge segment. The grid is valid if all the black cells form a path, and all the white cells form a path. A path is a set S of cells defined as follows: The cells form a connected piece. From each cell in S, you can reach any other cell