A Nanilanda l’orgoglio di ogni cittadino è il giardino, che è formato da una serie di vialetti ai cui incroci viene posto un nano da giardino.
I giardini di Nanilandia sono molto particolari: non è possibile partire da un nano e tornare allo stesso nano senza ripassare per un vialetto già percorso.
D’altra parte, è sempre possibile raggiungere tutti i nani a partire da qualunque nano.
Non soprendentemente, la struttura di un giardino è unica e irripetibile.
Ogni abitante si fregia, in effetti, della struttura originale del proprio.
Il Comitato per la Protezione dei Giardini di Nani ha però scoperto una truffa ignobile: alcuni abitanti copiano la struttura del giardino di altri, cambiando semplicemente il posto dei nani.
È infatti consentito avere lo stesso insieme di nani, purché la struttura (cioè la forma) del giardino sia diversa.
Dovete aiutare il Comitato a riconoscere giardini che differiscono solo per la posizione dei nani.
Per esempio, nell’esempio mostrato in figura i due gardini potrebbero apparire diversi a un osservatore disattento: ciononostante, spostando i nani del primo è possibile ottenere il secondo.
Dati in input
Il file di input, di nome input.txt, contiene sulla prima riga un intero, il numero N di nani del primo giardino.
I nani sono numerati da 1 a N.
Seguono, sulle seguenti N-1 righe, coppie di interi separate da uno spazio, che rappresentano un viottolo tra due nani nel primo giardino.
Infine, seguono N-1 righe che rappresentano un viottolo tra due nani nel secondo giardino.
Dati in output
Se i due giardini descritti hanno la stessa struttura, il file di output, di nome output.txt, deve contenere una lista di N interi separati da spazi.
Il primo intero deve essere il numero del nano che sta, nel secondo giardino, al posto del primo nano nel primo giardino.
Il secondo intero deve essere il numero del nano che sta, nel secondo giardino, al posto del secondo nano nel primo giardino, e così via.
In pratica, mettendo il nano i del primo giardino al posto del nano definito dall’i-esimo indice della lista nel secondo giardino, si trasforma il secondo giardino nel primo.
Se invece i due giardini sono proprio diversi, il vostro programma deve solo stampare -1 su una riga.
Se ci sono più modi di cambiare di posto i nani in modo da rendere i due giardini identici, il vostro programma ne deve emettere uno qualunque.
Assunzioni
- 1 ≤ N ≤ 300
- Il tempo limite di esecuzione è fissato in 2 secondi.
Esempio
| input.txt | output.txt |
|---|---|
| 6 1 4 4 3 4 2 4 6 6 5 6 1 1 5 5 2 5 4 5 3 |
4 2 3 5 6 1 |
L’esempio corrisponde ai giardini mostrati in figura
