Processing math: 100%

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


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

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Идет слияние двух компаний. В первой n рабочих, а во второй m. Новое руководство хочет оставить только людей, которые не знакомы с рабочими другой компании. Вам известно, кто с кем знаком в разных компаниях. Найдите максимальное количество рабочих, которое новое руководство может оставить.
Формат входного файла
В первой строке входного файла заданы два целых числа n и m (1n,m50). В следующих n строках задано описание знакомых работников первой компании: ki — количество знакомых i-го работника первой компаний, и ki чисел, каждое из которых от 1 до m, — номера знакомых во второй компании. В том же формате в следующих m строках задано описание знакомых работников второй компании. Номера работников из первой компаний от 1 до n.
Формат выходного файла
В первой строке выходного файла должно быть три числа — максимальное количество рабочих, которое новое руководство может оставить, k1 — сколько работников из первой компании и k2 — сколько из второй. Во второй строке выведите k1 чисел, номера работников которых нужно оставить из первой компании. В третьей строке выведите k2 чисел, номера работников которых нужно оставить из второй компании. Если существует несколько ответов выведите любой.
Примеры:
Вход
3 2
1 1
1 2
0
1 1
1 1
Ответ
3 2 1
1 3
2
посмотреть в олимпиаде

Комментарий/решение: