P6289 [COCI 2016/2017 #1] Vještica

Matej is facing a hard problem. Before that, we need to be familiar with a data structure called a prefix tree (`trie`). A trie stores words by their prefixes: - Each edge in the trie is labeled with a letter of the English alphabet. - The root node represents the empty prefix. - Every other node represents a non-empty prefix. The prefix is obtained by concatenating the letters on the path from the root to that node. - From any node, there are no two edges with the same letter. For example, this trie stores `A,to,tea,ted,ten,i,in,inn`:  Now, Matej has obtained $n$ words, and he may reorder the letters of some of them. For example, `abc` can be reordered into `acb,bac,bca,cab,cba`. Please compute the minimum possible number of nodes in the trie that stores these words, after reordering some words.

The first line contains an integer $n$. The next $n$ lines each contain a string, representing a word that Matej has obtained.

One line with one integer, the minimum possible number of nodes in the trie that stores these words after reordering some words.

#### Explanation for Sample 3 All words can be reordered into `aabb`. Clearly, the minimum number of nodes in the trie should be $5$ (including the root node that represents the empty prefix). ------------ #### Constraints For $100\%$ of the testdata, it is guaranteed that $1\le n\le 16$. The sum of the lengths of all words does not exceed $10^6$, and all words contain only lowercase letters. ------------ #### Note **This problem is translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T6 Vještica_**。 Translated by ChatGPT 5