* $2 ≤ N ≤ 100$ ; $1 ≤ M ≤ 5000$ şi $M < N*N-2$
* Şoricelul nu intră decât în camere neocupate de clienţi.
* Camera şoricelului este o cameră neocupată de clienţi.

* Dacă există mai multe trasee ale şoricelului de la camera lui la camera de alimente care trec prin exact $T$ camere,
atunci traseul afişat va fi cel mai mic traseu din punct de vedere lexicografic.
* Eticheta $(X1 Y1 Z1)$ se consideră strict mai mică în sens lexicografic ca eticheta $(X2 Y2 Z2)$ dacă este satisfăcută
doar una dintre condiţiile:

* Dacă există mai multe trasee ale şoricelului de la camera lui la camera de alimente care trec prin exact $T$ camere, atunci traseul afişat va fi cel mai mic traseu din punct de vedere lexicografic.
* Eticheta $(X1 Y1 Z1)$ se consideră strict mai mică în sens lexicografic ca eticheta $(X2 Y2 Z2)$ dacă este satisfăcută doar una dintre condiţiile:

1) $X1 < X2$ 2) $X1 = X2$ şi $Y1 < Y2$ 3) $X1 = X2$ şi $Y1 = Y2$ şi $Z1 < Z2$

* Eticheta $X1 Y1 Z1$ se consideră egală cu eticheta $X2 Y2 Z2$ dacă $X1 = X2$ şi $Y1 = Y2$ şi $Z1 = Z2$. Vom scrie
egalitatea lor astfel: $(X1 Y1 Z1) = (X2 Y2 Z2)$.
* Traseul ce trece (în această ordine) prin camerele cu etichetele $(X1 Y1 Z1), (X2 Y2 Z2),..., (XT YT ZT)$
este mai mic din punct de vedere lexicografic ca traseul $(A1 B1 C1, A2 B2 C2,…, AT BT CT)$ dacă există un indice
$J$ (1 ≤ J ≤ T) astfel încât $(X1 Y1 Z1) = (A1 B1 C1), (X2 Y2 Z2) = (A2 B2 C2)…., (XJ-1 YJ-1 ZJ-1) = (AJ-1 BJ-1 CJ-1)$ iar
eticheta $(XJ YJ ZJ)$ este strict mai mică ca eticheta $(AJ BJ CJ)$.
* Se acordă: 40% din punctaj pentru determinarea corectă a numărului $T$ şi 100% din punctaj pentru rezolvarea
corectă a ambelor cerinţe.

* Eticheta $X1 Y1 Z1$ se consideră egală cu eticheta $X2 Y2 Z2$ dacă $X1 = X2$ şi $Y1 = Y2$ şi $Z1 = Z2$. Vom scrie egalitatea lor astfel: $(X1 Y1 Z1) = (X2 Y2 Z2)$.
* Traseul ce trece (în această ordine) prin camerele cu etichetele $(X1 Y1 Z1), (X2 Y2 Z2),..., (XT YT ZT)$ este mai mic din punct de vedere lexicografic ca traseul $(A1 B1 C1, A2 B2 C2,…, AT BT CT)$ dacă există un indice $J$ (1 ≤ J ≤ T) astfel încât $(X1 Y1 Z1) = (A1 B1 C1), (X2 Y2 Z2) = (A2 B2 C2)…., (XJ-1 YJ-1 ZJ-1) = (AJ-1 BJ-1 CJ-1)$ iar eticheta $(XJ YJ ZJ)$ este strict mai mică ca eticheta $(AJ BJ CJ)$.
* Se acordă: 40% din punctaj pentru determinarea corectă a numărului $T$ şi 100% din punctaj pentru rezolvarea corectă a ambelor cerinţe.

* Se garantează că există soluţie pentru ambele cerinţe, pentru toate datele de test.
h2. Exemplu