Ciągi bez zająknięć

Limit pamięci: 32 MB

Rozważamy ciągi liter. Powiemy, że ciąg zawiera zająknięcie, jeśli napotykamy w nim dwa, następujące bezpośrednio po sobie, wystąpienia takiego samego podciągu. Tzn. jeśli dla pewnych i () zachodzi: .

Interesują nas -elementowe ciągi bez zająknięć o minimalnej liczbie liter.

Przykład

Dla wystarczą dwie litery, powiedzmy i . Mamy dokładnie dwa 3-elementowe ciągi bez zająknięć złożone z takich liter: i . Dla potrzebne są już 3 różne litery. Na przykład jest trójliterowym ciągiem bez zająknięć. W ciągu mamy dwa zająknięcia: i .

Zadanie

Napisz program, który:

• wczyta długość ciągu ,
• obliczy -elementowy ciąg bez zająknięć o minimalnej liczbie różnych liter,
• wypisze wynik.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita , .

Wyjście

Twój program powinien pisać na standardowe wyjście. W pierwszym wierszu powinna zostać wypisana jedna dodatnia liczba całkowita , równa minimalnej liczbie różnych liter, które muszą wystąpić w -elementowym ciągu nie zawierającym zająknięć.

W drugim wierszu należy wypisać obliczony ciąg bez zająknięć, jako słowo złożone z małych liter alfabetu angielskiego, od litery do -tej litery alfabetu. Jeżeli istnieje wiele takich ciągów, Twój program powinien wypisać jeden z nich.

Możesz przyjąć, że 26 liter wystarczy.

Przykład

Dla danych wejściowych:

5

poprawną odpowiedzią jest:

3
abcab

Autor zadania: Krzysztof Sikora.