Rezolvare PBinfo #3945

Cerința

Se dau n cuvinte distincte formate din litere mici. Afișați șirul format dintr-un număr maxim de cuvinte distincte dintre cele date, care respectă regula jocului Fazan. La jocul Fazan o succesiune de două cuvine a și b se consideră corectă dacă ultimele două litere din cuvântul a sunt identice cu primele două din b. De exemplu, cuvintele fazan și anterior sunt corecte în această ordine.

Date de intrare

Programul citește de la tastatură numărul n și apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.

Date de ieșire

Programul va afișa pe ecran cuvintele care formează șirul cerut, separate prin câte un spațiu.
Dacă există mai multe șiruri formate dintr-un număr maxim de cuvinte, se va afișa cel mai mic lexicografic.

Restricții și precizări

• 1 ≤ n ≤ 30
• cele n cuvinte sunt formate din litere mici, au lungimea cel puțin 2 și cel mult 20 și sunt distincte.

Exemplu:

Intrare

7
dor ana nasture repede alina diana decis

Ieșire

alina nasture repede decis

Explicație

Există mai multe soluții de lungime maximă, dar cea afișată este minimă lexicografic. Celelalte soluții sunt:

ana nasture repede decis
diana nasture repede decis