/*

Car Parking (IOI 2000)
Copyright (C) 2000 Paolo Boldi and Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



Per capire come funziona questo programma, e` necessario prima leggere
la dispensa sulle permutazioni che trovate su http://ioi.dsi.unimi.it/.

Il programma calcola la permutazione necessaria a rimettere a posto le auto
tramite la qsort() (secondo gli organizzatori un algoritmo come il quicksort e`
troppo lento, e bisognerebbe ricorrere al distribution counting, ma in realta`
la chiamata di libreria e` cosi` ottimizzata da rientrare nei parametri; potete
comunque provare a implementare un distribution counting e vedere la
differenza). Poi emettiamo la permutazione sotto forma di cicli di lunghezza W
in maniera greedy (cioe` emettendo ogni volta quanto possibile). Dato che ogni
spezzamento richiede l'aggiunta di una lettera, otteniamo esattamente il
risultato richiesto.

Dato che e` impossibile stabilire a priori quanti blocchi verranno emessi in 
output, facciamo due passate. 

*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXN 20000	/* Massimo numero di automobili */
#define MAXM 50		/* Massimo numero di tipi */
#define MAXW 50		/* Massimo numero di parcheggiatori */

int N, M, W;
int perm[MAXN];		/* Vettore che rappresenta la permutazione da emettere */
int temp[MAXN];		/* Vettore temporaneo per la permutazione inversa */
char tipo[MAXN];		/* Tipo di ogni macchina */
int coppia[MAXW][2];	/* Per ogni lavoratore, la coppia da utilizzare */
char usato[MAXN];		/* Booleano che ricorda se un posto e` stato gia` sistemato */
FILE *F;


/* Funzione di confronto per qsort(). La risposta e` in base al tipo. */

int comp(const void *a, const void *b) {
	return tipo[*(int *)a] - tipo[*(int *)b];
}

int ultimavolta,	/* Se e` vero stiamo facendo la seconda passata per l'output */
	totale;			/* Numero di blocchi */


/* Questa funzione stampa le prime l coppie nella matrice coppia[][] se
   ultimavolta e` vero, altrimenti incrementa totale. */

void stampacoppie(int l) {
	int i;
	
	if (!ultimavolta) {
		++totale;
		return;
	}
	
	fprintf(F, "%d", l);
	for(i=0; i<l; i++) fprintf(F, " %d %d", coppia[i][0]+1, coppia[i][1]+1);
	fprintf(F, "\n");
}



int main(int argc, char *argv[]) {
	int i, t, l, 
		primo, 
		corr, 
		minnonusato;


	F = stdin;
	fscanf(F, "%d %d %d\n", &N, &M, &W);
	for(i=0; i<N; i++) {
		fscanf(F, "%d", &t);
		tipo[i] = t;
		temp[i] = i;
	}

	/* Qui costruiamo la permutazione da emettere ordinando prima in modo
		indiretto le macchine, e poi invertendo la permutazione. */

	qsort(temp, N, sizeof *temp, comp);
	for(i=0; i<N; i++) perm[temp[i]] = i;
	memcpy(temp, perm, sizeof *perm * N);

	F = stdout;

	/* L'output e` in due passate, una per calcolare il numero di blocchi
		e la seconda per effettuare l'output. */

	for(ultimavolta = 0; ultimavolta<2; ultimavolta++) {
		if (ultimavolta) {
			/* All'inizio della seconda passata resettiamo le variabili. */
			fprintf(F, "%d\n", totale);
			memcpy(perm, temp, sizeof *perm * N);
			memset(usato, 0, sizeof usato);
		}

		l = 0;
		primo = -1; /* Per spezzare un ciclo dobbiamo ricordarci dove cominciava. */
		minnonusato = 0; /* Indice della prima lettera non ancora sistemata. */

		for(;;) {
    
			if (primo == -1) {
				/* Non stiamo continuando un ciclo spezzato. Dobbiamo trovare il
					primo elemento non ancora utilizzato in un ciclo scandendo il
					vettore usato[] a partire da minnnonusato. Se arriviamo in fondo
					abbiamo finito. */

				while((usato[minnonusato] || perm[minnonusato] == minnonusato) && ++minnonusato < N);
				if (minnonusato == N) {
					if (l) stampacoppie(l);
					break;
				}
				corr = primo = minnonusato;
			}
			else {
				/* In questo caso stiamo cominciando un ciclo che e` il residuo
					di uno piu` lungo. Le prime due lettere sono quindi primo
					(l'inizio del ciclo precedente) e corr (la lettera che non
					abbiamo emesso nel ciclo precedente. */
      
				coppia[l][0] = primo;
				coppia[l][1] = corr;
				l++;
			}
      
			/* Ora scandiamo la permutazione, inseguendo il ciclo corrente,
				che parte dalla lettera corr. Accumuliamo dentro coppia[][] il
				risultato, fino a che il ciclo e` terminato oppure raggiungiamo
				la lunghezza massima W. Ogni volta che esaminiamo una lettera
				la marchiamo come utilizzata. */

			do {
				coppia[l][0] = corr;
				coppia[l][1] = l == W-1 ? primo : perm[corr];
	
				usato[corr] = 1;
				corr = perm[corr];
			} while(++l < W && primo != corr);
      
			/* Se abbiamo W coppie le stampiamo (nella prima passata
				stampacoppie() effettua solo il conteggio). */
      
			if (l == W) {
				stampacoppie(l);
				l = 0;
				perm[primo] = corr;
			}
	
			/* Il caso del ciclo di lunghezza 1--la macchina e` gia` a posto. */
      
			if (primo == corr) primo = -1;
      
		}
	}

	return 0;
}