Торгівля

Торгівля — це тонка справа. Успішний торговець повинен не лише вміти своєчасно продавати потрібні товари та приваблювати покупців, а й добре розуміти ситуацію на ринку. Серед іншого, важливо знати, які торговці торгують один з одним, а які — ні. Іноді торговці не торгують напряму, але їхні товари все одно можуть дістатися один до одного через інших торговців. Наприклад, якщо торговці A та B торгують безпосередньо, а торговці B та C також торгують безпосередньо, то товари A і C можуть потрапити один до одного через торговця B. Інше важливе поняття — це неподільні пари: це такі пари торговців, які торгують напряму, і для яких не існує жодної послідовності проміжних торговців, через яких вони могли б торгувати опосередковано.

Мано хоче стати успішним торговцем. Ми не знаємо, якими необхідними якостями він володіє, але йому явно бракує знань про стан ринку. Все, що він знає — на ринку є $N$ торговців, $M$ пар, які торгують безпосередньо, і серед них $K$ неподільних пар. Йому якраз і потрібна конкретніша інформація, наприклад, "A торгує з B, C торгує з D, X торгує з A". Звісно, цей опис не завжди єдиний, але будь-який, що задовольняє ці вимоги, йому підійде.

Вам задано $T$ сценаріїв, кожен зі своїми значеннями $N$, $M$ і $K$. Для кожного з них визначте, чи існує така торгова мережа, і якщо так, представте її опис. Торговці нумеруються від $1$ до $N$ у довільному порядку, а опис торгової мережі — це множина всіх різних пар торговців, які торгують безпосередньо.