Problema C - Outro Tipo de Tesouro

Este é um problema de output-only.
Ao contrário dos outros problemas em que deves fazer leitura de dados e escrita do output, neste problema deves apenas submeter um ficheiro de texto.

No mundo real um tesouro é algo como ouro ou pedras preciosas, mas no mundo da matemática um tesouro é algo muito mais importante. É algo difícil de encontrar mesmo que saibamos que esteja lá. O nosso tesouro de hoje são cliques!

Vamos supor que temos um grafo com N vértices e M arestas. Um clique é um subconjunto de vértices que estão todos ligados entre si (ou seja, formam um grafo completo). É nos dado um inteiro X e o nosso objetivo é encontrar um clique de tamanho exatamente X. Este problema é muito díficil no geral, mas felizmente os grafos que vamos ter de considerar têm propriedades muito específicas.

O Problema

É nos dado um grafo com N vértices e M arestas assim como um inteiro X, o objetivo é encontrar um clique com X nós.

Input

Cada caso de teste começa com três inteiros separados por espaços, N, o número de vértices, M, o número de arestas, e X, o tamanho do clique pretendido.

Seguem-se M linhas, cada uma com dois inteiros separados por espaços de valores entre 1 e N representando arestas.

É garantido que não há multiplas arestas entre os mesmos dois vértices e que todas as arestas ligam vértices diferentes.

Casos de teste

Há 4 casos de teste, cada um com uma pontuação fixa (sem pontuações parciais para cada um). Devem olhar para cada caso de teste individualmente, os casos não são arbitrários e devem observar e aproveitar a estrutura de cada um para o resolver.

Os casos de teste são os seguintes:

(*) Um grafo aleatório com M arestas é um grafo onde cada aresta é escolhida com a mesma probabilidade. Uma outra forma de pensar no processo é considerar um conjunto com todas as N(N - 1)/2 possíveis arestas e tiramos M arestas de forma uniforme sem reposição.

Output/Submissão

Deve ser submetido um único ficheiro de txt (o formato é importante, o vosso ficheiro deve terminar em .txt). O ficheiro deve conter 4 linhas, uma por caso de teste, cada uma com os cliques pretendidos para o caso de teste, sendo que o formato por linha é o seguinte:

X inteiros distintos entre 1 e N separados por espaços, cada um representando um nó do clique. Podem vir por qualquer ordem.

Observações importantes:

Um exemplo válido de um ficheiro solução seria o seguinte (a sua pontuação é de 0 pontos):

1 2 3

1 2 3 ... 15
1 2 3 4 ... 50

Dicas para gerar o output

Visto que é necessário criar um ficheiro de txt para a vossa submissão, pode ser útil usar o terminal para gerar os ficheiros de texto (isto não é obrigatório, podem criar o ficheiro como quiserem).

Se para correrem o vosso programa usarem o comando X (por exemplo, para C++ isto seria algo como ./a.out, depois de compilar com g++ codigo.cpp), podem usar o seguinte comando para ler o input de um ficheiro inp.txt e escrever para um ficheiro out.txt: X < inp.txt > out.txt.

Para facilitar a organização do ficheiro de submissão, é aconselhado gerar um txt por cada caso de teste, por exemplo, para o caso de teste 2 ter um out2.txt.

Para posteriormente gerar um ficheiro out.txt para submeter, podem usar o seguinte comando (assumindo que têm um ficheiro outI.txt para cada um dos 4 casos de teste I): cat out1.txt > out.txt;cat out2.txt >> out.txt;cat out3.txt >> out.txt;cat out4.txt >> out.txt


Prova de Seleção para as IOI'2021
Prova Online
(3 de Junho de 2021)