题目背景

赛时答疑

数据已经修复

[生存世界]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行，每行有两个字符串（由大写字母、小写字母、下划线、数字、上引号或者逗号组成），分别表示的是这个镇员和他的直属上司。特别地，第二行是镇长，他没有直属上司，所以第二行只有一个字符串，表示镇长。数据保证第二个字符串在第一个字符串前出现过。

输出格式

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

3 1
1
2 1
3 2

1

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

8

提示

样例解释 第二个样例: （图片有可能会挂，请耐心等待一会哦qwq）




由于出题人过懒，移动子节点的情况就未列举。请自行hack自己。（滑稽）

数据范围：
记下列两种特殊情况：
1.保证字符串长度为1
2.树退化成一条链

对于所有的数据，保证k在int范围内，字符串长度不超过10^6。n,k均为正整数。