果冻

题目背景

[赛时答疑](https://www.luogu.org/discuss/show/80694) **数据已经修复** [生存世界]Steve:你们哪位dalao可以收留我啊qwq 在minecraft一个很友善、亲和的服务器里面,Steve很喜欢在里面畅游,服务器采用小镇机制,于是有很多小镇。有一个镇叫果冻镇,镇长长得很像(误)喜欢吃果冻,他很喜欢对着镜子(误)吃着blingbling的果冻。突然,他收到捷报,镇上不久就要造反。他吓得一跳,赶紧从床上跳了起来qwq,吃了一口果冻(误),着手处理这件事情。

题目描述

镇上有一个镇长以及n-1个镇员,所有的镇员都有着他的直属上司fi。每个镇镇员与镇长都有一个距离di(也就是他与镇长之间上司的人数+1)。镇长想要所有镇员都是自己的直属下司,也就是与他的距离为1。 他每分钟可以让自己的一个镇员变为自己的直属下司,在第t (t>0)分钟的时候,(也就是每一分钟的意思,而t将从1开始),这个镇员变为自己的直属下司,镇长可以收获(di+t)&k的安全指数(其中,&为按位与运算)。然后**这个镇员的下司都会跟着这个镇员一起变动**(也就是这个镇员的直属下司仍然是这个镇员的,除非镇长把这个下司变为自己的直属下司)。 当所有镇员都是自己的直属下司后,qwq镇长就可以安心吃他的果冻了。他现在想问你,应该怎样变动,才能使安全指数最大。因为镇长很想快点吃到果冻,_(:зゝ∠)\_他就把这个任务交给你了。

输入输出格式

输入格式


第一行是两个正整数n和k(具体意义请见题目描述) 从第二行开始,下面连续n行,每行有两个字符串(由大写字母、小写字母、下划线、数字、上引号或者逗号组成),分别表示的是这个镇员和他的直属上司。**特别地,第二行是镇长,他没有直属上司,所以第二行只有一个字符串,表示镇长**。数据保证第二个字符串在第一个字符串前出现过。

输出格式


一个整数,表示最大的安全值。

输入输出样例

输入样例 #1

3 1
1
2 1
3 2

输出样例 #1

1

输入样例 #2

7 3
LDLD
tk_sky LDLD
Jayden_deng LDLD
only_xiaohuang tk_sky
Muddled_xiaopan tk_sky
Inkn only_xiaohuang
ipdjkl only_xiaohuang

输出样例 #2

8

说明

**样例解释** 第二个样例: (图片有可能会挂,请耐心等待一会哦qwq) ![](https://s1.ax1x.com/2018/10/28/ic6RmQ.png) ![](https://s1.ax1x.com/2018/10/28/ic6Wwj.png) ![](https://s1.ax1x.com/2018/10/28/ic6fTs.png) ![](https://s1.ax1x.com/2018/10/28/ic64kn.png) ![](https://s1.ax1x.com/2018/10/28/ic6gOg.png) 由于~~出题人过懒~~,移动子节点的情况就未列举。请自行hack自己。(滑稽) **数据范围:** 记下列两种特殊情况: 1.保证字符串长度为1 2.树退化成一条链 ![]( https://cdn.luogu.com.cn/upload/pic/39861.png) 对于所有的数据,保证k在int范围内,字符串长度不超过10^6。n,k均为正整数。