Riddicks Cube

It is well known, that the most sold toy in history is Rubik's Cube. In mere $40$ years $350$ million items were sold.

A famous Kazakhstani businessman decided to repeat that success, by creating a simpler version of this puzzle. Riddick's Cube, the ingenious invention of the businessman, is an n \times m rectangle consisting of 1 \times 1 cells, each of which is colored in some color. The rules of the puzzle are simple: in a single move it is allowed to cyclically move any row or column by one cell in any direction (rows are moved left or right, columns are moved up or down). For example, this is how $2$-nd row is moved right and how $3$-rd column is moved up:

A configuration of the puzzle is called final, if either each of the rows contains cells of the same color or each column contains cells of the same color.

The businessman is concerned about the solvability of his puzzle and so he wants to estimate its complexity before starting the sales. And he gives that task to you. To estimate the complexity we will simplify the rules: you can shift some columns (possibly none) and then some rows (possibly none).

You are given a configuration of one of the Riddick's Cubes. If a final configuration can be reached using the simplified rules, then the complexity of the configuration is equal to the minimal number of moves, leading to a final configuration. If a final configuration cannot be reached using the simplified rules, then the Cube is said to be mega complex and its complexity is equal to $100500$ (probably, the puzzle can still be solved using the normal rules, but it's too complex).