시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 1 1 33.333%

문제

Для составления задач на очередное соревнование организаторы пригласили $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$. Если возможно несколько оптимальных решений, выведите любое.

예제 입력 1

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

예제 출력 1

2 1
1

예제 입력 2

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

예제 출력 2

3 2
4 5

힌트

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

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