Construction Conflictuelle – Regional event 2024

Énoncé¶

Le long du littoral de Midgard, une multitude de villes sont disputées par les dieux. Souhaitant renforcer leur puissance, les dieux tentent de créer un réseau d'échange routier entre les villes sous leur domination.

On considère ici $D$ dieux, numérotés de 0 à $D - 1$. $N$ villes sont citées le long du littoral, dans le tableau villes. Dans le tableau, on indique pour chaque ville le dieu qui possède le contrôle de la ville.

Il est possible de rajouter une connexion entre deux villes en créant une route reliant les deux villes par le sud.

• Il est seulement possible de relier deux villes sous le contrôle d'un même dieu ;
• On ne peut pas relier une ville à plus d'une autre ville ;
• Il est impossible que deux routes se croisent, car cela engendrerait un conflit entre les dieux concernés.

Aidez Jøsëf Marchand à planifier la construction du plus grand nombre de routes possible, en évitant tout conflit.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : D, le nombre de dieux.
• Sur la ligne suivante, un entier : N, le nombre de villes.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : villes, pour chaque ville, le dieu qui la contrôle.

Sortie¶

Affichez, sur une ligne, le plus grand nombre de routes que vous pouvez construire sans provoquer le moindre conflit.

Contraintes¶

• $1 \le D \le 10$
• $2 \le N \le 10$
• $0 \le \text{villes[i]} < D$

Contraintes de performance¶

• $1 \le D \le 500$
• $2 \le N \le 500$