Fişierul intrare/ieşire:	path.in, path.out	Sursă	Bursele Agora 2004
Autor	Cosmin Silvestru Negruseri	Adăugată de
Timp execuţie pe test	0.05 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Path

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.

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¹ si c², separate intre ele printr-un singur spatiu, cu semnificatia ca exista un arc care pleaca din nodul identificat prin c¹ si ajunge in nodul identificat prin c².

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.

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

Exemplu

Cum se trimit solutii?