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

Neinfricatul Sorinel a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la JBOI. Pentru ca Sorinel a investit foarte mult in pregatirea sa de adevarat olimpic, acesta nu mai are cu ce sa vina la competitie, asa ca a imprumutat un cal de la vecinul sau. Sorinel nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar ghiciti ce, Sorinel a devenit atat de bun in ultimul ana incat daca acesta ajunge la competitie o sa ia $MAXIM$ si evident primul loc. Acest lucru nu se poate intampla (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati lui Sorinel un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la JBOI. Din nefericire, la cat de praf este Sorinel la geografie, atat de buna memorie are. Asa ca voi trebuie sa-i dati un traseu cat mai lung si care nu trece printr-un loc de mai multe ori (altfel acesta o sa se prinda ca l-ati masluit).
Suprafata pe care poate calatori Sorinel (acesta sta cam prost cu actele de identitate si nu are voie sa paraseasca regiunea Est-Europeana) are forma unei table N*M. Calul lui Sorinel poate sa se deplaseze doar in forma de L (exact cum o fac toti caii de pe lumea asta). Scopul vostru este sa generati o serie de mutari de cal cu cardinal maxim. Puteti incepe de oriunde.

Neinfricatul K0Kalaru 47 a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la JBOI. Pentru ca K0Kalaru 47 a investit foarte mult in pregatirea sa de adevarat olimpic, acesta nu mai are cu ce sa vina la competitie, asa ca a imprumutat un cal de la vecinul sau. K0Kalaru 47 nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar ghiciti ce, el a devenit atat de bun in ultimul ana incat daca acesta ajunge la competitie o sa ia $MAXIM$ si evident primul loc. Acest lucru nu se poate intampla (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati K0Kalarului 47 un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la JBOI. Din nefericire, la cat de praf este el la geografie, atat de buna memorie are. Asa ca voi trebuie sa-i dati un traseu cat mai lung si care nu trece printr-un loc de mai multe ori (altfel acesta o sa se prinda ca l-ati masluit).
Suprafata pe care poate calatori K0Kalaru 47 (acesta sta cam prost cu actele de identitate si nu are voie sa paraseasca regiunea Est-Europeana) are forma unei table N*M. Calul lui Sorinel poate sa se deplaseze doar in forma de L (exact cum o fac toti caii de pe lumea asta). Scopul vostru este sa generati o serie de mutari de cal cu cardinal maxim. Puteti incepe de oriunde.

h2. Date de intrare

h2. Date de ieşire

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $Nr$ ce semnifica numarul de casute prin care Sorinel o sa treaca. Pe urmatoarele $Nr$ linii se afla cate doua numere $x$ si $y$ ce reprezinta sirul de casute prin care Sorinel trece in ordinea in care apar in fisierul de iesire. Fiecare casuta trebuie sa apara cel mult o data in cadrul unui test.

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $Nr$ ce semnifica numarul de casute prin care K0Kalaru 47 o sa treaca. Pe urmatoarele $Nr$ linii se afla cate doua numere $x$ si $y$ ce reprezinta sirul de casute prin care K0Kalaru 47 trece in ordinea in care apar in fisierul de iesire. Fiecare casuta trebuie sa apara cel mult o data in cadrul unui test.

h2. Restricţii