J. Максимальное независимое множество
2000 мс · 256 МБ · всё или ничего
В двудольном графе нужно найти наибольшее множество вершин, попарно не соединённых ребром, и вывести его.
Формат ввода
В первой строке и () — размеры долей. В следующих строках: — количество соседей -й вершины первой доли, затем их номера. Сумма всех не превосходит .
Формат вывода
В первой строке выведите размер максимального независимого множества. Во второй — количество взятых вершин первой доли и их номера в возрастающем порядке. В третьей — то же для второй доли.
Примеры
ввод
3 2 2 1 2 1 2 1 2
вывод
3 2 2 3 1 1
ввод
2 2 0 0
вывод
4 2 1 2 2 1 2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.