L’incredibile Hulk sta fuggendo dai suoi inseguitori che vogliono catturarlo per studiare la mutazione genetica che l’ha reso così forte, veloce e verde.
Possiede una mappa con le vie di fuga, dove gli snodi (cioè i punti da cui si dipartono zero o più strade) sono numerati da 1 a N e il tratto di strada che collega direttamente gli snodi I e J è indicato con (I,J) e può essere percorso in entrambe le direzioni.
Inoltre, non esistono due o più tratti di strada che colleghino direttamente la stessa coppia di snodi.
I tratti occupati dagli inseguitori sono indicati in rosso e quelli liberi in verde.
Hulk vuole trovare un percorso circolare libero per la sua fuga: in altre parole, vuole essere sicuro di poter girare circolarmente, e a velocità spedita, attraverso gli snodi (non necessariamente tutti).
In particolare, ha bisogno di individuare gli snodi I1, I2, I3, …, IK (dove K ≥ 3), distinti tra loro, che sono collegati da un cammino, ossia da una sequenza di tratti tutti in verde (I1,I2), (I2,I3), …, (IK-1,IK), (IK,I1) (notare la circolarità).
Il tuo compito è di aiutare Hulk a individuare un insieme di snodi che dia luogo a circolarità secondo quanto definito sopra.
Dati in Input
Il file input.txt è composto da M+1 righe.
- Sulla prima riga si trovano gli interi N e M separati da uno spazio, dove N è il numero di snodi e M è il numero di tratti che collegano gli snodi.
- Ciascuna delle successive M righe contiene tre interi I, J e C separati da uno spazio, dove 1 ≤ I, J ≤ N e 0 ≤ C ≤ 1, per indicare che gli snodi I e J sono collegati dal tratto (I,J) di colore rosso (C=0) o verde (C=1).
Dati in Output
Il file output.txt è composto da due righe.
- La prima riga contiene un intero K che indica quanti snodi sono coinvolti nella circolarità individuata.
- La seconda riga contiene K interi distinti I1, I2, I3, …, IK separati da uno spazio, ossia quali sono gli snodi coinvolti: essi risultano collegati da tratti in verde (I1,I2), (I2,I3), …, (IK-1,IK), (IK,I1).
Assunzioni
- 3 <= N <= 100000
- N < M <= 200000
- 3 <= K <= N
- Viene garantito che esiste sempre almeno una circolarità.
Esempi
| input.txt | output.txt |
|---|---|
| 5 8 5 4 1 1 2 1 1 3 1 3 2 1 1 5 0 1 4 1 3 4 0 2 5 1 |
3 2 3 1 |
Note
- Non tutti gli snodi hanno necessariamente una o più strade che si dipartono da loro (potrebbero esserci snodi completamente isolati).
- Non tutte le coppie di snodi sono necessariamente collegate tra di loro mediante un tratto o una sequenza di tratti.
- Per un dato input.txt ci possono essere più risposte corrette e sono tutte valide ai fini della gara: è necessario specificarne una (e una sola) in output.txt.