Battista

Battista è un autista di automobili di lusso.
Il suo mestiere gli permette di conoscere le persone più famose di tutta Hollysteel.
Si sa, però, che i divi di Hollysteel sono molto stravaganti e ognuno di loro ha delle fissazioni che rendono la vita di Battista molto difficile.

L’ultima moda di Hollysteel è un incubo per Battista: le celebrità, infatti, entrano in un’automobile solo se questa è di colore uguale ad almeno uno dei capi di abbigliamento che indossano.

Battista, questa sera, dovrà accompagnare N celebrità attraverso Hollysteel, ognuna vestita secondo i propri gusti.

A complicare le cose c’è anche la deontologia professionale di Battista: egli infatti vuole accompagnare le celebrità in rigoroso ordine di prenotazione.

Per soddisfare tutti, Battista deve ovviamente riverniciare la macchina se questa non corrisponde al colore di almeno uno dei capi d’abbigliamento della prossima celebrità.
La verniciatura dell’automobile è un’operazione lenta e Battista non vuol fare attendere i propri clienti: ha intenzione, quindi, di verniciare l’automobile il minor numero di volte possibile.

Verniciare una macchina è un’operazione delicata: in pratica, è possibile passare da un colore a un altro solo se i due colori sono simili.
Sapendo che i colori a Hollysteel sono indicati da numeri naturali da 1 a C, è possibile passare dal colore x al colore y solo se x e ydifferiscono al più di 1 (per esempio, se l’automobile ha colore 2, può essere riverniciata solo col colore 3 o col colore 1, ma non col colore 4; un’automobile di colore 1, d’altro canto, può essere riverniciata solo col colore 2, e un’automobile col colore C può essere riverniciata solo col colore C-1).

Nota: Inizialmente l’automobile è stata carteggiata, ma non è verniciata, e quindi dovrà necessariamente essere verniciata (di un qualunque colore) prima di accompagnare la prima celebrità.

Dati in input

Il file input.txt contiene informazioni sulle celebrità che dovranno essere accompagnate questa sera da Battista e sul numero totale di colori in uso a Hollysteel.

• Sulla prima riga si troveranno due numeri interi separati da uno spazio: il primo è il numero N di celebrità, e il secondo è il numero C di colori.
• Su ciascuna delle N righe successive del file saranno presenti i colori degli abiti delle varie celebrità (la prima riga corrisponde alla celebrità numero 1 e così via).

I colori degli abiti di una celebrità sono espressi tramite una sequenza di interi K c1, c2, …, cK , dove K è il numero di diversi colori che indossa e c1, c2, …, cK i numeri associati a quei colori. Le celebrità sono elencate in ordine di prenotazione.

Dati in output

Se il problema ammette soluzione (cioè se esiste una sequenza di riverniciature che consente a Battista di accompagnare tutte le celebrità), il file output.txt dovrà contenere nella prima riga il numero M di riverniciature dell’automobile e in ciascuna delle successiveM righe una coppia di numeri naturali.
Ogni coppia indica una riverniciatura: il primo numero indica quando dovrà avvenire la riverniciatura (in particolare se una riverniciatura avviene appena prima di accompagnare la celebrità i il primo valore della coppia dovrà essere i); il secondo numero della coppia indicherà invece il nuovo colore dell’auto.
Le riverniciature dovranno essere elencate in ordine crescente rispetto al primo intero della coppia.

Importante!
Non è consentita la ripetizione di coppie che abbiano come primo elemento lo stesso numero naturale.
Detto altrimenti, è considerato un errore riverniciare più di una volta consecutiva la macchina: fra due riverniciature Battista deve sempre accompagnare almeno una celebrità.

Se il problema non ammette soluzione (cioè se non esiste una sequenza di riverniciature ammissibili), il file output.txt dovrà contenere una sola riga, contenente il singolo intero -1.

Assunzioni

• Il tempo limite di esecuzione è fissato in 0,1 secondi
• 1 <= C <= 200
• 1 <= N <= 1000
• Per ogni celebrità, il numero K di colori dei capi d’abbigliamento soddisfa 1 <= K <= C, e i K colori indicati sulla riga (c1, c2, …,cK) sono tutti distinti e compresi fra 1 e C.

Esempio