Click Color

O puzzle Click Color consiste em um tabuleiro quadrado de dimensão $N$, onde cada casas contém uma cor (amarelo ou magenta). O objetivo do jogador é fazer com que todos os quadrados do tabuleiro tenham a mesma cor, sendo que o único movimento válido é clicar em um dos quadrdados: quando isto acontece, o quadrado clicado e todos os seus vizinhos nas direções norte, sul, leste e oeste (se existirem) trocam suas respectivas cores (de amarelo para magenta e vice-versa).

A figura abaixo ilustra o tabuleiro antes e depois de um click no quadrado que está na primeira linha, segunda coluna:

Dado o estado inicial do tabuleiro, determine o número mínimo de movimentos para a solução do problema, se existir.

Entrada

A primeira linha da entrada contém a dimensão $N$ ($3\leq N\leq 4$) do tabuleiro. As $N$ linhas seguintes contém $N$ caracteres que representam as cores de cada quadrado do tabuleiro: o $j$-ésimo caractere ($1\leq j\leq N$) da $i$-ésima linha ($1\leq i \leq N$) contém a cor do quadrado da posição ($i, j$) do tabuleiro (cuja posição (1, 1) é o canto superior esquerdo): Y para amarelo, M para magenta.

Saída

Imprima, em uma linha, o número mínimo $M$ de movimentos para a solução do problema. Em seguida, devem ser impressas $M$, onde a $i$-ésima linha contém as coordenadas $x$ e $y$ da célula que deve ser clicada no $i$-ésimo movimento da sequência que leva a solução do problema, separadas por um espaço em branco.

Caso exista mais de uma sequência que resolva o problema em $M$ movimentos, imprima qualquer uma delas. Caso não exista uma solução para o tabuleiro dado, imprima o valor $-1$.

Exemplo de entrada 1

3
MMM
MMM
MMM

Exemplo de saída 1

0

Explicação do exemplo 1: O problema já está resolvido, não sendo necessário nenhum movimento.

Exemplo de entrada 2

3
YMY
MYM
YMY

Exemplo de saída 2

4
1 2
2 1
2 3
3 2

Explicação do exemplo 2: A sequência de movimentos do segundo caso está ilustrada abaixo:

Exemplo de entrada 3

4
MMYY
YMYM
YYYY
YYMM

Exemplo de saída 3

-1