시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 72 18 13 25.000%

문제

연애가 하고싶은 형곤이는 소개팅을 통해서 자신의 짝을 만나려고 한다. 형곤이의 소개팅에는 특별한 규칙이 있다.

남자와 여자가 각각 N명씩 만나서 서로가 만나고 싶은 순위를 정해서 최적의 짝을 만들게 된다. 일반적인 소개팅이라면 성공 확률이 높지 않지만 이 소개팅은 성공률이 100%이다. 모두에 대하여 서로가 만족할 수 있는 최적의 짝을 정해준다. 최적의 짝이란 임의의 남녀 쌍에 대하여 서로가 현재 파트너보다 우선순위가 높은 경우가 없는 것을 말한다. 예를 들어 남자와 여자가 각각 2명이라고 할 때 다음의 경우를 생각해보자.

남자와 여자가 각각 2명씩 소개팅에 참여한다. 남자1은 [여자1, 여자2] 남자2는 [여자2, 여자1], 여자1은 [남자1, 남자2], 여자2는 [남자2, 남자1] 순서로 만나고 싶어한다고 하면 남자1-여자2, 남자2-여자1을 매칭하는 것은 최적의 짝이 아니다. 왜냐하면 남자1과 여자1은 현재 자신의 파트너보다 서로를 더 선호하기 때문이다. 형곤이가 소개팅에서 최적의 짝을 찾는 프로그램을 작성해보자. 최적의 짝이 여러 개인 경우, 아무거나 구하면 된다.

입력

첫 번째 줄에는 남자와 여자의 수를 의미하는 N (1 ≤ N ≤ 200)이 주어진다.

두 번째 줄과 세 번째 줄에는 각각 N명의 남자, N명의 여자의 이름이 주어진다.

이름은 알파벳 소문자와 숫자로 이루어져 있으며 4글자 이상 10글자 이하이다.

3번째 줄부터 N + 2번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 남자의 이름이고, 그 후부터는 모든 여자의 이름이 해당 남자가 선호하는 순서대로 주어진다.

N + 3번째 줄부터 2N + 2번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 여자의 이름이고, 그 후부터는 모든 남자의 이름이 해당 여자가 선호하는 순서대로 주어진다.

모든 이름은 유일하며 서로 다른 성별 간에도 같은 이름이 존재하지 않는다.

두, 세 번째 줄에서 나오는 남자, 여자 이름의 순서와 그 이후에 나오는 남자, 여자 이름의 순서는 관련이 없다.

출력

N개의 줄에 각각 남자와 여자를 매칭한 결과를 남자와 여자의 이름에 공백을 두어 출력하자.

출력하는 순서는 상관이 없다.

예제 입력 1

3
hyeyoo doby yepark
sunhpark soohchoi yomoon
hyeyoo soohchoi sunhpark yomoon
doby yomoon soohchoi sunhpark
yepark sunhpark soohchoi yomoon
sunhpark yepark hyeyoo doby
soohchoi doby hyeyoo yepark
yomoon hyeyoo doby yepark

예제 출력 1

doby yomoon
hyeyoo soohchoi
yepark sunhpark

출처

University > 충남대학교 > 제4회 생각하는 프로그래밍 대회 I번

  • 문제를 다시 작성한 사람: jh05013
  • 문제를 만든 사람: siontama