Шеф і двочастковий граф#11343
Шеф зацікавився вивченням двочасткових графів. Сьогодні він хоче побудувати двочастковий граф з вершинами в кожній з двох частин та загальною кількістю ребер, що дорівнює . Вершини лівої частини пронумеровані від до , вершини правої частини також пронумеровані від до .
Шеф також хоче, щоб степінь кожної вершини був не меншим за і не більшим за , тобто для всіх вершин виконувалося:
За заданими чотирма цілими числами n, m, d, D Вам необхідно допомогти Шефу побудувати деякий двочастковий граф, що задовольняє описаним умовам. Якщо такого графа не існує, виведіть .
Перший рядок містить кількість тестів . Кожен тест складається з одного рядка, що містить чотири цілих числа: n~(1 \le n \le 100), m~(0 \le m \le n \cdot n), d, D~(1 \le d \le D \le n).
Для кожного тесту виведіть , якщо не існує двочасткового графа, що задовольняє заданим умовам. Інакше виведіть рядків, кожен з яких містить два цілих числа та , що позначають наявність ребра між вершиною у лівій частині та вершиною у правій частині.
Якщо існує кілька розв'язків, виведіть будь-який з них. Зверніть увагу, що граф не повинен містити кратних ребер.
Приклад 1