Республиканская олимпиада по информатике 2011 года за 10 класс | Казахстанские олимпиады

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

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

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

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

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

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

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

Примеры

Вход

3 2
1 1
1 2
0
1 1
1 1

Выход

3 2 1
1 3
2