Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

GINCAN11 - Gincana

 

Toda semana Juquinha tem aulas de ACM (Artes Cênicas e Musicais) no colégio em que estuda e, recentemente, sua professora anunciou que haverá uma gincana no final do semestre. No entanto, os times devem ser formados o mais breve possível para que os alunos possam ensaiar.

Cada time é constituído de um ou mais alunos, e cada aluno tem que pertencer a exatamente um time. Além disso, os times não podem ser formados de qualquer maneira: se um aluno é amigo de outro, esses alunos devem estar no mesmo time. A professora então pediu para que os alunos a informassem das relações de amizade na sala de aula.

Os alunos então se numeraram de 1 até N e escreveram uma lista cujas linhas contém pares de números. Se dois alunos cujos números são i e j são amigos, haverá ao menos uma linha contendo i e j ou j e i na lista. Inversamente, se há uma linha contendo i e j na lista, então os alunos cujos números são i e j são amigos.

A professora então recolheu a lista e, na próxima aula, deverá decidir que times formar. Ela está pensando em formar o maior número possível de times e gostaria de saber quantos times ela formaria. Ajude então a professora escrevendo um programa que, dada a lista de amizades, determina qual o maior número de times que ela pode formar.

Entrada

A primeira linha da entrada contém dois inteiros N e M que representam, respectivamente, o número de alunos na turma e o número de linhas na lista.

As próximas M linhas contêm a lista de amizades. Cada linha contém dois inteiros I e J separados por exatamente um espaço.

Saída

Seu programa deve imprimir uma linha contendo o número máximo de times que podem ser formados pela professora.

Restrições

  • 1 ≤ N ≤ 1000.
  • 0 ≤ M ≤ 5000.
  • 1 ≤ I, JN.

Exemplos

Entrada
3 1
1 3

Saída
2

Entrada
7 6
1 6
6 4
5 2
3 7
2 3
7 2

Saída
2


Adicionado por:Wanderley Guimarăes
Data:2012-02-29
Tempo limite:0.141s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 2 nível junior

hide comments
2016-04-21 17:20:42 Elsio [UFABC]
Monta o grafo, aplica o dfs.
reinicia o dfs ate ter visitado todo o grafo.
conta quantas vezes reiniciou o dfs.
Relacionados:
http://br.spoj.com/problems/ENERGIA/# (facinho)
http://br.spoj.com/problems/OBIDOMIN/# (um pouco mais dificil que esse)
2012-08-27 12:03:08 Diego Climaites [USJT]
O enunciado está correto?
O parágrafo que diz os alunos se numeraram de 1 até n me parece repetitivo...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.