I. Составление задач
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Примеры
Входные данные
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
Примечание

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

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

Обратите внимание — в этой задаче требуется считать из входного потока много данных. Для этого в программе на языке C++ следует добавить в начало функции main следующие три строчки:


ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

В программе на языке Java следует отказаться от использования класса Scanner.