L'Attaque du Joseph du Milieu – Épreuve régionale 2025

Niveau 6 ⋅ Validation weight: 15%

Énoncé

Joseph Marchand et sa bande, ayant enfin semé les deux gardes à l'entrée de la tour, y entrent enfin ! Cependant, en entrant, un dispositif d'alarme se déclenche dans la tour de contrôle. Il faut faire vite, et empêcher l'alarme de se propager dans les salles des autres gardes !

Heureusement, Joseph Mappant dispose d'une cartographie des environs. Le système de communication est en fait un réseau d'alarmes reliées par des canaux de communication unidirectionnels.

Les canaux peuvent former un cycle, mais tous les signaux d'alarme sont envoyés depuis une unique source : la tour de contrôle, notée $1$.

Votre objectif va être de trouver des points stratégiques afin d'empêcher la propagation de l'alarme à des endroits précis. On considère qu'une alarme $A$ contrôle une alarme $B$ si la suppression de $A$ empêcherait l'alarme $B$ de se déclencher, ou plus formellement, s'il n'existe aucun chemin de la tour de contrôle à $B$ qui ne passe pas par $A$.

Dans l'exemple ci-dessous, l'alarme $2$ ne contrôle pas l'alarme $4$ car même en désactivant l'alarme $2$, l'alarme $4$ peut récupérer le signal depuis l'antenne $3$. En revanche, la tour de contrôle ($1$) contrôle bien l'alarme $4$.

Exemple non contrôlé

Parfois, il arrive qu'une alarme soit contrôlée par plusieurs autres alarmes. Dans l'exemple ci-dessous, les alarmes $1$ et $2$ contrôlent l'alarme $3$.

Exemple contrôlé

Dans ce cas-là, pour une certaine alarme $A$, on nomme le plus proche contrôleur de $A$ l'alarme pouvant contrôler $A$ étant également contrôlée par toutes les autres alarmes contrôlant $A$. On peut démontrer que, mis à part pour la tour de contrôle, chaque alarme possèdera toujours un unique plus proche contrôleur.

Dans l'exemple précédent, le plus proche contrôleur de l'alarme $3$ est l'alarme $2$, car elle est également contrôlée par l'alarme $1$, et non l'inverse.

Afin de pouvoir planifier leur sabotage pour empêcher la propagation de l'alarme, aide Joseph en déterminant le plus proche contrôleur de chaque alarme.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'alarmes.
  • Sur la ligne suivante, un entier : M, le nombre de canaux de transmission.
  • Sur les lignes suivantes, une liste de M éléments : canaux, la liste des canaux de transmission.
    • Une ligne par élément de la liste : séparés par des espaces, un entier A (l'alarme envoyant le signal), et un entier B (l'alarme recevant le signal).

Sortie

Afficher, sur une ligne, dans l'ordre, et séparés par des espaces, le plus proche contrôleur de toutes les alarmes (excepté la tour de contrôle).

Contraintes

  • $2 \le N \le 100$
  • $1 \le M \le 100$
  • $1 \le A \le N$
  • $1 \le B \le N$

Contraintes de performance

  • $2 \le N \le 200\,000$
  • $1 \le M \le 320\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

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

Voici le schéma des alarmes telles que décrit par l'entrée :

Exemple

Calculons pour chaque alarme (exceptée la tour de contrôle) la liste des alarmes qui la contrôlent.

L'alarme $2$ étant un fils immédiat de la tour de contrôle, elle est contrôlée uniquement par celle-ci. Son plus proche contrôleur est donc $1$.

L'alarme $3$ est contrôlée par la tour de contrôle ainsi que par l'alarme $2$. L'alarme $2$ étant contrôlée par la tour de contrôle et non l'inverse, c'est elle qui fait office de plus proche contrôleur pour l'alarme $3$.

L'alarme $4$ est contrôlée par les alarmes $1$, $2$ et $3$. L'alarme $3$ étant elle-même contrôlée par les alarmes $1$ et $2$, c'est elle le dernier piégeur de $4$.

On affiche donc sur la sortie standard, dans l'ordre, $1$, puis $2$, puis $3$.