← 返回题目列表

Codeforces · 1105/E

E. 帮助 Hiasat

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

Hiasat 在 NeckoForces 注册了一个新帐户,当他的朋友们发现此事后,每个人都要求使用他的名字作为 Hiasat 的账号。

对于 Hiasat 来说幸运的是,他可以在某些时间点改变他的手柄。他还知道朋友们访问他的个人资料页面的确切时间。正式地,您将获得两种类型的事件序列:

- $$$1$$$ — Hiasat 可以更改他的昵称。
- $$$2$$$ $$$s$$$ — 好友 $$$s$$$ 访问了 Hiasat 的个人资料。

朋友$$$s$$$会很高兴,如果他每次访问Hiasat的个人资料时他的句柄都是$$$s$$$。

Hiasat 要求你帮助他,找到他能获得的最大可能数量的快乐朋友。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 40$$$) — 事件数和好友数。

然后是 $$$n$$$ 行,每行表示以下两种类型之一的事件:

- $$$1$$$ — Hiasat 可以更改他的昵称。
- $$$2$$$ $$$s$$$ — 好友 $$$s$$$ ($$$1 \le |s| \le 40$$$) 访问 Hiasat 的个人资料。

保证每个朋友的名字仅由小写拉丁字母组成。

可以保证,第一个活动始终是第一种类型,每个朋友都会至少访问 Hiasat 的个人资料一次。

输出

打印一个整数——快乐朋友的最大数量。

示例

输入 #1

5 3
1
2 motarack
2 mike
1
2 light

输出 #1

2

输入 #2

4 3
1
2 alice
2 bob
2 tanyaromanova

输出 #2

1

注意

在第一个示例中,最好的方法是将第一个事件中的“motarack”句柄更改为第四个事件中的“light”句柄。这样,“motarack”和“light”会高兴,但“mike”不会。

在第二个示例中,您可以选择“alice”、“bob”或“tanyaromanova”,只有该朋友会感到高兴。