Datorită faptului că deşertul Sahara se extinde tot mai mult în fiecare an, statele lumii au hotărât să reducă acest proces. Chiar mai mult, specialiştii au demonstrat că la câţiva metri sub stratul de nisip se ascund zăcăminte importante de apă şi au hotărât împădurirea acestui deşert.
Pentru simplificare, să considerăm reprezentarea hărţii deşertului ca fiind o matrice cu n linii şi m coloane. În fiecare element al matricei poate exista un singur copac.
Se mai ştie că datorită condiţiilor climaterice extreme un copac nou plantat nu ar rezista decât dacă ar fi învecinat cu cel puţin alţi doi copaci existenţi. Deci, în procesul de împădurire, în fiecare zi se plantează copaci care pot rezista.

Cerinţă

Scrieţi un program care să determine dacă deşertul poate fi complet împădurit sau nu. În caz afirmativ se cere numărul minim de zile în care se poate realiza împădurirea, altfel se cere numărul minim de zile după care se opreşte împădurirea, urmat pe linia următoare de mesajul IMPOSIBIL.

Date de intrare

Datele se citesc din fişierul de intrare copaci1.in care are următoarea structură:
- pe prima linie sunt scrise două numere naturale n şi m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei;
- pe fiecare dintre următoarele n linii sunt scrise câte m numere naturale separate prin spaţii; al j-lea element de pe linia (i+1) este 0 dacă poziţia de pe linia i şi coloana j de pe hartă este neocupată sau este 1 dacă poziţia respectivă este ocupată de un copac.

Date de ieşire

Rezultatul va fi afişat în fişierul de ieşire copaci1.out.
Dacă împădurirea poate avea loc, fişierul de ieşire conţine o singură linie pe care se află numărul minim de zile în care se poate realiza împădurirea.
Dacă împădurirea nu poate avea loc, atunci fişierul de ieşire conţine două linii. Pe prima linie va fi afişat numărul minim de zile după care se opreşte împădurirea, iar pe cea de a doua linie va fi afişat cu litere mari cuvântul IMPOSIBIL.

Restricţii

1 <= n, m <= 100
În fiecare căsuţă a matricei poate exista doar un singur copac.
Două poziţii se numesc vecine dacă ele sunt învecinate pe orizontală sau pe verticală.

Exemple

copaci1.in	copaci1.out
5 6 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0	9
3 3 1 0 0 0 0 0 1 0 0	1 IMPOSIBIL

autor: Prof. Lucia Miron

propunător: Prof. Marinel Şerban

Liceul de Informatica

marinel.serban@gmail.com