← 返回题目列表

AtCoder · agc047_b

B. 第一第二

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

分数: 700 点

问题陈述

Limak 可以重复删除字符串的前两个字符之一, 例如 abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.

你被给予 N 不同的字符串 S_1, S_2, \ldots, S_N。 其中 N \cdot (N-1) / 2 对 (S_i, S_j), 利马克可以从多少对中获得一根绳子和另一根绳子?

约束

  • 2 \leq N \leq 200\,000
  • S_i 由小写英文字母组成 a-z.
  • S_i \neq S_j
  • 1 \leq |S_i|
  • |S_1| + |S_2| + \ldots + |S_N| \leq 10^6

输入

输入由标准输入按以下格式给出。

N
S_1
S_2
\vdots
S_N

输出

打印无序对的数量 (S_i, S_j) 其中 i \neq j 和 Limak 可以从另一个获取一个字符串。


示例输入 1

3
abcxyx
cyx
abc

示例输出 1

1

唯一好的一对是 (abcxyx, cyx).


示例输入 2

6
b
a
abc
c
d
ab

示例输出 2

5

有五对好对: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).