Составление задач

문제

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

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

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

입력

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

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

출력

В первой строке выведите два числа $P_{0}P\_0$ и $T_{0}T\_0$ --- искомое количество участников и задач. Обратите внимание --- в первую очередь требуется максимизировать количество участников, а при максимальном числе участников --- количество задач.

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

힌트

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

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

3 4 6
1 1
1 2
2 2
2 3
3 3
3 4

2 1
1

3 5 6
1 1
1 2
2 1
2 3
3 1
3 3

3 2
4 5