EduBrick

J. Максимальное независимое множество

2000 мс · 256 МБ · всё или ничего

В двудольном графе нужно найти наибольшее множество вершин, попарно не соединённых ребром, и вывести его.

Формат ввода

В первой строке nn и mm (1≤n,m≤20001 \le n, m \le 2000) — размеры долей. В следующих nn строках: KiK_i — количество соседей ii-й вершины первой доли, затем их номера. Сумма всех KiK_i не превосходит 2⋅1052 \cdot 10^5.

Формат вывода

В первой строке выведите размер максимального независимого множества. Во второй — количество взятых вершин первой доли и их номера в возрастающем порядке. В третьей — то же для второй доли.

Примеры

ввод
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
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.