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

Gigel este o persoana cu pasiune pentru jocurile pe calculator, asa ca s-a angajat ca tester. Gigel a primit sarcina de a analiza un joc cu $N$ stari. El poate face $M$ mutari de tipul $(u, v)$ avand semnificatia ca din starea $u$ trece in starea $v$. El stie ca doua comenzi executate consecutiv pot produce anumite efecte pe care vrea sa le descopere. Gigel porneste din orice stare a jocului si incepe sa execute comenzi. El nu are mult timp la dispozitie asa ca doreste sa stie o secventa de a executa comenzi astfel incat **oricare doua comenzi $(u, v)$ si $(v, w)$ sa existe consecutiv in secventa**. Jocul poate fi resetat, o resetare inseamna reinceperea jocului din orice stare. Se doreste o secventa cu numar minim de resetari, iar in caz de egalitate se doreste o secventa cu numar minim de comenzi.

 
Paraschiva e tester de jocuri. Ultimul joc pe care il testeaza are $N$ stari si $M$ taste ce definesc anumite actiuni. Fiecare tasta modifica starea jocului dintr-o anumita stare $x$ in $y$. Paraschiva stie de la creatorii jocului ca oricare doua taste ( $x$, $y$ ) si ( $y$, $z$ ) apasate consecutiv produc un **combo** special (a doua tasta trebuie neaparat sa afecteze starea in care jocul este lasat de prima tasta). Paraschiva trebuie sa testeze toate combourile posibile ce pot aparea in joc. Pentru asta ea procedeaza astfel: porneste din orice stare a jocului si incepe sa tasteze pentru a descoperi efectele combo-urilor. Ea, de asemenea, poate oricand reseta jocul, adica poate reporni din orice stare doreste. Paraschiva se plictiseste repede asa ca doreste sa testeze jocul intr-un mod cat mai distractiv posibil: ea vrea sa produca o serie de tastari si resetari astfel incat **orice combo posibil sa apara in secventa o singura data iar numarul total de resetari ale jocului sa fie minim**

h2. Date de intrare

Fişierul de intrare $tester.in$ contine pe prima linie doi intregi, $N$ si $M$. Pe urmatoarele $M$ linii se afla cate doi intregi $u$ si $v$, avand semnificatia din enunt.

Fişierul de intrare $tester.in$ contine pe prima linie doi intregi, $N$ si $M$. Urmeaza $M$ linii fiecare continand doi intregi: linia $i+1$ contine $u$ si $v$ desemnand actiunea tastei $i$.

h2. Date de ieşire

În fişierul de ieşire $tester.out$ va contine un sirul de stari pe care Gigel trebuie sa il parcurga pentru a testa jocul. O resetare va fi codificata prin litera $R$.

În fişierul de ieşire $tester.out$ va contine o singura linie care va descrie secventa de stari ce respecta condiitile din enunt. Orice resetare este marcata cu un $R$. Pentru a intelege mai bine formatul fisierului de iesire studiati exemplul.

h2. Restricţii

h2. Restrictii si precizari

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 5000$

4 3
3 4
3 1

| 1 2 3 2 3 4 3 2 3 1 4 3 4 3 1 |

| 4 3 1 4 3 4 R 2 3 1 2 3 4 3 2 3 2 |

h3. Explicaţie