Задача №111129. Королевская задача
В одной далекой-далекой галактике жил-был король, и было у него N сыновей. Кроме того, в этом королевстве жило N прекрасных девушек, и король знал про каждого из своих сыновей, кого из этих девушек тот любит. Сыновья короля были молоды и легкомысленны, так что вполне возможно, что один сын любит нескольких девушек. Король попросил волшебника найти для каждого из сыновей девушку, которую тот любит, так, чтобы они могли пожениться. И королевский волшебник сделал это — для каждого из сыновей была выбрана девушка, на которой он может жениться, причем он любил ее, и, конечно, каждая прекрасная девушка выходила замуж только за одного из королевских сыновей. Однако, король посмотрел на список и сказал: «Мне нравится, то что ты сделал, но я не до конца удовлетворен. Для каждого из сыновей я хотел бы знать всех девушек, на которых он может жениться. Конечно, после того, как он женится на одной из этих девушек, для другого сына ты должен быть в состоянии выбрать девушку, на которой он может (и хочет) жениться...». Задача, которую король задал волшебнику, оказалась слишком сложной для него. Вы должны спасти жизнь волшебника, решив эту задачу.
Первая строка входного файла содержит число N — количество сыновей у короля (0 ≤ N ≤ 2 000). Следующие N строк для каждого сына описывают список девушек, которые ему нравятся: первое число Ki — количество таких девушек, а затем Ki различных целых чисел от 1 до N, задающие девушек. Сумма всех Ki не превосходит 200 000. Последняя строка входного файла содержит список, сделанный волшебником — N различных целых чисел: для каждого сына номер девушки, на которой тот должен жениться согласно списку. Гарантируется, что список корректен, т.е. каждому из сыновей нравится девушка, на которой он должен жениться.
Выведите N строк. Для каждого из сыновей короля напечатайте число Li — количество различных девушек, на которых он может и хочет женится, так, что после его свадьбы все еще можно поженить остальных королевских сыновей. После этого напечатайте Li различных чисел, обозначающих девушек, в возрастающем порядке.
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
2 1 2
2 1 2
1 3
1 4