Énoncé¶
Enfin sorti de la salle précédente, vous passez par un sas avant d'accéder à la prochaine épreuve. Cependant, vous vous rendez compte que la porte permettant d'accéder à la prochaine salle, supposée ouverte, est cassée !
Il va donc falloir trouver un moyen de l'ouvrir.
Vous étudiez le système des portes en observant la porte d'entrée que vous venez d'emprunter et comprenez très vite le principe : Un réseau de puces est positionné sur chaque porte, chaque puce étant reliée aux autres par des fils. Si les puces ne sont pas toutes connectées entre elles, il est impossible d'ouvrir une porte : le graphe formé doit être connexe pour pouvoir espérer ouvrir la porte. Une fois que le graphe est connexe, le mécanisme d'ouverture active la puce centrale du graphe, ce qui déclenche l'ouverture de la porte. Une puce est dite centrale si la suppression de celle-ci dans un graphe connexe de $N$ puces entraîne une décomposition de ce graphe en plusieurs composantes connexes d'au plus $\lceil N/2 \rceil$ puces chacune.
Vous analysez donc à présent la porte de sortie supposée être ouverte, et vous constatez que le réseau de puces n'est pas endommagé : le réseau forme un arbre, chaque puce est reliée au réseau, la porte est censée pouvoir s'ouvrir. Cependant, c'est le mécanisme d'activation qui ne fonctionne plus ! La puce centrale n'est plus reliée au bouton d'ouverture de la porte. Heureusement, vous avez tout juste moyen d'insérer un câble pour pouvoir connecter une puce au bouton. Mais malheureusement, vous n'avez pas de câble sur vous !
C'est alors qu'il vous vient une idée : Vous allez devoir minutieusement retirer certains fils de la porte d'entrée, en prenant bien garde à ne jamais bloquer la porte, cela pourrait déclencher un système d'alarme ! Vous pouvez retirer un fil sans déclencher l'alarme que si le réseau de puce reste connexe après la suppression du fil, et que chaque puce centrale reste centrale après la suppression de ce fil. Vous allez ensuite pouvoir mettre bout à bout chaque fil retiré pour former un plus long câble, d'une longueur égale à la somme des longueurs de chaque fil. Vous allez tenter d'insérer ce câble, si possible, afin de relier une puce centrale de la porte de sortie au bouton de déclenchement. Attention, chaque puce se situe à une distance précise du bouton, et certaines puces peuvent ne pas être atteignables si elles sont trop loin du bouton pour être reliées par votre câble ! Si vous avez réussi à connecter une puce centrale de la porte de sortie au bouton, vous devriez pouvoir ouvrir la porte et passer à l'épreuve suivante !
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : pucesEntree, le nombre de puces présentes sur la porte d'entrée.
- Sur la ligne suivante, un entier : filsEntree, le nombre de fils présents sur la porte d'entrée.
- Sur les lignes suivantes, une liste de filsEntree éléments : entree,
liste des fils présents sur la porte d'entrée.
- Une ligne par élément de la liste : séparés par des espaces, un entier puceEntree1 (première extrémité du fil), un entier puceEntree2 (seconde extrémité du fil), et un entier longueur (longueur du fil).
- Sur la ligne suivante, un entier : pucesSortie, le nombre de puces présentes sur la porte de sortie.
- Sur la ligne suivante, un entier : filsSortie, le nombre de fils présents sur la porte de sortie.
- Sur les lignes suivantes, une liste de filsSortie éléments : sortie,
liste des fils présents sur la porte de sortie.
- Une ligne par élément de la liste : séparés par des espaces, un entier puceSortie1 (première extrémité du fil), et un entier puceSortie2 (seconde extrémité du fil).
- Sur la ligne suivante, une liste de pucesSortie entiers séparés par des espaces : distance, distance entre le bouton et chaque puce présente sur la porte de sortie.
Sortie¶
S'il est possible d'ouvrir la porte, afficher l'index de la puce (indexé à 0) qui permet d'ouvrir la porte. Sinon, afficher "-1".
Contraintes¶
- $2 \le pucesEntree \le 1\,000$
- $1 \le filsEntree \le 2\,000$
- $2 \le pucesSortie \le 1\,000$
- $1 \le filsSortie \le 999$
- $0 \le distance[ ] \le 1\,000\,000\,000$
- $0 \le longueur \le 100\,000$
- Il est garanti que le réseau situé sur la porte d'entrée est connexe.
- Il est garanti que le réseau situé sur la porte de sortie forme un arbre.
- Il est garanti que le réseau situé sur chaque porte possède au moins une puce centrale.
- Il est garanti qu'il n'existe jamais plus d'une solution valide.
Contraintes de performance¶
- $2 \le pucesEntree \le 100\,000$
- $1 \le filsEntree \le 200\,000$
- $2 \le pucesSortie \le 100\,000$
- $1 \le filsSortie \le 99\,999$