În această problemă vrem să verificăm dacă un caroiaj este sau nu _labirint_. Un labirint este un caroiaj cu o serie de proprietăţi suplimentare:

* celulele adiacente pot avea maxim un perete despărţitor, definit pentru una din celule,
* fiecare celulă de pe margine e despărţită de exterior prin perete,
* între oricare două celule din caroiaj există exact un drum simplu format din paşi pe orizontală şi verticală între celule adiacente şi nedespărţite.

* celulele adiacente pe verticală sau orizontală pot avea maxim un perete despărţitor, definit pentru una din celule,
* fiecare celulă de pe margine are pereţi care despart caroiajul de exterior pe fiecare latură cu exteriorul,
* între oricare două celule din caroiaj există exact un drum simplu format din paşi pe orizontală şi verticală între celule adiacente şi nedespărţite de perete pe latura comună.

Fiecare celulă este descrisă de un număr natural pe $4$ biţi, unde biţii adevăraţi descriu, în ordine, existenţa unui perete pe direcţiile sus, dreapta, jos, stânga. De exemplu, numărul $5$ = $0$ $×$ $2^3^$ + $1$ $×$ $2^2^$ + $0$ $×$ $2^1^$ + $1$ $×$ $2^0^$ descrie o celulă cu pereţi doar în dreapta şi stânga.

Fiecare celulă este codificată ca un număr natural pe $4$ biţi, unde biţii adevăraţi denotă, în ordine, existenţa unui perete pe direcţiile sus, dreapta, jos, stânga. De exemplu, numărul $5$ = $0$ $×$ $2^3^$ + $1$ $×$ $2^2^$ + $0$ $×$ $2^1^$ + $1$ $×$ $2^0^$ denotă o celulă cu pereţi în dreapta şi stânga.

h2. Date de intrare