## COCI '16 Contest 1 #6 Vještica

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

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:

• Each edge of the tree is denoted with a letter from the alphabet.
• The root of the tree represents an empty prefix.
• All other nodes in the tree represent a non-empty prefix in a way that each node represents a prefix obtained by concatenating letters written on the edges that lead from the root of the tree to that node (in that order).
• There will never be two edges labeled with the same letter coming out of a single node (this way we minimize the number of nodes necessary to represent all prefixes).
Prefix tree for words: A, to, tea, ted, ten, i, in, and inn.

Only after Matej learned what a prefix tree was does the real puzzle begin!

The witch, as you may have guessed, has 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!

#### Input Specification

The first line of input contains the integer .

Each of the following lines contains a single word consisting of lowercase letters of the English alphabet.

The total length of all words will be less than .

#### Output Specification

The first and only line of output must contain a number, the answer to witch Marija's puzzle.

#### Sample Input 1

3
a
ab
abc

#### Sample Output 1

4

#### Sample Input 2

3
a
ab
c

#### Sample Output 2

4

#### Sample Input 3

4
baab
abab
aabb
bbaa

#### Sample Output 3

5

#### Explanation for Sample Output 3

All words can be permuted into the word aabb, so the prefix tree will have 5 nodes (4 + 1 for the root of the tree – the empty prefix).