Lo Chef e il grafo bipartito#11343
Lo Chef si è interessato allo studio dei grafi bipartiti. Oggi vuole costruire un grafo bipartito con vertici in ciascuna delle due parti e un numero totale di archi pari a . I vertici della parte sinistra sono numerati da a , i vertici della parte destra sono anch'essi numerati da a .
Lo Chef vuole inoltre che il grado di ogni vertice non sia minore di e non superiore a , cioè che per tutti i vertici valga:
Dati quattro interi n, m, d, D, dovete aiutare lo Chef a costruire un grafo bipartito che soddisfi le condizioni descritte. Se un tale grafo non esiste, stampate .
La prima riga contiene il numero di test . Ogni test è costituito da una singola riga contenente quattro interi: n~(1 \le n \le 100), m~(0 \le m \le n \cdot n), d, D~(1 \le d \le D \le n).
Per ogni test, stampate se non esiste un grafo bipartito che soddisfi le condizioni date. In caso contrario, stampate righe, ciascuna contenente due interi e , indicanti la presenza di un arco tra il vertice nella parte sinistra e il vertice nella parte destra.
Se esistono più soluzioni, stampatene una qualsiasi. Notate che il grafo non deve contenere archi multipli.
Esempio 1