Matraquenard – Épreuve régionale 2025

Niveau 5 ⋅ Validation weight: 20%

Énoncé

Arrivés devant la présupposée tour de contrôle, Joseph Marchand et Joseph Martial y trouvent deux gardes devant les différentes entrées de la tour. Il s'agit de Traque & Matraque !

Malheureusement, Joseph se fait repérer, et les deux gardes se lancent à sa poursuite !

La ville est représentée par un graphe non orienté, où chaque arête représente une rue, et chaque sommet représente une intersection entre deux rues. Joseph, Traque et Matraque se situent sur trois sommets du graphe (pas nécessairement distincts) donnés en entrée.

Joseph tente alors d'échapper aux deux gardes qui essaient de l'attraper, c'est-à-dire de se trouver sur le même sommet que Joseph à la fin de leur tour.

À leur tour, Joseph, Traque et Matraque sont obligés de se déplacer. Joseph est le premier à se déplacer, puis Traque, puis Matraque. Ils continueront à suivre cet ordre en boucle jusqu'à ce que Joseph ne se fasse intercepter, à moins qu'il soit impossible pour Traque et Matraque d'attraper Joseph à coup sûr. On compte la fin d'un tour dès que l'une des personnes se déplace.

Votre objectif est d'aider Joseph à déteminer s'il peut échapper indéfiniment à Traque et Matraque, ou, dans le cas contraire, de combien de temps il dispose avant que ses ravisseurs n'arrivent à leurs fins. Pour cela, on suppose que Joseph, Traque et Matraque se déplacent de manière optimale, Joseph cherchant à maximiser le temps avant de se faire attraper, et Traque et Matraque coopérant pour attraper Joseph en un minimum de temps.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, nombre d'intersections dans la ville.
  • Sur la ligne suivante, un entier : M, nombre de rues.
  • Sur la ligne suivante, des entiers séparés par des espaces :
    • joseph, position de Joseph Marchand.
    • traque, position de Traque.
    • matraque, position de Matraque.
  • Sur les lignes suivantes, une liste de M éléments : rues, liste des rues composant la ville.
    • Une ligne par élément de la liste : séparés par des espaces, un entier intersection 1 (1ère intersection), et un entier intersection 2 (2ème intersection).

Sortie

Afficher, sur une ligne, le temps nécessaire au minimum à Traque et Matraque pour intercepter Joseph. Si Joseph peut fuir à l'infini, afficher -1.

Contraintes

  • $3 \le N \le 12$
  • $2 \le M \le 24$
  • $1 \le \mathtt{joseph} \le N$
  • $1 \le \mathtt{traque} \le N$
  • $1 \le \mathtt{matraque} \le N$
  • $1 \le \mathtt{intersection 1} \le N$
  • $1 \le \mathtt{intersection 2} \le N$

Contraintes de performance

  • $3 \le N \le 100$
  • $2 \le M \le 200$

Contraintes d'exécution

Utilisation mémoire maximum
300000 kilo-octets
Temps d'exécution maximum
2500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
4
1 3 4
1 2
1 3
2 4
3 4
Exemple de sortie
3
Commentaire

Le graphe ci-dessous représente la ville décrite en entrée.

Exemple 1

Joseph (J) commence son premier déplacement. Afin de ne pas se faire attraper immédiatement, il choisit de se déplacer sur le sommet $2$. Vient ensuite le tour de Traque (T), qui se déplace indifférement sur le sommet $1$ ou $3$ (dans notre cas, ce choix n'impactera pas la suite des déplacements). Enfin, Matraque (M) se déplace sur le sommet $2$ pour attraper Joseph.

Joseph se fait donc attraper à la suite du troisième tour. Il faut donc afficher 3.

Exemple d'entrée
8
12
8 3 2
1 2
2 4
4 3
3 1
3 5
5 6
6 4
2 8
8 7
7 1
7 5
6 8
Exemple de sortie
-1
Commentaire

Le graphe ci-dessous représente la ville décrite en entrée.

Exemple 2

À partir de cette position, Joseph (J) aura toujours à son tour un déplacement qui l'éloigne d'au moins deux rues de Traque (T) et Matraque (M). Si Joseph se déplace correctement, il ne se fera jamais attraper.

Il faut donc afficher -1.