Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3281
File System Travel

Time Limit: 2 Seconds      Memory Limit: 32768 KB

There is a file system whose structure is a tree structure which has only one root. Mr Mouse's home is located in this root. In this file system, he can walk between different directory.
He can enter a subdirectory by a double click he can go up to parent-directory by a single click.

Mr Mouse's life only lasts for n seconds which is very short, so he wants to travel the file system as deep as he can.

In the past, Mr Mouse's ancestors can not travel too deep as they were limited by aps which means they can do only aps times click every second.

However, Mr Mouse has his own aps too. Luckliy, modern file systems support a file named Link.
Links are located in some directories. When Mr Mouse is in these directories, he can be transformed to another directory immediately by double click the Link.

Besides, Mr Mouse must return back to his home before the end of his life.

NOTES: One directory's Depth means the number of directories Mr Mouse has to pass throught before he arrives at this directory while he doesn't use Link.

Input

There are multiple cases.
The first line in each case is n and aps. (0 <= n <= 500 , 0 <= aps <= 15)
The second line is m which means there are m directories.
Then next m lines descripe the file system. (1 <= m <= 5000)
Each line begin with a string which is one directory's name.
Then there are few strings follow it which is his subdirectory's or Link's names in this directory.
Every directory's length is less than 50 and only contains lowercase, uppercase or number.
Every Link's name will begin with "Link:" followed by a directory's name which this Link links to. Every directory has distinct name while every link will be pointed to an existing directory.
The first directory will be Mr Mouse's home.
The number of test case will no more than thirty.

Output

For each case output the depth Mr Mouse can travel in his life in one line.

Sample Input

2 3
5
A B
B C
C D
D E
E
2 3
5
A B Link:E
B C
C D
D E
E

Sample Output

2
4

Author: MIN, Zhechen
Source: ZOJ Monthly, December 2009
Submit    Status