Chef and Bipartite Graph (Editorial)

Let us consider the conditions for the existence of a solution. Each part of the graph contains $n$ vertices. Since the degree of each vertex must be at least $d$ and at most $D$, the total number of edges $m$ must satisfy the following constraints:

If this condition is not satisfied, it is impossible to construct the required graph.

Now let us move on to constructing the graph. Let's use a constructive approach: we connect vertices from the left part to vertices from the right part using cyclic shifts.

1. Initialize the variable cur = 0.

2. For each i~(1 \le i \le n), add an edge between vertex $i$ in the left part and the vertex in the right part with index j = i + cur. If j > n, we instead take j = i + cur - n, i.e., we effectively use modulo $n$ indexing. After adding each edge, we increment the edge counter. As soon as the total number of added edges becomes equal to $m$, the algorithm terminates.

3. Increase cur = cur + 1 and repeat step $2$.

Thus, at each iteration we add a "shifted" set of edges, which guarantees a uniform distribution of vertex degrees. As a result, the degree of each vertex does not exceed $D$, and with a sufficient number of iterations, it reaches at least $d$.

Example

The graph shown in the example has the following form:

Algorithm implementation

Read the number of test cases $tests$.

scanf("%d", &tests);
while (tests--)
{

Read the input data for the current test case.

  scanf("%d %d %d %d", &n, &m, &d, &D);

If it is impossible to construct the graph due to violation of the required inequalities, print $-1$.

  if (n * d > m || n * D < m)
  {
    printf("-1\n");
    continue;
  }

Set cur = 0.

  cur = 0;
  while (m > 0)
  {

Until exactly $m$ edges are constructed, build them according to the described algorithm.

    for (i = 1; i <= n; i++)
    {
      j = (i + cur) % n;
      if (j == 0) j = n;

Print the edge $(i,j)$.

      printf("%d %d\n", i, j);
      m--;

As soon as all $m$ edges are constructed, terminate the program.

      if (m == 0) break;
    }

Increment the variable $cur$ by $1$.

    cur++;
  }
}