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

 
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**.

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 exact odata 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$. Urmeaza $M$ linii fiecare continand cate doi intregi: linia $i+1$ contine $u$ si $v$ reprezentand faptul ca tasta $i$ modifica starea jocului din $u$ in $v$.

Fişierul de intrare $tester.in$ contine pe prima linie doi intregi, $N$ si $M$. Urmeaza $M$ linii fiecare continand cate doi intregi: linia $i+1$ contine $x$ si $y$ reprezentand faptul ca tasta $i$ modifica starea jocului din $x$ in $y$.

h2. Date de ieşire

Fişierul de ieşire $tester.out$ va contine o singura linie care va descrie starile prin care jocul trece in secventa Paraschivei. Orice resetare este marcata cu un $R$. Pentru a intelege mai bine formatul fisierului de iesire studiati exemplul.

Fişierul de ieşire $tester.out$ va contine o singura linie care va descrie **starile** prin care jocul trece in secventa Paraschivei. Orice resetare este marcata cu un $R$. Pentru a intelege mai bine formatul fisierului de iesire **studiati exemplul si explicatia**.

h2. Restrictii si precizari
* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 5000$

* Nu vor exista doua taste cu acelasi efect (adica sa aibe aceasi pereche ( $x$, $y$ )).
* Tasta ( $x$, $y$ ) este diferita de tasta ( $y$, $x$ ).

* Orice solutie care respecta conditiile din enunt va obtine punctajul pe respectivul test.

* Graful neorientat determinat de stari ca noduri si taste ca muchii este conex.

h2. Exemplu

h3. Explicaţie

Pentru primul exemplu, comenzile executate sunt (1, 2) (2, 3) (3, 5) (5, 4) - (1, 2) (2, 4) se observa ca orice combo posibil apare in secventa o singura data ( ( $1$, $2$ ) este o tasta, nu un combo ).

Pentru primul exemplu, tastele apasate sunt (1, 2) (2, 3) (3, 5) (5, 4) - (1, 2) (2, 4). Se observa ca orice combo posibil apare in secventa exact odata ( ( $1$, $2$ ) este o tasta, nu un combo deci poate aparea de mai multe ori ). **Atentie**, valorile afisate sunt starile jocului si nu tastele; tastele sunt implicit determinate de doua numere consecutive din secventa.

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

4301