tower8

Cerință

Dispozitivul de apărare al elfilor are forma unei matrice cu $N$ linii și $M$ coloane. În fiecare poziție a matricei se plasează câte un turn de aparare după reguli bine stabilite. Cât timp există poziții neocupate de un turn, se alege o astfel de poziție și se plasează acolo un turn de nivel $1$. Numim această operațiune plasare. În funcție de configurația pozițiilor vecine (pe $8$ direcții) turnul va trece la un nivel superior. Atunci când un turn atinge nivelul $X$ și are cel puțin un vecin de nivel $X$, atunci el devine turn de nivelul $X+1$ și toate turnurile vecine de nivel $X$ dispar, lăsând astfel locuri libere unde pot fi din nou plasate alte turnuri. Numim această operațiune upgrade și se va aplica de cate ori este posibil după o plasare. Dispozitivul de apărare are forma finală în momentul în care nu se mai poate plasa niciun turn.

Cunoscând configurația finală a dispozitivului de apărare indicați o succesiune minimală de plasări prin care să se ajungă în acea configurație.

Date de intrare

Fişierul tower8.in conţine pe prima linie două numere naturale separate prin spațiu, $N$ și $M$ - numărul liniilor și coloanelor dispozitivului de aparare. Pe următoarele $N$ linii se găsesc câte $M$ numere naturale nenule separate prin spațiu - nivelele turnurilor dispozitivului de aparare în forma finală.

Date de ieșire

Fişierul tower8.out va conţine pe prima linie un număr natural $K$ reprezentând numărul minim de turnuri care au fost plasate pentru a aduce dispozitivul de aparare la forma finală. Pe următoarele $K$ linii se gasesc câte doua numere naturale $L$ și $C$ separate prin spațiu - cu seminficația: se plasează un turn de nivel $1$ pe linia $L$, coloana $C$ a dispozitivului de aparare.

Restricții și precizări

• $2 \leq N, M \leq 100$
• dacă se afișează corect numai numărul minim de plasări se obține $20\%$ din punctaj
• dacă se afișează o succesiune corectă cu un număr mai mare de plasări se obține $80\%$ din punctaj cu condiția ca numărul de plasări sa fie cel mult dublul numărului minim
• dacă se afișează corect numărul minim de plasări și o succesiune corectă a acestora se obține $100\%$ din punctaj (succesiunea de plasări nu este unică!)
• Atenție: pozițiile din colțurile dispozitivului de apărare au doar $3$ vecini iar celelalte de la marginea dispozitivului de apărare au doar $5$ vecini.

Exemplul 1

tower8.in

2 2
1 2
3 4

tower8.out

15
1 1
1 2
1 1
2 1
1 1
1 2
1 1
2 2
1 1
1 2
1 1
2 1
1 1
1 2
1 1

Explicație

S-a efectuat următorul șir de mutări

Unde $P$ – semnifică faptul urmează o plasare în poziția hașurată iar $U$ – semnifică faptul că urmează un upgrade în pozitia bordată cu ajutorul turnului subliniat din poziție vecină.