시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 51 20 14 42.424%

문제

솔로부대를 이끄는 주경이는 어느덧 나이가 11010살이다. 솔로 탈출 및 결혼을 하고 싶은 주경이는 ‘짝’에 출연하기로 결정하였다.

‘짝’의 매칭 방법은 다음과 같다.

  1. n명의 남자와 n명의 여자가 있다.
  2. 모든 남자는 반드시 단 한 명의 여자와 짝이 지어 지고 마찬가지로 모든 여자도 단 한 명의 남자와 짝이 지어진다.
  3. 각각의 남녀는 다른 이성에 대한 선호도가 확실히 존재한다.
  4. 임의의 남자 m과 여자 w에 대해서도 각자의 파트너보다 서로를 더 선호하는 경우는 없어야 된다. (즉 1번 남자와 2번 여자가 짝이고 3번 여자와 2번 남자가 짝이 되었을 경우, 1번 남자가 2번 여자보다 3번 여자를 더 선호하고 3번 여자가 2번 남자보다 1번 남자를 더 선호하는 경우는 없어야 한다.)

각각의 남녀의 선호도가 주어졌을 때 짝이 어떻게 지어지나 알아내는 프로그램을 작성하자.

입력

첫째 줄에 남자와 여자의 사람 수 (1 ≤ N ≤ 1000) 이 주어진다. 각각의 남녀는 1부터 N까지의 고유 번호가 주어진다. 그 후 N개의 줄에는 각각의 남자가 선호하는 여자의 선호도가 주어지고 그 후 N개의 줄에는 각각의 여자가 선호하는 남자의 선호도가 주어진다.

(선호도는 우선적으로 선호하는 사람의 번호가 주어진다.)

출력

N개의 줄에 i번 남자가 누구와 짝이 되는지 출력 한다.

예제 입력

4
3 2 1 4
2 4 1 3
3 1 4 2
1 2 3 4
1 3 2 4
3 4 2 1
2 3 4 1
4 2 1 3

예제 출력

1
4
3
2

힌트