字符串树

题号：NC274789
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

若干年后，偶尔回想起那个午后，我都有些怅然若失，如果能重来，我是否有机会告诉伊娜小姐呢，只是一句简单的，透着土气的话。

“伊娜，你就是我的 Little09。”

给你 $n$ 个字符串，第 $i$ 个字符串为 $s_i$ 。

定义一棵有根树为 表示树，当且仅当这棵树上所有边都有一个在 $\text{a}\sim\text{z}$ 之间的小写英文字母的边权。

对于一棵表示树上的两个点 $s,t$ ，定义 $f(s,t)$ 表示从 $s$ 到 $t$ 的简单路径上经过的所有边的边权依次拼接而成的字符串。
注意， $f(s,t)$ 不一定与 $f(t,s)$ 相等。

定义一棵表示树为这 $n$ 个字符串的 子串表示树，当且仅当对于每个字符串 $s_i$ 的每个子串 $t$ ，都存在至少一对 $(u,v)$ 满足 $u$ 是 $v$ 的祖先，且 $f(u,v)=t$ 。

定义一棵子串表示树 $T$ 为这 $n$ 个字符串的 最小子串表示树，当且仅当不存在任意一棵这 $n$ 个字符串的子串表示树 $T'$ ，满足 $T'$ 的节点个数 $<T$ 的节点个数。

现在，你需要求出这 $n$ 个字符串的最小字串表示树的节点个数。

输入描述:

第一行一个整数 ，表示给定的字符串个数。
接下来  行，每行一个字符串，表示 。

数据保证：，， 均由  之间的小写英文字母构成。

输出描述:

一个整数，表示最小子串表示树的大小。

示例1

输入

复制

4
abca
caab
bdca
cacb

输出

复制

说明

下图是一种合法的构造方法，需要用到  个点。容易发现不存在点数更少的构造方案。

示例2

输入

复制

2
abbca
bbc

输出

复制

示例3

输入

复制

4
orz
rzfft
zffoftt
ftt

输出

复制