Şef və ikitərəfli qraf#11343
Şef ikitərəfli (bipartit) qrafları öyrənməklə maraqlanmağa başladı. Bu gün o, hər iki hissəsində təpə olan və rəbələrin ümumi sayı -ə bərabər olan ikitərəfli qraf qurmaq istəyir. Sol hissənin təpələri -dən -ə qədər nömrələnib, sağ hissənin təpələri də -dən -ə qədər nömrələnib.
Şef həmçinin istəyir ki, hər bir təpənin dərəcəsi -dən az olmasın və -dən çox olmasın, yəni bütün təpələri üçün aşağıdakı şərt ödənilsin:
Verilmiş dörd tam ədəd n, m, d, D üçün siz Şefə təsvir olunan şərtləri ödəyən müəyyən bir ikitərəfli qraf qurmaqda kömək etməlisiniz. Əgər belə qraf mövcud deyilsə, çap edin.
Birinci sətirdə testlərin sayı verilir. Hər test dörd tam ədədi ehtiva edən bir sətirdən ibarətdir: n~(1 \le n \le 100), m~(0 \le m \le n \cdot n), d, D~(1 \le d \le D \le n).
Hər test üçün, verilmiş şərtləri ödəyən ikitərəfli qraf mövcud deyilsə, çap edin. Əks halda, hər biri və adlı iki tam ədəd ehtiva edən sətir çap edin, bu ədədlər sol hissədəki təpəsi ilə sağ hissədəki təpəsi arasında rəbə olduğunu bildirir.
Əgər bir neçə həll mövcuddursa, onlardan istənilən birini çap edin. Diqqət yetirin ki, qraf təkrarlanan rəbələr ehtiva etməməlidir.
Nümunə 1