One day, Mary told you that she really liked someone in your class.
However, Mary is so shy that she won't tell who it is.
But curiosity has driven you to try pumping more information from Mary.
For example, you might write to Mary the following:
Then you suddenly realized who it is.
But, the above is an ideal scenario. Because Mary is shy, she is so reluctant that she will not answer too many questions.
Since you know the characteristics of everyone in the class, you are going to ask as few questions as possible from Mary.
No matter who is the person Mary likes, you have to ensure that you will know the answer after asking these questions.
Note that you will write all the questions you are going to ask to Mary before getting any replies from her.
You are going to write a program that determines what the minimum number of question needed is.
The input may contain many cases. In each case, there are 2 numbers, n and m (1<=n<=10000, 0<=m<=12) that
describe the number of students in your class and the number of possible characteristics.
Then the following are n lines, where in each line there is a string denote the name of the student.
Then the following describe the characteristics of people. For each characteristic, there is a string describing
the characteristic followed by an integer ki (1<=ki<=n) denoting the number of people who has this characteristic.
The next line contains exactly ki strings separated by a space which represent the people who have this characteristic.
All the strings in the input only contain "_", digits or upper-case letters and have length at most 24.
For each case, you should output exactly one non-negative integer in a line representing the minimum number of
questions needed to get the answer regardless of who it is. If there is a possibility that you will never know
who it is then output -1.
In the sample input, you can choose to ask "Is he smart?", "Is he handsome?", and "Is he an unicorn?".
Then no matter who is it, you can recognize him from the answers responded by Mary.