18104번 - Составление задач 스페셜 저지다국어

Для составления задач на очередное соревнование организаторы пригласили $P$ опытных участников этих же соревнований. Каждый из них знает некоторый набор задач. Участники любят делиться идеями задач, поэтому каждая задача может быть известна нескольким участникам. К сожалению, если участник знает хотя бы одну задачу из выбранного на соревнование комплекта, то он не может принять в нём участие.

Организаторы заинтересованы в массовости соревнования, поэтому они хотят выбрать задачи так, чтобы как можно больше участников могли принять в нём участие. При этом набор задач должен быть не пуст, и, по возможности, как можно больше.

Организаторы не являются программистами, поэтому испытывают проблемы с тем, чтобы набрать задачи требуемым образом, поэтому просят вас помочь им.

В первой строке входных данных записаны три целых числа $P$, $T$ и $M$ ($1 \leq P$, $T \leq 10^5$; $0 \leq M \leq \min(10^6, P \cdot T)$) --- количество участников, задач и пар участник-задача, которую он знает, соответственно.

В следующих $M$ строках описаны задачи, которые известны участникам. В каждой строке записаны два целых числа $u$ и $v$ ($1 \leq u \leq P; 1 \leq v \leq T$) --- номер участника и номер одной из известных ему задач. Гарантируется, что для каждого участника каждая известная ему задача описана ровно один раз.

В первой строке выведите два числа $P_0$ и $T_0$ --- искомое количество участников и задач. Обратите внимание --- в первую очередь требуется максимизировать количество участников, а при максимальном числе участников --- количество задач.

Во второй строке выведите $T_0$ чисел --- номера задач в набранном комплекте. Все номера должны быть различными натуральными числами, не превосходящими $T$. Если возможно несколько оптимальных решений, выведите любое.

В первом примере можно было также взять задачу с номером $4$, поскольку ее знает один человек.

Во втором примере никто не знает задач с номерами $4$ и $5$, поэтому лучше всего взять их.