Соціологія#5445

Соціологія

2 секунди

256 мегабайтів

Дуже складна

Вася працює в Науково-дослідному інституті соціологічних завдань (НДІСЗ). Він досліджує взаємовідносини між позаштатними розробниками програмного забезпечення та їхніми менеджерами. Вася розглядає декілька завдань, поставлених перед програмістами. Кожне завдання виконується одним інженером та управляється одним менеджером.

Вася називає підмножину $A$ менеджерів надлишковою, якщо потужність множини інженерів, які мають принаймні одну спільну задачу з менеджером із $A$ , менша за $∣ A ∣$ . Його гіпотеза полягає в тому, що система без надлишкових підмножин менеджерів є більш стабільною і створює менше тиску на працівників.

Ваше завдання — знайти надлишкову підмножину менеджерів або повідомити, що такої не існує.

Вхідні дані

Вхід складається не більше ніж із $10$ тестових випадків. Перший рядок кожного тесту містить два цілих числа $N_{e}$ N_e та $N_{m}$ N_m — кількість інженерів і менеджерів відповідно ( $1 \leq N_{e}, N_{m} \leq 1 0^{4}$ 1 \le N_e, N_m \le 10^4). Наступний рядок містить одне число $N_{j}$ N_j — кількість завдань ( $1 \leq N_{j} \leq 1 0^{5}$ 1 \le N_j \le 10^5). Далі слідують $N_{j}$ N_j рядків, кожен із яких містить два числа $e_{i}$ e_i та $m_{i}$ m_i — номери інженера та менеджера, призначених на виконання задачі номер $i$ .

Вихідні дані

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

Приклади

Приклад 1