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”,只有该朋友会感到高兴。