← 返回题目列表

Codeforces · 1263/D

D. 秘密密码

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

一名身份不明的黑客想要获取AtForces测试系统的管理员密码,以便在下次比赛中出现问题。为了实现这一目标,他潜入管理员办公室并偷了一张纸,上面列出了 $$$n$$$ 密码 - 字符串,由小拉丁字母组成。

黑客回家并开始准备攻击 AtForces。他发现系统只包含被盗列表中的密码,并且系统确定密码 $$$a$$$ 和 $$$b$$$ 的等价性如下:

- 如果 $$$a$$$ 和 $$$b$$$ 中都存在一个字母,则两个密码 $$$a$$$ 和 $$$b$$$ 是等效的;
- 如果列表中存在密码 $$$c$$$,则两个密码 $$$a$$$ 和 $$$b$$$ 是等效的,这相当于 $$$a$$$ 和 $$$b$$$。

如果系统中设置了密码并使用等效密码来访问系统,则用户可以访问系统。

例如,如果列表包含密码“a”、“b”、“ab”、“d”,则密码“a”、“b”、“ab”彼此等效,但密码“d”不与列表中的任何其他密码等效。换句话说,如果:

- 管理员密码是“b”,那么您可以使用以下任意密码访问系统:“a”、“b”、“ab”;
- admin的密码是“d”,那么您只需使用“d”即可访问系统。

列表中只有一个密码是测试系统的管理员密码。帮助黑客计算保证访问系统所需的最少密码数量。请记住,黑客不知道系统中设置了哪个密码。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 列表中的密码数量。接下来的 $$$n$$$ 行包含列表中的密码 – 非空字符串 $$$s_i$$$,长度最多 $$$50$$$ 个字母。有些密码可能是相同的。

保证所有密码的总长度不超过$$$10^6$$$个字母。它们全部仅由小写拉丁字母组成。

输出

在一行中打印最少数量的密码,使用这些密码将保证访问系统。

示例

输入 #1

4
a
b
ab
d

输出 #1

2

输入 #2

3
ab
bc
abc

输出 #2

1

输入 #3

1
codeforces

输出 #3

1

注意

在第二个示例中,黑客需要使用任何密码来访问系统。