OII 2006

[Mesh89]

Questo è un problema assegnato alle scorse Olimpiadi Italiane di Informatica

Siccome è venuto un po' incasinato, ecco la pagina
http://143.225.229.60/oii/vecchie_ed...li/curling.htm

Voi cm lo risolvereste? Che strutture dati usereste? Non voglio l'algoritmo, ma solo la logica...


Partite di curling (curling)
Difficoltà D = 2 (tempo limite 3 secondi).
Descrizione del problema

Giorgino è un appassionato di sport e ha scoperto il gioco del curling durante le recenti Olimpiadi invernali. Ciascuna partita di curling è giocata da due squadre e le regole olimpiche, in caso di pareggio, prevedono precise modalità per designare la squadra vincitrice: in altre parole, ogni partita ha sempre un vincitore.

Giorgino ha registrato tutte le partite olimpiche che si sono svolte tra le N squadre nazionali e, quindi, può vedere la partita tra una qualunque coppia di squadre (a tal fine, ha enumerato le squadre da 1 a N). Per apprendere meglio le strategie di gioco, decide di organizzare un fine settimana con gli amici per vedere una sequenza di partite tra quelle disputate alle Olimpiadi, selezionandole con le seguenti regole:

1. la sequenza deve contenere il massimo numero di partite con il vincolo che tutte le squadre debbano essere coinvolte e che nessuna squadra vinca o perda più di una volta nelle partite selezionate;
2. se in una partita (diversa dall'ultima) della sequenza la squadra i risulta vincitrice con la squadra j, allora j deve risultare vincitrice nella partita immediatamente successiva (della sequenza);
3. la squadra che risulta vincitrice nella prima partita della sequenza non disputa ulteriori partite tra quelle selezionate nella sequenza.



Aiutate Giorgino a decidere quali partite selezionare per la sequenza, sapendo che ciascuna coppia di squadre ha disputato esattamente una partita (da cui è risultato un vincitore) durante le Olimpiadi invernali.
Dati di input

Il file input.txt è composto da 1 + Nx(N-1)/2 righe.

La prima riga contiene un intero positivo che rappresenta il numero N di squadre olimpiche.

Le successive Nx(N-1)/2 righe contengono coppie di interi positivi che rappresentano tutte le partite di curling tra le squadre. Ogni riga è composta da due interi distinti i e j separati da uno spazio, a rappresentare che la squadra i ha vinto la partita disputata con la squadra j (dove 1 ≤ i,j ≤ N). Da notare che la stessa partita non può apparire in più di una riga e l'ordine dei due interi in ciascuna riga è significativo in quanto il primo intero indica la squadra vincitrice (se in una riga appare la coppia i e j, in nessun'altra riga può apparire la coppia j e i ).
Dati di output

Il file output.txt è composto da 1 + M righe.

La prima riga contiene un intero positivo che rappresenta il numero M di partite selezionate con le regole indicate sopra.

Le successive M righe contengono coppie di interi positivi che rappresentano la sequenza delle partite selezionate. Analogamente a quanto descritto per il file input.txt, ogni riga è composta da due interi distinti i e j separati da uno spazio, a rappresentare che la squadra i ha vinto la partita disputata con la squadra j (dove 1 ≤ i,j ≤ N). Inoltre, se tale riga non è l'ultima, allora la riga successiva deve contenere la coppia di interi j e k, in cui la squadra k non appare nelle righe precedenti. L'ordine delle partite selezionate nella sequenza è quindi importante; inoltre, ci possono essere più sequenze di partite che soddisfano le regole di selezione e, in tal caso, una qualunque di tali sequenze fornisce la risposta corretta (come mostrato negli esempi).
Assunzioni

* 3 ≤ N ≤ 2000
* I dati in input.txt garantiscono sempre che esiste una sequenza di partite che soddisfa le regole di selezione.

Esempi di input/output


File input.txt File output.txt

3
1 2
2 3
1 3



2
1 2
2 3




File input.txt File output.txt

4
1 2
2 4
4 3
3 2
4 1
3 1



3
3 2
2 4
4 1




File input.txt File output.txt

4
1 2
2 4
4 3
3 2
4 1
3 1



3
4 3
3 1
1 2