Editing 3945 - Fazan Max

==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
==Rezolvare==
def backtracking(current_path, remaining_words, result):
    if not remaining_words:
        # Verificăm dacă șirul format este mai lung sau la fel de lung ca rezultatul curent
        if len(current_path) > len(result):
            return current_path
        elif len(current_path) == len(result):
            # Verificăm dacă șirul curent este lexicografic mai mic
            current_str = " ".join(current_path)
            result_str = " ".join(result)
            if current_str < result_str:
                return current_path
            else:
                return result
        else:
            return result

    last_word = current_path[-1] if current_path else None

    for word in remaining_words:
        if last_word is None or last_word[-2:] == word[:2]:
            new_path = current_path + [word]
            new_remaining = remaining_words.copy()
            new_remaining.remove(word)
            result = backtracking(new_path, new_remaining, result)

    return result

# Citirea datelor de intrare
n = int(input())
words = input().split()

# Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului
words.sort()

# Inițializăm rezultatul cu primul cuvânt
initial_word = words.pop(0)
result = backtracking([initial_word], words, [])

# Afișăm rezultatul
print(" ".join(result))