레스토랑
시간 제한3초메모리 제한2048 MB
고객과 식당 양쪽이 선호 순위를 가지며 식당마다 정원이 있을 때, 안정적인 배정을 찾아 배정된 고객 번호를 오름차순으로 출력한다.
문제
모두가 파리에 있는 레스토랑에 다시 가게 되어 매우 기뻐한다. 하지만 당분간 레스토랑은 좌석 수가 매우 제한적이다. 두 레스토랑이 가능한 한 많은 사람을 받을 수 있고, 손님이 원하는 좌석에 들어갈 수 있도록 하려 한다.
명의 손님과 개의 레스토랑이 있고, 손님은 부터 까지, 레스토랑은 부터 까지 번호가 매겨져 있다. 각 손님은 레스토랑의 부분집합에 예약을 하고, 자신의 예약 목록을 선호도 순으로 제시한다. 각 레스토랑은 받은 예약을 자체적인 선호 순서로 정렬한다. 예를 들어 레스토랑은 먼저 등록한 손님을 더 높게 평가할 수 있다. 각 레스토랑 에는 정원 , 즉 수용할 수 있는 최대 손님 수가 있다.
다음 조건을 만족하도록 일부 손님을 레스토랑에 배정하는 방법을 찾아야 한다.
-
어떤 레스토랑도 정원보다 많은 손님을 받지 않는다.
-
각 손님은 많아야 한 레스토랑에서 테이블을 받는다.
-
레스토랑 과 에 예약한 손님 의 쌍 중에서 다음을 모두 만족하는 경우가 없다.
- 가 테이블을 받지 못했거나, 가 배정받은 레스토랑보다 을 더 선호한다.
- 에 빈 좌석이 있거나, 이 만석이지만 에 배정된 손님 중 적어도 한 명보다 를 더 선호한다.
추가로 알아 둘 점:
- 모든 손님은 적어도 하나의 예약을 했다.
- 레스토랑은 자신에게 예약을 한 손님만 평가한다. 레스토랑에 예약한 손님이 한 명도 없을 수 있다.
입력
첫째 줄에 과 이 주어진다.
다음 개의 줄은 정원을 나타내며, 번째 줄에는 레스토랑 의 정원 가 정수로 주어진다.
이어서 개의 줄이 주어진다. 번째 줄은 손님 의 예약 목록을 선호도 순으로 나타낸다. 이 줄에는 서로 다른 정수(1 이상 이하)가 공백으로 구분되어 선호도가 높은 것부터 낮은 것 순으로 주어진다.
이어서 개의 줄이 주어진다. 번째 줄은 레스토랑 의 정렬된 선호도를 나타낸다. 이 줄에는 레스토랑 에 예약한 손님이 없을 경우 숫자 0이 주어지고, 그렇지 않으면 레스토랑 에 예약한 손님의 번호가 서로 다른 정수로 공백으로 구분되어 레스토랑이 선호하는 순서대로 주어진다.
출력
위 규칙에 따라 가능한 배정 중 하나에서 테이블을 받은 손님의 집합을 출력한다. 집합은 한 줄에 손님 하나씩, 번호 오름차순으로 출력한다.
제한
- 예약 선택지의 총 개수는 이하이다.