Colored Domino Tilings and Cuts

Consider rectangular grid that composed of N rows and M columns. Colored domino tiling of the grid is some way to put lowercase English letter in each cell of the grid provided that each cell has exactly one neighbor with the same letter as in this cell. Two cells of the grid are neighbors if they share a common side. Each letter represents some color. Cut of colored domino tiling is vertical or h