← 返回题目列表

Codeforces · 1482/H

H. 考试

中文机器翻译题面 查看原题

今年木叶再次举办中忍选拔考试,参加考试的有$$$n$$$忍者,名字分别为$$$s_1$$$、$$$s_2$$$、...、$$$s_n$$$。所有的名字都是不同的。考试阶段之一包括参与者之间的战斗。今年每场比赛确定忍者的规则如下:如果满足以下条件,忍者 $$$i$$$ 和 $$$j$$$ 将相互对战:

- $$$i \neq j$$$;
- $$$s_{j}$$$ 是 $$$s_{i}$$$ 的子串;
- 除了$$$i$$$和$$$j$$$之外,没有$$$k$$$,$$$s_{j}$$$是$$$s_{k}$$$的子串,而$$$s_{k}$$$是$$$s_{i}$$$的子串。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

你的任务是找出今年将发生多少场战斗。

输入

第一行由唯一的整数 $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$) 组成,代表考生人数。

以下 $$$n$$$ 行包含它们的名称。没有两个名称重合,所有名称都非空且由小写英文字母组成。所有名称的总长度不超过$$$10^6$$$。

输出

打印代表战斗次数的唯一整数。

示例

输入 #1

5
hidan
dan
hanabi
bi
nabi

输出 #1

3

输入 #2

4
abacaba
abaca
acaba
aca

输出 #2

4

注意

在第一个示例中,hidan 与 dan 战斗,hanabi 与 nabi 战斗,nabi 也与 bi 战斗。名为“hanabi”和“bi”的忍者不会互相战斗,因为有一个名为“nabi”的忍者为他们打破了第三个条件。

在第二个示例中,战斗在 abacaba 和 acaba、abacaba 和 abaca、acaba 和 aca、abaca 和 aca 之间进行。