Шеф і двочастковий граф (Розбір)

Розглянемо умови існування розв'язку. У кожній частці графа міститься по $n$ вершин. Оскільки степінь кожної вершини має бути не менше $d$ і не більше $D$, загальна кількість ребер $m$ повинна задовольняти наступним обмеженням:

Якщо ця умова не виконується, побудувати необхідний граф неможливо.

Перейдемо до побудови графа. Використаємо конструктивний підхід. Будемо з'єднувати вершини лівої частки з вершинами правої частки циклічними зсувами.

1. Ініціалізуємо змінну cur = 0.

2. Для кожного i~(1 \le i \le n) додаємо ребро між вершиною $i$ лівої частки та вершиною правої частки з номером j = i + cur. Якщо j \gt n, то замість цього беремо j = i + cur - n, тобто фактично використовуємо індексацію за модулем $n$. Після додавання кожного ребра збільшуємо лічильник ребер. Як тільки загальна кількість доданих ребер стане рівною $m$, алгоритм завершується.

3. Збільшуємо cur = cur + 1 і повторюємо крок $2$.

Таким чином, на кожній ітерації ми додаємо "зсунутий" набір ребер, що гарантує рівномірний розподіл степенів вершин. У результаті степінь кожної вершини не перевищує $D$, а за достатньої кількості ітерацій досягає щонайменше $d$.

Приклад

Граф, наведений у прикладі, має наступний вигляд:

Реалізація алгоритму

Читаємо кількість тестів $tests$.

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

Читаємо вхідні дані чергового тесту.

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

Якщо граф неможливо побудувати через невиконання необхідних нерівностей, виводимо $-1$.

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

Встановлюємо cur = 0.

  cur = 0;
  while (m > 0)
  {

Поки не буде побудовано рівно $m$ ребер, будуємо їх за вказаним алгоритмом.

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

Виводимо ребро $(i,j)$.

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

Як тільки всі $m$ ребер будуть побудовані, завершуємо програму.

      if (m == 0) break;
    }

Збільшуємо значення змінної $cur$ на $1$.

    cur++;
  }
}