393. Bergamot Problem

Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berland alphabet consists of N letters, which are first N latin letters. Citizens of Berland use simple abbreviation scheme for SMS writing purposes. Each word is abbreviated to the sequence of two symbols — its first and last letters. For example, the word "" is abbreviated to "". Unfortunately, for single-letter words this rule leads to a word lengthening. For example, word "" will be written as "".

Vocabulary used for SMS creation consists of only two-character words. The numerous studies of well-known scientists showed that the vocabulary consists of M distinct words.

Bergamot company is ready to put their new cell phone in production. The new model is planned to have the revolutionary system of a quick text input (somewhat similar to the famous T9). Keyboard of the phone will consist of K buttons. Each button will have one or several letters from placed on it. Each letter can be placed on exactly one button of the phone. In order to enter a word, a user should press two buttons on the phone one after another: button with the first letter of the word, and then button with the last letter of the word. Placement of letters on the keyboard is called for a given vocabulary, if there are no words from vocabulary that can be entered using the same two-buttons sequence.

For example, if the vocabulary consists of three words "", "" and "", two buttons are enough for creating the keyboard. The first button will have "" and "", the second button — "". The placement like "" and "" on the first button, "" on the second button will not work, because words "" and "" can be entered using the same sequence of buttons.

Bergamot engineers have got a problem finding optimal placement of Berland alphabet letters on the keyboard of the phone. The placement is any correct placement with the minimal possible number of buttons used for the given Berland alphabet.

Input
The first line of the input contains two integer numbers N, M (1 ≤ N ≤ 13; 0 ≤ M ≤ 50). The following M lines contain words from the vocabulary — one word per line. Each word consists of exactly two lowercase Latin letters. Only first N letters from Latin alphabet can be used. All words in the vocabulary are different.

Output
The first line of the output file should contain the minimal possible number of the keyboard buttons K for the optimal letters placement. The placement itself should be printed to the following K lines. The i+1th line of the output file should contain letters placed on the ith button. The order of letters within each line, and the order of lines describing the placement don't matter. If there are several solutions, you may output any of them.

Example(s)
sample input
sample output
3 3
ab
aa
bc
2
ac
b

sample input
sample output
4 2
ab
cd
2
cb
ad

sample input
sample output
5 4
aa
bb
cc
dd
4
ae
b
c
d




Online Contester Team © 2002 - 2010. All rights reserved.