F. Уменьшение паросочетания
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан двудольный граф с $$$n_1$$$ вершинами в первой доле, $$$n_2$$$ вершинами во второй доле и $$$m$$$ ребрами. Максимальное паросочетание в таком графе — максимальный по размеру набор ребер, такой, что ни одна вершина не инцидентна более чем одному выбранному ребру.

Вам нужно обрабатывать запросы двух видов к этому графу:

  • $$$1$$$ — удалить минимально возможное количество вершин так, чтобы размер максимального паросочетания уменьшился ровно на $$$1$$$, и вывести список удаленных вершин. Затем найти любое максимальное паросочетание в полученном графе и вывести сумму номеров ребер, входящих в это паросочетание;
  • $$$2$$$ — запрос этого типа может быть задан только после запроса типа $$$1$$$. В качестве ответа на этот запрос вы должны вывести список номеров ребер, входящих в выбранное в предыдущем запросе паросочетание.

Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на последний запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.

Входные данные

В первой строке заданы четыре целых числа $$$n_1$$$, $$$n_2$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n_1, n_2 \le 2 \cdot 10^5$$$; $$$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$$$; $$$1 \le q \le 2 \cdot 10^5$$$).

Затем следуют $$$m$$$ строк. В $$$i$$$-й из них заданы два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n_1$$$; $$$1 \le y_i \le n_2$$$), обозначающих, что $$$i$$$-е ребро соединяет вершину $$$x_i$$$ в первой доле с вершиной $$$y_i$$$ во второй доле. Ни одна пара вершин не соединена более чем одним ребром.

Затем следуют $$$q$$$ строк. В $$$i$$$-й из них задано одно целое число — $$$1$$$ или $$$2$$$ — обозначающее $$$i$$$-й запрос. Дополнительные ограничения на запросы:

  • количество запросов типа $$$1$$$ не превысит размер максимального паросочетания в исходном графе;
  • количество запросов типа $$$2$$$ не превысит $$$3$$$;
  • каждому запросу типа $$$2$$$ предшествует запрос типа $$$1$$$;
  • ваше решение может считать $$$i$$$-й запрос только после того, как выведет ответ на запрос $$$(i-1)$$$ и сбросит буфер вывода.
Выходные данные

Для запроса типа $$$1$$$ выведите три строки:

  • в первой строке выведите количество удаляемых вершин;
  • во второй строке выведите список вершин, которые вы удаляете, следующим образом: если вы удаляете вершину $$$x$$$ из первой доли, выведите $$$x$$$; если вы удаляете вершину $$$y$$$ из второй доли, выведите $$$-y$$$ (номер со знаком минус);
  • в третьей строке выведите сумму номеров ребер, которые принадлежат некоторому максимальному паросочетанию. Ребра нумеруются от $$$1$$$ до $$$m$$$.

Для запроса типа $$$2$$$ выведите две строки:

  • в первой строке выведите одно число — размер максимального паросочетания;
  • во второй строке выведите номера ребер, формирующих максимальное паросочетание. Обратите внимание, что сумма этих номеров должна быть равна числу, которое вы вывели в конце предыдущего запроса типа $$$1$$$;

После вывода ответа на запрос не забудьте сбросить буфер вывода.

Протокол взаимодействия

В этой задаче вы можете получить вердикт «Решение зависло», так как ее нужно решать в режиме online. Если это случилось, то либо вы не следуете формату вывода, либо нарушаете какое-то из ограничений задачи. Вы можете считать, что это эквивалентно вердикту «Неправильный ответ».

Для вашего удобства в примере из условия вывод для запросов разделен строкой ===. Ваше решение не должно выводить эту строку; она добавлена только для того, чтобы было проще понять, где ответ на какой запрос.

Пример
Входные данные
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2
Выходные данные
1
-4
3
===
2
1 2
===
1
2
2
===
1
2