시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 64 MB | 17 | 15 | 14 | 93.333% |
Young hero, an adventurer Matej, has, after a long and strenuous journey, arrived to his final destination – the house of evil witch Marija. In order to complete his adventure, he must solve the final puzzle the witch gives him.
To even begin solving her puzzle, our hero needs to become familiar with the data structure called prefix tree (trie).
A prefix tree is a data structure that represents all prefixes of words from a certain set in the following way:
Prefix tree for words: “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, i “inn”.
Only after Matej learned what a prefix tree was does the real puzzle begin!
The witch, as you may have guessed, has N words that consist of lowercase letters of the English alphabet. The puzzle would be very simple if the witch wanted to know the number of nodes of the prefix tree for that set of words, but she is not interested in this. She wants to know the minimal number of nodes a prefix tree can have after permuting the letters of each word in an arbitrary manner.
Help Matej find the answer to the puzzle!
The first line of input contains the integer N (1 ≤ N ≤ 16).
Each of the following N lines contains a single word consisting of lowercase letter of the English alphabet.
The total length of all words will be less than 1 000 000.
The first and only line of output must contain a number, the answer to witch Marija’s puzzle.
3 a ab abc
4
3 a ab c
4
4 baab abab aabb bbaa
5