Pyramid
A pyramid is a word puzzle that needs to be filled with M words in M lines. A properly filled pyramid begins with a word which has 1 letter, and each following line has a word with one more letter compared to the previous line – additionally, that word also contains all the letters that are in the previous line (not necessarily in the same order).
You are given N words (and it is assumed that you may additionally create any word of length 1). Use the words to make the longest possible pyramid.
Input
The first line contains one integer number N (1 <= N <= 10 000).
Each of the following N lines contains one of the words you may use (all written in capital letters of the English alphabet). The words will contain between 1 and 1000 characters.
Output
In the first line, print one integer M (the length of the longest word in your pyramid).
In the following M lines output the words of your pyramid from shortest to longest, one in each line (all written with capital letters of the English alphabet).
If there are multiple solutions that result in a pyramid of maximum possible length, print any one of them.
Constraints
Time limit: 1 second
Memory limit: 512 megabytes
Examples
input 12 NIM COMEDIAN MACEDONIA ADMIN DUX MIND PIRS MEDIAN IN OUT KURATOWSKI DOMAINE | output 9 N IN NIM MIND ADMIN MEDIAN DOMAINE COMEDIAN MACEDONIA |
input 8 TRKA KARTA KRILA AR ARTIKL RAK AKROLIT IKRA | output 7 R AR RAK IKRA KRILA ARTIKL AKROLIT |
input 3 BB BBB AAAB | output 3 B BB BBB |
Subtasks
Let’s use |W| to denote the length of the longest word in the input.
1) In test cases worth 9 points, (N <= 10, |W| <= 10)
2) In other test cases worth 13 points, (N <= 100, |W| <= 100)
3) In other test cases worth 16 points, (N <= 1 000, |W| <= 100)
4) In other test cases worth 11 points, the words will only contain the letters ‘A’ and ‘B’
5) To earn all 100 points, your solution must work for the input constraints presented in the “Input” section.