==Include(page="template/taskheader" task_id="path")==
 
==Include(page="template/raw")==
 
Path
 
 
 
Se considera un graf orientat aciclic ce contine N noduri si M arce. Nodurile sunt identificate prin litere distincte ale alfabetului englezesc (sunt permise atat litere mari, cat si litere mici). Un drum este format dintr-o succesiune de arce, iar aceste drumuri sunt ordonate in ordine lexicografica (fiecarui drum ii corespunde un sir de caractere obtinut prin concatenarea literelor corespunzatoare nodurilor, in ordinea in care apar nodurile in drum; se considera ca toate literele mici sunt, din punct de vedere lexicografic, inaintea tuturor literelor mari).
 
Dintre toate drumurile din graf, sunt luate in considerare doar cele mai lungi (lungimea unui drum este data de numarul de arce care il formeaza). Se cere ca dintre acestea din urma sa se determine cel de-al k-lea in ordine lexicografica.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare path.in contine trei numere intregi N, M si k separate intre ele printr-un singur spatiu.
 
 
 
Fiecare dintre urmatoarele M linii contine doua caractere ale alfabetului englezesc c[1] si c[2], separate intre ele printr-un singur spatiu, cu semnificatia ca exista un arc care pleaca din nodul identificat prin c[1] si ajunge in nodul identificat prin c[2].
 
h2. Date de Iesire
 
Fisierul de iesire rpath.out va contine pe o singura linie un sir de caractere care reprezinta drumul determinat. Caracterele acestui sir nu vor fi separate intre ele prin spatii.
 
h2. Restrictii si precizari
 
. Numarul de drumuri de lungime maxima este mai mare sau egal decat k.
 
. 2 <= N <= 52;
 
. 1 <= M <= N(N-1) / 2;
 
. Intre doua noduri poate exista cel mult o muchie.
 
. 1 <= K <= 2.000.000.000
 
h2. Exemplu
 
 
|path.in |path.out |
 
|3 3 1 |abc |
| | |
|a b | |
| | |
|b c | |
| | |
|a c | |

==Include(page="template/taskheader" task_id="path")==
 
Se considera un graf orientat aciclic ce contine $N$ noduri si $M$ arce. Nodurile sunt identificate prin litere distincte ale alfabetului englezesc (sunt permise atat litere mari, cat si litere mici). Un drum este format dintr-o succesiune de arce, iar aceste drumuri sunt ordonate in ordine lexicografica (fiecarui drum ii corespunde un sir de caractere obtinut prin concatenarea literelor corespunzatoare nodurilor, in ordinea in care apar nodurile in drum; se considera ca toate literele mici sunt, din punct de vedere lexicografic, inaintea tuturor literelor mari).
Dintre toate drumurile din graf, sunt luate in considerare doar cele mai lungi (lungimea unui drum este data de numarul de arce care il formeaza). Se cere ca dintre acestea din urma sa se determine cel de-al k-lea in ordine lexicografica.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare $path.in$ contine trei numere intregi $N, M$ si $k$ separate intre ele printr-un singur spatiu.
Fiecare dintre urmatoarele $M$ linii contine doua caractere ale alfabetului englezesc $c[1]$ si $c[2]$, separate intre ele printr-un singur spatiu, cu semnificatia ca exista un arc care pleaca din nodul identificat prin $c[1]$ si ajunge in nodul identificat prin $c[2]$.
 
h2. Date de Iesire
 
Fisierul de iesire $path.out$ va contine pe o singura linie un sir de caractere care reprezinta drumul determinat. Caracterele acestui sir nu vor fi separate intre ele prin spatii.
 
h2. Restrictii si precizari
 
* Numarul de drumuri de lungime maxima este mai mare sau egal decat $k$.
* $2 ≤ N ≤ 52$
* $1 ≤ M ≤ N(N-1) / 2$
* Intre doua noduri poate exista cel mult o muchie.
* $1 ≤ K ≤ 2.000.000.000$
 
h2. Exemplu
 
table(example). |_. path.in |_. path.out |
| 3 3 1
a b
b c
a c
| abc |
 
==Include(page="template/taskfooter" task_id="path")==

==Include(page="template/taskfooter" task_id="path")==

1024