Sanduíche
Uma nova lanchonete abriu na cidade, prometendo um menu com a maior variedade de sanduíches da região. A cada dia o Chef de cozinha compra N ingredientes distintos e prepara o menu usando esses N ingredientes. Infelizmente não é possível ter sanduíches com qualquer combinação de ingredientes: a cada dia o Chef determina que M pares de ingredientes não podem ser utilizados no mesmo sanduíche, porque ele considera que esses ingredientes "não combinam".
Por exemplo, suponha que num determinado dia N é igual a quatro e os ingrediantes são queijo, presunto, goiabada e azeitona, e M é igual a dois: os pares (goiabada, presunto) e (azeitona, goiabada) não podem ser utilizados no mesmo sanduíche. Nesse dia, alguns dos sanduíches que podem ser feitos são:
- presunto, queijo
- azeitona
- presunto, azeitona, queijo
- goiabada, queijo
Alguns dos sanduíches que não podem ser feitos são:
- presunto, queijo, goiabada
- azeitona, goiabada
- goiabada, presunto, azeitona
Dados os N ingredientes e os M pares de ingredientes que não combinam, sua tarefa é determinar qual o máximo número de sanduíches diferentes que podem ser feitos. Dois sanduíches A e B são considerados diferentes se A contém um ingrediente X que não está presente em B ou se B contém um ingrediente Y que não está presente em A. Um sanduíche deve conter ao menos um ingrediente.
Entrada
A primeira linha contém dois números inteiros N e M, indicando respectivamente o número de ingredientes e o número de pares de ingredientes que não combinam. Os ingredientes são identificados por números de 1 a N. Cada uma das M linhas seguintes contém dois números inteiros X e Y que representam um par de ingredientes que não combinam.
Saída
Seu programa deve produzir uma única linha, o número de sanduíches diferentes que podem ser feitos.
Restrições
- 1 ≤ N ≤ 20
- 0 ≤ M ≤ 400
- 1 ≤ X ≤ N
- 1 ≤ X < Y
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 10 pontos, N ≤ 5.
- Para um conjunto de casos de testes valendo outros 40 pontos, N ≤ 10.
- Para um conjunto de casos de testes valendo outros 50 pontos, nenhuma restrição adicional.
Exemplos
Entrada
3 2 2 3 1 2 |
Saída
4 |
Entrada
3 0 |
Saída
7 |
Entrada
3 3 1 2 2 3 1 3 |
Saída
3 |
