Parceiros de Telecomunicação
Por Rodolfo Jardim Azevedo 
Brasil
Por Rodolfo Jardim Azevedo Brasil
A ICPC, uma companhia de telecomunicação internacional, quer melhorar sua relação com as empresas que utilizam os seus serviços, oferecendo a estas descontos nas ligações feitas para um determinado conjunto de telefones, sendo este selecionado por cada empresa cliente. Para ajudar a ICPC a decidir o custo para este novo serviço, as empresas clientes da ICPC fizeram uma busca em suas bases de dados e produziram uma lista de chamadas telefônicas feitas de uma empresa para a outra no último ano. Se uma empresa se comunicou com outra (efetuando ou recebendo uma chamada) durante o último ano, diremos que estas são Parceiras de Negócios.
Você foi contratado pela ICPC para processar a lista de ligações do último ano e determinar o tamanho (em número de empresas) do maior conjunto de empresas que são Parceiras de Negócios de pelo menos K outras empresas neste mesmo conjunto e que todas as empresas desse conjunto possam fazer tratos de negócios diretamente ou indiretamente com qualquer outra empresa nesse conjunto (uma empresa pode fazer tratos diretamente com outra, se forem parceiros de negócios e as duas estiverem no conjunto). Isto é, você deve encontrar um conjunto S de empresas tal que toda empresa que pertence a S tem pelo menos K parceiros de negócios que também estão em S (e possivelmente parceiros que estão fora de S), onde K é um parâmetro definido pela ICPC.
Seu programa deverá processar diversos casos de teste. A primeira linha de um caso de teste contém três inteiros N, P e K. N representa o número total de empresas clientes da ICPC (1 ≤ N ≤ 1000); empresas são identificadas por um número entre 1 e N. P representa o total de pares de parceiros de negócios produzidos pela lista de ligações do último ano; e K é o número mínimo de parceiros que uma empresa necessita para pertencer ao conjunto final (1 ≤ K ≤ N-1), como descrito acima. As próximas P linhas descrevem cada par de parceiros de negócios, representados por dois inteiros X e Y, onde X e Y são empresas (1 ≤ X ≤ N, 1 ≤ Y ≤ N e X ≠ Y). O valor N = 0 indica o fim da entrada.
Para cada caso de teste da entrada, seu programa deverá imprimir uma única linha, contendo o tamanho do maior conjunto de empresas encontrado pelo seu programa.
| Exemplo de Entrada | Exemplo de Saída |
|
5 3 1 |
3 |