eolymp
bolt
Try our new interface for solving problems
Məsələlər

Социология

Социология

Вася работает в НИИСПИ (Научно-Исследовательском Институте Социологических Передовых Испытаний). Он изучает взаимоотношения между разработчиками и архитекторами программного обеспечения. Вася рассматривает некоторое количество задач, поставленных перед программистами. Каждой задачей должен заниматься один разработчик и один архитектор. Вася называет подмножество архитекторов \textbf{A} избыточным, если подмножество разработчиков, имеющих общие задачи с хотя бы одним из архитекторов из \textbf{A}, меньшей мощности, чем \textbf{|A|}. Он выдвинул гипотезу о том, что система, в которой нет ни одного избыточного подмножества архитекторов, более стабильна и меньше давит на рабочую атмосферу. Ваша задача заключается в том, чтобы найти избыточное подмножество или сказать, что такового нет. \InputFile Входные данные состоят из не более, чем \textbf{10} тестовых блоков. Первая строка каждого тестового блока содержит два целых числа \textbf{N_e} и \textbf{N_m} - количество разработчиков и архитекторов соответственно (\textbf{1} ≤ \textbf{N_e}, \textbf{N_m} ≤ \textbf{10^4}). Следующая строка содержит единственное число \textbf{N_j} - количество задач (\textbf{1} ≤ \textbf{N_j} ≤ \textbf{10^5}). Затем следуют \textbf{N_j} строк, описывающих задачи. Каждая такая строка содержит два числа \textbf{e_i} и \textbf{m_i} - порядковые номера разработчика и архитектора, назначенных на выполнение задачи номер \textbf{i}. \OutputFile Для каждого тестового блока выведите избыточное подмножество архитекторов либо сообщение о том, что такового не существует. Придерживайтесь формата вывода, указанного в тестовом примере, как можно ближе.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3 3
6
1 2
1 3
2 3
2 1
3 1
3 2
2 3
2
1 3
2 2
1 3
3
1 1
1 2
1 3
Çıxış verilənləri #1
Case #1: There is no excessive subset of managers.
Case #2: Manager 1 forms an excessive subset.
Case #3: Managers 1 and 2 form an excessive subset.
Müəllif Vitaly Valtman, Yury Petrov