Quick Search#1816
A police unit is faced with situations where they must search multiple locations as quickly as possible with a small group of officers. Figures 1 and 2 show diagrams of two such situations. The locations to be searched are marked with capital letters. The location marked with is the common starting point. Some of these locations are connected by paths. Each connecting path takes one unit of time to traverse; searching individual locations visually requires no extra time.
Consider Figure 1. If there are or more officers, the search takes only one unit of time. Different officers follow the paths AB, AC, and AD. If there are two officers, the complete search takes two time units. For example, one officer could follow ABC, and the other AD.
Consider Figure 2. If there were officers, they could follow the paths ABC, ABD, and AEAF, taking units of time. With officers, they could follow ABCBD and AEAF, taking units of time.
These are simple enough examples to solve by hand. For more complex scenarios, your programming help is needed.
The input consists of to data sets, followed by a line containing only .
Each data set is a single line starting with the space-separated positive integers , where is the number of locations to search, is the number of officers, and is the number of connecting paths. Constraints: 2 \leq s \leq 10, 1 \leq n \leq 4, and p \leq 20. The rest of the line contains pairs of capital letters, each separated by a space, representing the paths between locations. The locations are labeled with the first capital letters. All locations will be connected by some sequence of connecting paths. The two letters in each pair are in ascending alphabetical order. No letter pair is repeated.
For each data set, print a single line containing the minimum search time for officers starting from location .
Be careful with your algorithm, or your solution may take too long.
The sample input data sets correspond to the scenarios discussed.
Example 1