Have you seen the movie "You are the apple of my eye" ? It's a romantic movie that talking about 5 men pursuing one lovely girl. It's said that people who doesn't have a boy/girlfriend would rolling tears down as watching this movie.
However, today we are talking about not girls but apples. Orange likes apples so much that he can't stop roaring " Hey! Apple!", and it makes every apples beside him almost going mad. Orange collects apples, which became demented due to Orange's annoying. Orange put his collections on a N*M grid. Each cell contains at most one apple. Orange put these apples in the grid according to some regulations he formulated, and the regulations are as following:
1. For the ith rows (there are N rows) randomly generate a number ki(0<=ki<=M), than generate ki numbers a1, a2, a3... aki ( 1<=aj<=M, for j=1..ki ).
2. Then Orange will put apples on the ( i , aj ) ( j = 1..ki ).
3. No apples will be put in a same cell.
And now, Orange has finished allocating all his apples, he wanna begin chatting with these apples. With his strongly annoying ability, Orange can chat with a whole row's apples each time. And Orange is unwilling to chat with apples on repeated columns. That is, each time Orange would choose a row and chat with all apples on it, supposing there are three apples and these apples are located on x, y, z column, respectively. Then he might chat with another row, but on this row there must none of apples is located on x, y, or z column.
Orange want to choose some rows' apples to talk with and not violate his unwilling mentioned above. He want to know how many rows he have to choose at least so that every M columns have one apple he chat with.
There may be multiple test cases, terminated by EOF.
Each test case consists of two positive integers N (<= 200), M (<= 200), denoting the number of rows and columns of the grid.
Then, following N lines will starting with an integer ki, and ki numbers following, denoting which columns of ith rows should put an apple.
For each test case, output a single line contains the number denoting how many rows Orange have to choose at least so that every M columns have one apple he chat with. If no matter how he choose rows would never satisfied Orange's demand, just output -1.
6 7 3 3 5 6 3 1 4 7 3 2 3 6 2 1 4 2 2 7 3 4 5 7 6 7 3 1 4 7 2 1 4 3 4 5 7 3 3 5 6 4 2 3 6 7 2 2 7
3 3
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|