== include(page="template/taskheader" task_id="alee") ==

Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari. Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in N*N zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu N linii si N coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la N. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera. Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.

Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari. Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in NxN zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu N linii si N coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la N. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera. Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.

h2. Cerinta

h2. Restrictii

* 1 ≤ N ≤  200
* 1 ≤ M ≤ N*N
* Aleea este continua daca oricare doua placi consecutive au o latura comuna.
* Aleea incepe cu zona unde se gaseste prima poarta si se termina cu zona unde se gaseste cea de a doua poarta.
* Pozitiile portilor sunt distincte si corespund unor zone libere.
* Pentru datele de test exista intotdeauna solutie.
 

* $1 ≤ N ≤ $ 200

h2. Exemplu