eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Торгівля

Торгівля

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

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

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

Вхідні дані

Перший рядок містить кількість сценаріїв T. Далі йде T рядків, кожен з яких містить три числа N, M, K (2N100, 0KMN·(N - 1)/2).

Кількість сценаріїв у одному вхідному файлі не перевищує 100.

Сума M по всім сценаріям у одному вхідному файлі не перевищує 50000.

Вихідні дані

Для кожного з T сценаріїв виведіть "NO SOLUTION" (без лапок), якщо відповідної торгівельної мережі не існує. У протилежному випадку виведіть "TRADE MARKET FOUND", а далі M рядків. Кожен з рядків повинен містити пару чисел, відокремлнеих пропуском — номери торгівців, які обмінюються товаром напряму.

Приклад

Вхідні дані #1
3
4 3 0
4 2 0
5 5 2
Вихідні дані #1
TRADE MARKET FOUND
1 2
2 3
3 1
NO SOLUTION
TRADE MARKET FOUND
1 2
2 3
3 1
1 4
1 5
Автор Ельдар Богданов
Джерело Зимова Школа, Харків 2011, День 7