Il torneo amatoriale di Rocca Caprina per N giocatori prevede lo scontro diretto di ogni partecipante con tutti gli altri, ossia Nx(N-1)/2partite.
Poiché l’intero torneo dura una settimana, le partite vengono interrotte allo scadere della settimana.
Per l’assegnazione del montepremi (orecchiette, cavatelli, intorchiate, taralli, diavulaccé, taràtufulu e scagliozzi), sono considerate valide soltanto le M partite in cui è stata assegnata una vittoria, dove M ≤ Nx(N-1)/2.
Non potendo sempre stabilire un singolo vincitore del torneo, tale montepremi viene assegnato a una coalizione di dominatori, che esiste sempre ed è definita come segue.
Una coalizione è un gruppo di giocatori tali che nessun giocatore del gruppo ha mai vinto contro un altro giocatore dello stesso gruppo.
Numerati in modo univoco i giocatori da 1 fino a N, i giocatori dominati da una coalizione G sono tutti quei giocatori C per i quali almeno una delle seguenti condizioni è soddisfatta (dove 1 ≤ A, B, C ≤ N sono tre numeri distinti che individuano altrettanti giocatori):
- C appartiene alla coalizione G oppure
- esiste un giocatore A in G che ha vinto la partita contro C oppure
- esiste un giocatore A in G che ha vinto la partita contro un qualche giocatore B e, a sua volta, B ha vinto la partita contro C.
Lo scoperto di una coalizione è il numero di giocatori non dominati da essa.
Una coalizione di dominatori è quindi una coalizione con scoperto pari a 0.
Scrivete un programma che aiuti a individuare una coalizione.
Dati in Input
Il file input.txt è composto da M+1 righe, dove M è un intero positivo.
- La prima riga contiene due interi positivi N e M che rappresentano rispettivamente il numero N di giocatori e il numero M di partite in cui è stata assegnata una vittoria.
- Le successive M righe contengono i risultati delle partite in cui è stata assegnata una vittoria. Ciascuna di tali righe è composta da due interi distinti I e J separati da uno spazio per indicare che I ha vinto nella partita contro J, dove 1 ≤ I, J ≤ N (quindi il primo intero è il vincitore mentre il secondo intero è il perdente).
Dati in Output
Il file output.txt è composto da una sola riga contenente i numeri, separati da uno spazio, che identificano i giocatori di una coalizione.
Assunzioni
- 2 ≤ N ≤ 1000
- 1 ≤ M ≤ Nx(N-1)/2
Valutazione delle soluzioni
Il punteggio è pari a 0 nel caso in cui l’output non rappresenti una coalizione.
Altrimenti, sia Z lo scoperto della coalizione restituita.
Il punteggio viene assegnato secondo la seguente regola:
- punteggio pieno pari a D=3 se Z=0 (coalizione di dominatori);
- punteggio pari a 1 se 0 < Z ≤ N/2;
- punteggio pari a 0 altrimenti.
Esempi
| input.txt | output.txt | |
|---|---|---|
| 1 | 4 4 1 2 4 2 3 4 3 2 |
1 3 |
| 2 | 7 8 1 5 6 1 6 2 4 2 4 1 2 3 3 6 3 4 |
6 4 7 |
| 3 | 7 8 1 5 6 1 6 2 4 2 4 1 2 3 3 6 3 4 |
1 3 7 |
Note
- Poiché una coalizione di dominatori esiste sempre, per gli esempi forniti è stato reputato utile elencare una delle coalizioni di dominatori, ma ovviamente una soluzione parziale è ammessa come risposta e soggetta alla valutazione di cui sopra.