Un peu de compagnie – Qualification 2016

Énoncé¶

Une nouvelle problématique vient troubler la quiétude post-apocalyptique des Prolosaures : suite à la solitude qui règne sur leurs îles, les Prolosaures en sont venus à se détester, de telle sorte que la plupart d'entre eux ont au moins un rival à haïr. Le téléphone yaourt, qui ne permet pas les communications simultanées, sert alors de carburant, alimentant la haine entre rivaux.

Le grand conseil, préoccupé par la situation, pense avoir trouvé une solution : sur l'une des îles se trouvait une fabrique de talkie-walkies, fonctionnant par paires, dont la portée permet de couvrir toute l'étendue de l'archipel Prolosaure.

Il suffirait que ne soient mis en contact que des couples de Prolosaures entretenant de bonnes relations, en prenant garde à ne laisser personne dans la solitude. Il n'est par contre pas nécessaire de rallier un même individu à plusieurs autres, à moins que leurs rivalités ne l'imposent.

Toutefois, les talkie-walkies se font rares, et le conseil en vient à se demander s'il sera un jour possible de mettre ce plan à exécution.

À partir du nombre d'îles et d'une liste de couples d'îles dont les habitants ne souhaitent pas communiquer avec ceux de l'autre île, écrivez un programme qui indique le nombre minimal de couples de talkie-walkies nécessaires. On vous garantit qu'aucun Prolosaure n'est détesté de tous.

Entrée¶

L'entrée comprendra :

• sur la première ligne, un entier naturel représentant le nombre d'îles à rallier, noté n ;
• sur la seconde ligne, un entier représentant le nombre de rivalités animant les Prolosaures, noté m ;
• sur les m lignes suivantes, des couples d'identifiants d'îles (entiers compris entre 0 et n-1) indiquant que leurs occupants se détestent, séparés par une espace (on note que les paires fournies ne sont pas redondantes, et que le premier identifiant sera toujours inférieur au second).

Sortie¶

Vous afficherez en sortie :

• le nombre minimal de paires de talkie-walkies nécessaires pour que chaque île dispose d'au moins un talkie-walkie et ne communique qu'avec des Prolosaures non hostiles.

Contraintes¶

• 1 ≤ n ≤ 200 ;
• 1 ≤ m ≤ n(n-1)/2.