Республиканская олимпиада по информатике, 2011 год, 10-11 классы

Задача C. Слияние

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

Идет слияние двух компаний. В первой $n$ рабочих, а во второй $m$. Новое руководство хочет оставить только людей, которые не знакомы с рабочими другой компании. Вам известно, кто с кем знаком в разных компаниях. Найдите максимальное количество рабочих, которое новое руководство может оставить.

Формат входного файла

В первой строке входного файла заданы два целых числа $n$ и $m$ $(1 \le n,m \le 500).$ В следующих $n$ строках задано описание знакомых работников первой компании: $k_i$ — количество знакомых $i$-го работника первой компаний, и $k_i$ чисел, каждое из которых от 1 до $m,$ — номера знакомых во второй компании. В том же формате в следующих $m$ строках задано описание знакомых работников второй компании. Номера работников из первой компаний от 1 до $n.$

Формат выходного файла

В первой строке выходного файла должно быть три числа — максимальное количество рабочих, которое новое руководство может оставить, $k_1$ — сколько работников из первой компании и $k_2$ — сколько из второй. Во второй строке выведите $k_1$ чисел, номера работников которых нужно оставить из первой компании. В третьей строке выведите $k_2$ чисел, номера работников которых нужно оставить из второй компании. Если существует несколько ответов выведите любой.

Примеры:

Вход

3 2
1 1
1 2
0
1 1
1 1

Ответ

3 2 1
1 3
2