Scuola di supereroi

Hulk vuole organizzare una scuola per supereroi.
A tal fine, vuole invitare N supereroi che verranno numerati da 1 a N e dovranno superare due prove P.

La prima prova (P=1) prevede che i supereroi vengano messi di fronte a N cattivi, anch’essi numerati da 1 a N.
La prova è suddivisa in N round.
In ciascun round, ogni supereroe deve affrontare uno dei cattivi.
In uno stesso round, non ci possono essere due o più supereroi che affrontano lo stesso cattivo oppure due o più cattivi che si oppongono allo stesso supereroe.
Inoltre, ogni supereroe deve affrontare tutti gli N cattivi negli N round previsti per la prova.

Per esempio, per N=3, una soluzione è data dai tre round [(1,1), (2,2), (3,3)], [(1,3), (2,1), (3,2)] e [(1,2), (2,3), (3,1)], dove la coppia (I,J) indica che il supereroe numero I affronta il cattivo numero J.
In generale altre soluzioni sono possibili, mentre alcune configurazioni non sono risposte valide, come per esempio
organizzare i seguenti tre round [(1,1), (2,2), (3,3)], [(1,3), (2,1), (3,2)] e [(1,3), (2,2), (3,1)], i quali violano le regole suddette.

La seconda prova (P=2) prevede che i supereroi debbano quindi affrontarsi tra di loro.
La prova consiste in N-1 round. In ciascun round, i supereroi si affrontano a due a due.
Ogni supereroe deve affrontare tutti gli altri N-1 supereroi negli N-1 round previsti per la prova.

Per esempio, per N=4, una soluzione è data dai tre round [(1,2), (3,4)], [(1,3), (2,4)] e [(1,4), (2,3)], dove la coppia (I,J) indica che i due supereroei numero I e J si affrontano.

Aiuta Hulk a organizzare le due prove specificando le coppie che devono affrontarsi in ciascuno dei round.
Il tuo obiettivo è di organizzare N round nella prima prova e N-1 round nella seconda prova, permettendo a tutti di affrontarsi secondo le regole riportate sopra.
Per facilitarti il compito, nella seconda prova il valore di N è una potenza di 2 (N = 2, 4, 8, 16, 32, 64, …).

Dati in Input

Il file input.txt è composto da una riga contenente due interi N e P separati da uno spazio, dove N è il
numero di supereroi (e di cattivi) e P è il numero della prova da organizzare in round (ossia vale P=1 oppure P=2).

Dati in Output

Il formato del file output.txt dipende dal valore P specificato nel file input.txt.

• Se P=1, il file output.txt è composto da N righe. Ciascuna riga individua un round e contiene 2N interi separati da uno spazio che, quando vengono presi a due a due, rappresentano le N coppie che si affrontano nel round.
• Se P=2, il file output.txt è composto da N-1 righe. Ciascuna riga individua un round e contiene N interi separati da uno spazio che, quando vengono presi a due a due, rappresentano le N/2 coppie che si affrontano nel round.

 

Assunzioni

• 2 <= N <= 2100

 

Esempi

Note

• Nella prima prova, le coppie (I,J) e (J,I) rappresentano due situazioni diverse, in quanto la prima componente della coppia indica il supereroe e la seconda indica il cattivo.
• Nella seconda prova, le coppie (I,J) e (J,I) hanno medesimo significato: i supereroi I e J si affrontano.