magic

Misopan şi Trofonaced sunt doi eroi care vor să-şi unească forţele în lupta împotriva răului. Regatul este reprezentat printr-o matrice dreptunghiulară de N linii şi M coloane. Fiecare element al matricei corespunde unei bucăţi de teren uscat sau mlăştinos. Cei doi eroi nu se vor aventura în părţile mlăştinoase ale regatului – se vor deplasa numai pe uscat. Ei se pot muta dintr-o poziţie a matricei în una din cele 4 poziţii vecine pe orizontală sau pe verticală, dacă această poziţie corespunde unei zone de uscat. Unele poziţii de uscat pot fi transformate prin vrajă în mlaştină.

Cerinţă

Ajutaţi un vrăjitor malefic să aleagă un număr minim de poziţii ”transformabile“, prin schimbarea cărora cei doi eroi să nu se poată întâlni (să nu existe un drum pe uscat între cei doi).

Date de intrare

Prima linie a fişierului magic.in conţine două numere întregi N şi M reprezentând numărul de linii, respectiv de coloane ale matricei. Următoarele N linii conţin câte M caractere cu următoarea semnificaţie:

• . - pentru o poziţie uscată
• x - pentru una mlăştinoasă
• * - pentru una uscată ”transformabilă“ în una mlăştinoasă de către vrăjitor
• M - pentru poziţia eroului Misopan
• T - pentru poziţia eroului Trofonaced

Date de ieşire

Pe prima linie a fişierului magic.out se scrie numărul întreg R, reprezentând numărul minim de poziţii care trebuie transformate. Pe următoarele R linii vor apărea câte 2 numere, reprezentând poziţiile alese. Primul număr va fi linia (între 1 şi N), iar al doilea va fi coloana (între 1 şi M).

Restricţii şi precizări

• 1 ≤ N, M ≤ 50
• R (rezultatul afişat) poate fi 0
• Pe testele date va exista întotdeauna soluţie
• Se garantează că în toată matricea caracterele M, respectiv T vor apărea fiecare exact o dată
• Poziţiile eroilor sunt implicit zone de uscat care nu pot fi transformate de vrăjitor

Exemplu

magic.in

4 4
MxxT
.x*.
.**.
**x.

magic.out

1
3 3