Дан двудольный граф с \(n_1\) вершинами в первой доле, \(n_2\) вершинами во второй доле и \(m\) ребрами. Максимальное паросочетание в таком графе — максимальный по размеру набор ребер, такой, что ни одна вершина не инцидентна более чем одному выбранному ребру.
Вам нужно обрабатывать запросы двух видов к этому графу:
- \(1\) — удалить минимально возможное количество вершин так, чтобы размер максимального паросочетания уменьшился ровно на \(1\), и вывести список удаленных вершин. Затем найти любое максимальное паросочетание в полученном графе и вывести сумму номеров ребер, входящих в это паросочетание;
- \(2\) — запрос этого типа может быть задан только после запроса типа \(1\). В качестве ответа на этот запрос вы должны вывести список номеров ребер, входящих в выбранное в предыдущем запросе паросочетание.
Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на последний запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.
Выходные данные
Для запроса типа \(1\) выведите три строки:
- в первой строке выведите количество удаляемых вершин;
- во второй строке выведите список вершин, которые вы удаляете, следующим образом: если вы удаляете вершину \(x\) из первой доли, выведите \(x\); если вы удаляете вершину \(y\) из второй доли, выведите \(-y\) (номер со знаком минус);
- в третьей строке выведите сумму номеров ребер, которые принадлежат некоторому максимальному паросочетанию. Ребра нумеруются от \(1\) до \(m\).
Для запроса типа \(2\) выведите две строки:
- в первой строке выведите одно число — размер максимального паросочетания;
- во второй строке выведите номера ребер, формирующих максимальное паросочетание. Обратите внимание, что сумма этих номеров должна быть равна числу, которое вы вывели в конце предыдущего запроса типа \(1\);
После вывода ответа на запрос не забудьте сбросить буфер вывода.
Протокол взаимодействия
В этой задаче вы можете получить вердикт «Решение зависло», так как ее нужно решать в режиме online. Если это случилось, то либо вы не следуете формату вывода, либо нарушаете какое-то из ограничений задачи. Вы можете считать, что это эквивалентно вердикту «Неправильный ответ».
Для вашего удобства в примере из условия вывод для запросов разделен строкой ===. Ваше решение не должно выводить эту строку; она добавлена только для того, чтобы было проще понять, где ответ на какой запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|