SPOJ Brasil

Armando, um funcionário do Banco Central da Sildávia, descobriu que há nos cofres do banco cerca de U$ 164,5 milhões. Como Armando não é a pessoa mais honesta do mundo, ele decidiu que irá tentar roubar esse dinheiro.

As paredes do cofre, porém, são revestidas por uma grossa camada de titânio, de forma que é inviável entrar nele exceto pela porta. Essa porta usa uma trava eletrônica extremamente sofisticada. Existem 32 chaves eletrônicas, e a porta só se abre se pelo menos M delas estiverem presentes. Cada um dos diretores do banco possui um microchip contendo zero ou mais dessas chaves implantado em algum lugar de seu corpo.

Assim, Armando concluiu, a única maneira de realizar o roubo é sequestrar alguns dos diretores do banco e trazê-los até a porta do cofre. Porém, sequestrar vários diretores ao mesmo tempo sem chamar a atenção da polícia é uma tarefa difícil. Assim, Armando quer minimizar o número de diretores a serem sequestrados. Ele, porém, está tendo dificuldade em determinar exatamente qual é o número mínimo e repassou essa tarefa a você.

Ele criou uma lista de diretores que ele crê que consegue sequestrar, e das chaves carregadas por cada um desses diretores. Dado o número mínimo de chaves M necessário para abrir a porta do cofre e uma lista das chaves que cada diretor possui, determine o número mínimo de pessoas que Armando deve sequestrar de forma a conseguir abrir o cofre.

Observações

• As chaves são identificadas por inteiros entre 0 e 31, inclusive;
• Quaisquer M chaves distintas abrem o cofre.

Entrada

A entrada começa com uma linha contendo um inteiro T, o número de casos de teste (1 ≤ T ≤ 20). Em seguida, há T casos de teste.

Cada caso de teste começa com uma linha contendo dois inteiros M (0 ≤ M ≤ 32) e D (1 ≤ D ≤ 20), respectivamente o número mínimo de chaves necessário para abrir o cofre e o número de diretores que podem ser sequestrados. Em seguida, há D linhas, uma para cada diretor.

Cada uma dessas linhas começa com um inteiro C (0 ≤ C ≤ 32), o número de chaves distintas presentes no microchip daquele diretor. Em seguida, há C inteiros identificando as chaves. Cada chave é identificada por um inteiro entre 0 e 31, inclusive.

Saída

Para cada caso de teste, imprima uma linha na saída contendo um inteiro que representa o número mínimo de diretores a serem sequestrados para que o assalto seja realizado com sucesso. Se for impossível conseguir abrir o cofre usando apenas os diretores da lista, imprima "Desastre!".

Exemplos

Entrada:
3
5 2
6 1 13 23 24 26 29
0
5 3
2 10 15
3 0 10 15
3 0 2 10
4 4
3 9 19 20
2 19 20
2 9 19
3 17 19 20

Saída:
1
Desastre!
2

No primeiro caso de teste, o primeiro diretor possui mais chaves do que o necessário, então basta sequestrá-lo.

No segundo caso, os três diretores juntos possuem apenas 4 chaves distintas (0, 2, 10, 15), de forma que não é possível obter as 5 chaves necessárias para se abrir o cofre.

No terceiro caso, nenhum diretor isoladamente possui 4 chaves. Porém, se sequestrarmos o quarto diretor (com as chaves 17, 19, e 20), podemos sequestrar também ou o primeiro ou o terceiro diretor (que possuem a chave 9) e abrir o cofre. Assim, 2 diretores são o suficiente.