Nella società lavorano $n$ dipendenti, uno dei quali è il direttore. Ogni dipendente, tranne il direttore, ha esattamente un superiore diretto.
Ogni dipendente svolge un lavoro ben preciso. Se il dipendente $a$ deve far eseguire un lavoro di cui si occupa il dipendente $b$, deve inviare una richiesta a $b$. Secondo la politica aziendale, le richieste possono essere trasmesse direttamente soltanto da un dipendente al suo superiore diretto oppure, viceversa, da un superiore a un suo subordinato diretto. La richiesta viene passata da un dipendente all'altro finché non raggiunge $b$.
Per alleggerire il lavoro dei dipendenti, la società ha assunto $k$ corrieri. Il corriere numero $i$ è assegnato alla coppia di dipendenti $a_i$ e $b_i$ e consegna le richieste tra loro. Quando uno dei due deve inviare una richiesta all'altro, la affida al corriere, che la trasmette in successione tra i dipendenti secondo la politica aziendale, finché non passa attraverso tutti i dipendenti intermedi necessari e raggiunge il destinatario. Durante la consegna di una singola richiesta, il corriere non visita uno stesso dipendente più di una volta.
Per ottimizzare i costi, si è deciso di trovare una coppia di corrieri i cui percorsi si sovrappongano il più possibile e rinunciare ai servizi di uno, affidandone il lavoro all'altro. Definiamo il grado di duplicazione di una coppia di corrieri come il numero di passaggi tra un dipendente e il suo superiore diretto, in qualsiasi direzione, che appartengono sia al percorso del primo corriere sia a quello del secondo.
Scrivete un programma che determini due corrieri con il massimo grado di duplicazione.
Input
La prima riga contiene due interi: $n$, il numero di dipendenti, e $k$, il numero di corrieri, con $2\le n,k\le2\cdot10^5$. I dipendenti sono numerati da $1$ a $n$; il direttore ha il numero $1$.
La seconda riga contiene $n-1$ interi $p_2,p_3,\ldots,p_n$: i numeri dei superiori diretti di ciascun dipendente, escluso il direttore, con $1\le p_i<i$.
Le successive $k$ righe contengono ciascuna due interi $a_i,b_i$: i numeri dei dipendenti della coppia assegnata al corriere numero $i$, con $1\le a_i,b_i\le n$ e $a_i\ne b_i$. Alla stessa coppia di dipendenti possono essere assegnati più corrieri.
Output
La prima riga deve contenere un solo intero: il massimo grado di duplicazione tra due corrieri.
La seconda riga deve contenere due interi distinti da $1$ a $k$: i numeri dei corrieri di una coppia con il massimo grado di duplicazione. Se esistono più coppie di questo tipo, potete stamparne una qualsiasi.
Nota
Diremo che il dipendente $a$ obbedisce agli ordini del dipendente $b$ se $b$ è il superiore diretto di $a$, oppure se il superiore diretto di $a$ obbedisce agli ordini di $b$. È naturale chiamare importante un corriere che trasmette richieste da un dipendente a qualcuno che obbedisce ai suoi ordini, o nella direzione opposta.
Sottoproblemi
| Sottoproblema | Punti | Vincoli su $n$ | Vincoli su $k$ | Vincoli aggiuntivi | Sottoproblemi necessari |
|---|---|---|---|---|---|
| $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$ | Il numero di passaggi tra qualsiasi dipendente e il direttore non supera $20$ | |
| $6$ | $12$ | $2\le n\le10^5$ | $2\le k\le50\,000$ | Ogni corriere è importante | |
| $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$ |
Esempi
Input 1
4 2 1 2 2 1 3 1 4
Output 1
1 2 1
Input 2
4 2 1 2 3 1 2 3 4
Output 2
0 1 2
Input 3
7 3 1 2 2 4 5 5 1 3 3 7 6 1
Output 3
2 2 3
Input 4
4 3 1 2 3 1 4 4 1 1 4
Output 4
3 2 1
Nota
Nel primo esempio ci sono due corrieri. Il primo consegna richieste dal dipendente $1$ al dipendente $3$ o viceversa. Per esempio, consegnando una richiesta da $1$ a $3$, la trasmette prima da $1$ a $2$, poi da $2$ a $3$. Il secondo corriere consegna richieste da $1$ a $4$ o viceversa. Per esempio, consegnando una richiesta da $4$ a $1$, la trasmette prima da $4$ a $2$, poi da $2$ a $1$. Il grado di duplicazione di questa coppia è $1$, perché condividono il passaggio tra il dipendente $1$, il direttore, e il dipendente $2$.
Anche nel secondo esempio ci sono due corrieri, ma i loro percorsi non si intersecano.
Il terzo esempio è rappresentato nella figura sopra. Le linee spesse indicano i passaggi tra dipendenti. Le linee sottili indicano il percorso del primo corriere tra i dipendenti $1$ e $3$. Le linee a tratteggio lungo indicano il percorso del secondo corriere tra i dipendenti $3$ e $7$. Le linee a tratteggio corto indicano il percorso del terzo corriere tra i dipendenti $1$ e $6$.
Ai percorsi del primo e del secondo corriere appartiene in comune soltanto il passaggio tra i dipendenti $2$ e $3$. Ai percorsi del primo e del terzo corriere appartiene in comune soltanto il passaggio tra i dipendenti $1$ e $2$. I percorsi del secondo e del terzo corriere condividono due passaggi: tra i dipendenti $2$ e $4$, e tra i dipendenti $4$ e $5$. Quindi la coppia di corrieri numero $2$ e $3$ ha il massimo grado di duplicazione, pari a $2$.
Nel quarto esempio tutti i corrieri trasportano richieste tra il direttore e il dipendente numero $4$. Pertanto tutte le coppie hanno grado di duplicazione $3$. È consentito stampare una coppia qualsiasi.
Informazioni generali sulle prove della seconda giornata
Accesso ai risultati della valutazione durante la gara
In tutte le prove potete richiedere un numero illimitato di volte il risultato della valutazione definitiva. Per ciascun sottoproblema vengono comunicati i punti e il risultato del programma su ciascun test.
Limite alla dimensione del codice sorgente
In tutte le prove la dimensione del file contenente il codice sorgente della soluzione non deve superare 256 KB.
Procedura di valutazione
In tutte le prove i punti di un sottoproblema vengono assegnati soltanto se tutti i suoi test sono superati. La tabella di valutazione indica, per ciascun sottoproblema, i numeri dei sottoproblemi necessari. I test di un sottoproblema vengono eseguiti soltanto se tutti i sottoproblemi necessari sono stati superati.
Nota
Per le prove con grandi quantità di dati in ingresso, la giuria consiglia ai partecipanti che usano linguaggi del gruppo C/C++ di inviare soluzioni con il compilatore LINUX GNU C++ e di leggere i dati con scanf.
Notate che in questa giornata è possibile inviare soluzioni in Java e Python, e anche soluzioni della prova interattiva sotto il sistema operativo Ubuntu Linux.
Informazioni generali sulle prove della seconda giornata
Accesso ai risultati della valutazione durante la gara
In tutte le prove potete richiedere un numero illimitato di volte il risultato della valutazione definitiva. Per ciascun sottoproblema vengono comunicati i punti e il risultato del programma su ciascun test.
Limite alla dimensione del codice sorgente
In tutte le prove la dimensione del file contenente il codice sorgente della soluzione non deve superare 256 KB.
Procedura di valutazione
In tutte le prove i punti di un sottoproblema vengono assegnati soltanto se tutti i suoi test sono superati. La tabella di valutazione indica, per ciascun sottoproblema, i numeri dei sottoproblemi necessari. I test di un sottoproblema vengono eseguiti soltanto se tutti i sottoproblemi necessari sono stati superati.
Nota
Per le prove con grandi quantità di dati in ingresso, la giuria consiglia ai partecipanti che usano linguaggi del gruppo C/C++ di inviare soluzioni con il compilatore LINUX GNU C++ e di leggere i dati con scanf.
Notate che in questa giornata è possibile inviare soluzioni in Java e Python, e anche soluzioni della prova interattiva sotto il sistema operativo Ubuntu Linux.
Informazioni generali sulle prove della seconda giornata
Accesso ai risultati della valutazione durante la gara
In tutte le prove potete richiedere un numero illimitato di volte il risultato della valutazione definitiva. Per ciascun sottoproblema vengono comunicati i punti e il risultato del programma su ciascun test.
Limite alla dimensione del codice sorgente
In tutte le prove la dimensione del file contenente il codice sorgente della soluzione non deve superare 256 KB.
Procedura di valutazione
In tutte le prove i punti di un sottoproblema vengono assegnati soltanto se tutti i suoi test sono superati. La tabella di valutazione indica, per ciascun sottoproblema, i numeri dei sottoproblemi necessari. I test di un sottoproblema vengono eseguiti soltanto se tutti i sottoproblemi necessari sono stati superati.
Nota
Per le prove con grandi quantità di dati in ingresso, la giuria consiglia ai partecipanti che usano linguaggi del gruppo C/C++ di inviare soluzioni con il compilatore LINUX GNU C++ e di leggere i dati con scanf.
Notate che in questa giornata è possibile inviare soluzioni in Java e Python, e anche soluzioni della prova interattiva sotto il sistema operativo Ubuntu Linux.