Compressed Dictionary Tree

Petr and Dmitry are working on a novel data compression scheme. They are given a set of words and must construct a rooted tree. Each edge of the tree is marked with exactly one letter. The dictionary of a tree is defined as the set of all words that can be read by concatenating letters on any path (not necessarily starting at the root) that goes downward. The tree must have a dictionary that is a superset of the given set of words, and among all such trees you are to construct one with the smallest number of vertices.

Note that you are allowed to “attach” a word at any vertex, not necessarily at the root. In other words, the word does not have to be a prefix from the root. For example, consider the words ab and ac. If both words are attached directly to the root the total number of vertices is 5 (root + 2 for ab and 2 for ac). However, by first adding an edge labeled a from the root and then branching with b and c from that vertex, the total number of vertices reduces to 4. Another example is the pair aba and bab for which a single path won’t suffice; a branching construction yields fewer vertices.

Your task is: Given a set of words, compute the minimum number of vertices in a rooted tree that has a dictionary (i.e. the set of all downward paths in the tree) which is a superset of the given words.

Input format: The first line contains an integer n (the number of words). The following n lines each contain a word consisting of lowercase letters. It is guaranteed that 1 ≤ n ≤ 10 and the total length of all words is reasonably small. (Note: If a word appears as a substring of another word, it can be removed since its occurrence is automatically guaranteed.)

Output format: Output a single integer – the minimum number of vertices in a rooted tree that satisfies the condition.

Explanation:

• For example, if the input is:

  2
  ab
  ac
      

  then one optimal tree is constructed by having an edge labeled a from the root and two edges from that vertex with labels b and c, making the total number of vertices equal to 4.
• Another example:

  2
  aba
  bab
      

  One optimal tree is obtained by constructing a single path "abab" (4 edges, 5 vertices) in which aba appears as the prefix and bab appears as a substring.

inputFormat

The first line contains an integer n – the number of words. The next n lines each contain a word consisting of lowercase letters.

outputFormat

Output a single integer – the minimum number of vertices in a rooted tree whose dictionary (i.e. set of all downward paths) is a superset of the given words.

sample

2
ab
ac

4