Problem Description

In a friendly and harmonious Minecraft server, Steve enjoys roaming around. The server uses a town mechanism, so there are many towns. There is a town called Jelly Town, where the mayor, who resembles (mistakenly) someone who loves eating jelly, enjoys eating shiny jelly in front of a mirror (mistakenly). Suddenly, he receives good news that a rebellion will soon break out in the town. Startled, he jumps out of bed, takes a bite of jelly (mistakenly), and starts to deal with the situation.

Problem Description

The town has a mayor and n-1 town members, each with a direct superior, fi. Each town member and the mayor have a distance, di (which is the number of superiors between them plus one). The mayor wants all town members to be his direct subordinates, meaning the distance to him should be 1.

Each minute, he can make one of his town members his direct subordinate. At minute t (t > 0), this town member becomes his direct subordinate, and the mayor gains a safety index of (di + t) & k (where & is the bitwise AND operation). Then, all subordinates of this town member will follow this change (meaning their direct superiors remain the same unless the mayor makes them his direct subordinates).

When all town members are his direct subordinates, the mayor can safely enjoy his jelly. He now wants to know how to make these changes to maximize the safety index. Since the mayor is eager to eat his jelly, he assigns this task to you.

Input Format

The first line contains two positive integers, n and k (refer to the problem description for their meanings).
The following n lines each contain two strings (consisting of uppercase and lowercase letters, underscores, digits, apostrophes, or commas), representing a town member and their direct superior. Specifically, the second line represents the mayor, who has no direct superior, so it contains only one string, representing the mayor. The data guarantees that the second string has appeared before the first string.

Output Format

An integer representing the maximum safety value.

Sample Input and Output

Input Sample #1

3 1
1
2 1
3 2

Output Sample #1

1

Input Sample #2

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

Output Sample #2

8

Notes

Sample Explanation
For the second sample, due to the laziness of the problem setter, the movement of child nodes is not listed. Please hack it yourself. (Witty)

Data Range:
Consider the following special cases:
1. The string length is guaranteed to be 1.
2. The tree degenerates into a chain.
For all data, k is within the int range, and the string length does not exceed 10^6. Both n and k are positive integers.

见题面 Input 部分

见题面 Output 部分