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

ROBO este un robot care poate executa o secventa de actiuni pentru a repara o statie orbitala. ROBO are senzori care ii permit sa detecteze “starea curenta” in care se afla statia. O stare de succes corespunde situatiei in care statia a fost reparata. Starea curenta si actiunea aleasa de ROBO determina in mod unic starea urmatoare. Un exemplu este ilustrat mai jos:

ROBO este un robot care poate executa o secventa de actiuni pentru a repara o statie orbitala. ROBO are senzori care ii permit sa detecteze "starea curenta" in care se afla statia. O stare de succes corespunde situatiei in care statia a fost reparata. Starea curenta si actiunea aleasa de ROBO determina in mod unic starea urmatoare. Un exemplu este ilustrat mai jos:

In exemplul de mai sus, starile sunt reprezentate prin noduri (cercuri). Actiunile eticheteaza muchiile dintre noduri. Starea initiala este “0”, iar cea de succes este 4.

In exemplul de mai sus, starile sunt reprezentate prin noduri (cercuri). Actiunile eticheteaza muchiile dintre noduri. Starea initiala este "0", iar cea de succes este 4.

Analizand modelul de mai sus, ROBO observa ca poate realiza reparatia daca executa secventa de actiuni '''aba''' (trecand prin starile 0,1,4), dar si daca executa '''bbba''' (trecand prin starile 0,2,3,2,4). ROBO crede ca poate inlocui modelul sau intern, ilustrat mai sus, cu un model mai bun, adica unul in care:

Pentru un model oarecare '''M''', ROBO cauta '''numarul de stari''' al modelului cel mai bun - adica numarul minim de stari cu care putem reprezenta '''M''' astfel incat exact aceleasi secvente de actiuni din '''M''' conduc la reparatia statiei si in modelul imbunatatit.
Modelele au urmatoarele proprietati:

* Starea initiala este intotdeauna etichetata cu “0”

* Starea initiala este intotdeauna etichetata cu "0"

* Pentru fiecare stare si actiune, gasim intotdeauna o stare urmatoare;
* Nu exista stari inaccesibile (stari in care nu putem ajunge prin nici o secventa de actiuni);
h2. Date de intrare

Fişierul de intrare $robo.in$ ...

Datele de intrare se citesc din fişierul $robo.in$.
Pe prima linie se află numărul de teste, T. După aceea, pentru fiecare test sunt citite următoarele informaţii:
* Pe prima linie: numarul de '''stari''' urmat de numarul de '''actiuni''' posibile
* Pe a doua linie: o secventa de numere ce reprezinta '''starile in care statia e reparata'''
* Pe fiecare linie urmatoare: un triplet de forma '''stare actiune stare_urmatoare''',unde '''stare''' si '''stare_urmatoare''' sunt numere iar '''actiune''' este un caracter alfabetic.

h2. Date de ieşire