Une entreprise emploie $n$ personnes, dont une est le directeur. Chaque employé, à l'exception du directeur, a exactement un supérieur hiérarchique direct.
Chaque employé effectue un travail bien défini. Si l'employé $a$ a besoin d'un travail effectué par l'employé $b$, il doit lui envoyer une demande. Selon les règles de l'entreprise, une demande ne peut être transmise directement que d'un employé à son supérieur direct, ou inversement, d'un supérieur à son subordonné direct. Elle est transmise d'employé en employé jusqu'à atteindre $b$.
Pour alléger la charge des employés, l'entreprise a embauché $k$ coursiers. Le coursier $i$ est affecté à la paire d'employés $a_i,b_i$ et transporte leurs demandes. Quand l'un doit envoyer une demande à l'autre, il la confie au coursier, qui la transmet successivement entre les employés conformément aux règles de l'entreprise, jusqu'à ce qu'elle ait traversé tous les intermédiaires nécessaires et atteigne son destinataire. Lors de la livraison d'une demande, le coursier ne visite pas deux fois le même employé.
Afin de réduire les dépenses, l'entreprise souhaite trouver les deux coursiers dont les trajets se recouvrent le plus, puis se passer de l'un d'eux en confiant son travail à l'autre. Le degré de duplication d'une paire de coursiers est le nombre de passages entre un employé et son supérieur direct, dans l'un ou l'autre sens, qui appartiennent aux trajets des deux coursiers.
Écrivez un programme qui trouve deux coursiers ayant le plus grand degré de duplication.
Entrée
La première ligne contient deux entiers $n$, le nombre d'employés, et $k$, le nombre de coursiers ($2\le n,k\le2\cdot10^5$). Les employés sont numérotés de $1$ à $n$ ; le directeur porte le numéro $1$.
La deuxième ligne contient $n-1$ entiers $p_2,p_3,\ldots,p_n$, les numéros des supérieurs directs de tous les employés sauf le directeur ($1\le p_i<i$).
Les $k$ lignes suivantes contiennent chacune deux entiers $a_i,b_i$, les numéros des employés de la paire affectée au coursier $i$ ($1\le a_i,b_i\le n$ ; $a_i\ne b_i$). Plusieurs coursiers peuvent être affectés à la même paire d'employés.
Sortie
La première ligne doit contenir un entier : le plus grand degré de duplication de deux coursiers.
La deuxième ligne doit contenir deux entiers distincts compris entre $1$ et $k$ : les numéros des coursiers d'une paire ayant ce degré de duplication maximal. S'il existe plusieurs paires, vous pouvez afficher n'importe laquelle.
Remarque
On dit que l'employé $a$ obéit aux ordres de l'employé $b$ si $b$ est le supérieur direct de $a$, ou si le supérieur direct de $a$ obéit aux ordres de $b$. On appelle naturellement important un coursier qui transmet des demandes d'un employé à quelqu'un qui obéit à ses ordres, ou dans le sens inverse.
Sous-tâches
| Sous-tâche | Points | $n$ | $k$ | Contraintes supplémentaires | Sous-tâches requises |
|---|---|---|---|---|---|
| 1 | 29 | $2\le n\le100$ | $2\le k\le100$ | — | |
| 2 | 12 | $2\le n\le4000$ | $2\le k\le1000$ | — | 1 |
| 3 | 7 | $2\le n\le10^5$ | $2\le k\le1000$ | — | 1–2 |
| 4 | 8 | $2\le n\le10^5$ | $2\le k\le5000$ | — | 1–3 |
| 5 | 10 | $2\le n\le10^5$ | $2\le k\le50\,000$ | Le nombre de passages entre chaque employé et le directeur ne dépasse pas 20 | |
| 6 | 12 | $2\le n\le10^5$ | $2\le k\le50\,000$ | Chaque coursier est important | |
| 7 | 12 | $2\le n\le10^5$ | $2\le k\le50\,000$ | — | 1–6 |
| 8 | 10 | $2\le n\le2\cdot10^5$ | $2\le k\le2\cdot10^5$ | — | 1–7 |
Exemples
Entrée 1
4 2 1 2 2 1 3 1 4
Sortie 1
1 2 1
Entrée 2
4 2 1 2 3 1 2 3 4
Sortie 2
0 1 2
Entrée 3
7 3 1 2 2 4 5 5 1 3 3 7 6 1
Sortie 3
2 2 3
Entrée 4
4 3 1 2 3 1 4 4 1 1 4
Sortie 4
3 2 1
Remarque
Le premier exemple comporte deux coursiers. Le premier livre les demandes de l'employé 1 à l'employé 3 ou inversement. Pour livrer de 1 à 3, il transmet d'abord la demande de 1 à 2, puis de 2 à 3. Le deuxième livre de 1 à 4 ou inversement. Par exemple, pour livrer de 4 à 1, il transmet d'abord de 4 à 2, puis de 2 à 1. Leur degré de duplication vaut 1, car ils ont en commun le passage entre l'employé 1, le directeur, et l'employé 2.
Le deuxième exemple comporte aussi deux coursiers, mais leurs trajets ne se croisent pas.
Le troisième exemple est représenté ci-dessus. Les traits épais représentent les passages entre employés. Les traits fins représentent le trajet du premier coursier entre les employés 1 et 3. Les pointillés longs représentent le trajet du deuxième coursier entre 3 et 7. Les pointillés courts représentent celui du troisième coursier entre 1 et 6.
Les trajets des premier et deuxième coursiers ont seulement en commun le passage entre les employés 2 et 3. Ceux des premier et troisième coursiers ont seulement en commun le passage entre 1 et 2. Ceux des deuxième et troisième coursiers ont en commun deux passages : entre 2 et 4, et entre 4 et 5. La paire de coursiers 2 et 3 a donc le degré de duplication maximal, égal à 2.
Dans le quatrième exemple, tous les coursiers transportent les demandes entre le directeur et l'employé 4. Toutes les paires ont donc un degré de duplication égal à 3. Vous pouvez afficher n'importe quelle paire.
Informations communes aux problèmes du deuxième tour
Résultats de l'évaluation pendant le tour
Pour tous les problèmes, vous pouvez demander les résultats de l'évaluation finale un nombre illimité de fois. Pour chaque sous-tâche, les points obtenus et le résultat du programme sur chaque test sont indiqués.
Taille du code source
Pour tous les problèmes, le fichier du code source de la solution ne doit pas dépasser 256 Ko.
Déroulement de l'évaluation
Les points d'une sous-tâche ne sont attribués que si tous ses tests sont réussis. Le tableau de notation indique les numéros des sous-tâches requises pour chaque sous-tâche. Ses tests ne sont exécutés que si toutes les sous-tâches requises sont réussies.
Remarque
Pour les problèmes dont l'entrée est volumineuse, le jury recommande aux participants utilisant C/C++ de soumettre avec le compilateur LINUX GNU C++ et de lire les données avec scanf.
Pendant ce tour, il est possible de soumettre des solutions en Java et en Python, ainsi que des solutions du problème interactif sous Ubuntu Linux.