Problems
Chef and Bipartite Graph
Chef and Bipartite Graph
Chef is very interested in studying biparite graphs. Today he wants to construct a bipartite graph with $n$ vertices each, on the two parts, and with total number of edges equal to $m$. The vertices on the left are numbered from $1$ to $n$. And the vertices on the right are also numbered from $1$ to $n$. He also wants the degree of every vertex to be greater than or equal to $d$, and to be lesser than or equal to $D$. ie. for all $v: d \le deg(v) \le D$.
Given four integers $n, m, d, D$ you have to help Chef in constructing some bipartite graph satisfying this property. If there does not exist any such graph, output $-1$.
\InputFile
First line contains the number of test cases $t$.
The only line of each test case contains four integers $n~(1 \le n \le 100)$, $m~(0 \le m \le n \cdot n)$, $d, D~(1 \le d \le D \le n)$.
\OutputFile
For each test case, output $-1$ if there is no bipartite graph satisfying this property. Otherwise output $m$ lines, each of the lines should contain two integers $u, v$ denoting that there is an edge between vertex $u$ on the left part and vertex $v$ on the right part. If there can be multiple possible answers, you can print any. Note that the bipartite graph should not have multi-edges.
Input example #1
2 2 3 1 2 2 3 1 1
Output example #1
1 1 2 2 1 2 -1