X Olympiad in Informatics 2002/2003

Problem: Sequences without Stammers

Author: Krzysztof Sikora

We consider sequences of letters. We say a sequence x_{1}x_{2}...x_{n} contains a stammer, if we can find in it two occurrences of the same subsequence, one directly following the other, i.e. if for some i and j (1 <= i < j <= (n+i+1)/2) we have x_{i} = x_{j}, x_{i+1} = x_{j+1}, ..., x_{j1} = x_{2ji1}.
We are interested in nelement sequences having no stammers, built of the minimal number of different letters.
For n = 3 it is enough to use two letters, say a and b. We have exactly two 3element sequences without stammers build of those letters: aba and bab. For n = 5 we need three different letters. For example abcab is a threeletter sequence without stammers. In the sequence babab we have two stammers: ba and ab.
In the first line of the standard input there is one positive integer n, 1 <= n <= 10000000.
Your program should write to the standard output. In the first line there should be one positive integer k equal to the minimal number of different letters that must appear in an nelement sequence having no stammers.
In the second line one should write the computed sequence without stammers as a word that comprises n lower case letters of English alphabet and is built only of the letters from a up to the kth letter of the alphabet. If there are many such sequences, your program should write one of them.
You may assume 26 letters are enough.
5a correct answer is in the following output:
3 abcab