Teenagers from the local high school have
asked you to help them with the organization of next yearÕs Prom. The idea is
to find a suitable date for everyone in the class in a fair and civilized way.
So, they have organized a web site where all students, boys and girls, state
their preferences among the class members, by ordering all the possible
candidates. Your mission is to keep everyone as happy as possible. Assume that
there are equal numbers of boys and girls.
Given a set of
preferences, set up the blind dates such that there are no other two people of
opposite sex who would both rather have each other than their current partners.
Since it was decided that the Prom was Ladies' Choice, we want to produce the best
possible choice for the girls.
The input consists of a positive integer N, not greater than 1,000, indicating the number of couples in the
class. Next, there are N lines, each one
containing the all the integers from 1 to N,
ordered according to the girlÕs preferences. Next, there are N lines, each one containing all the integers from 1 to N, ordered according to the boyÕs preferences.
The output consists of a sequence of N lines, where the i-th line contains
the number of the boy assigned to the i-th girl
(from 1 to N).
5
1 2 3 5 4
5 2 4 3 1
3 5 1 2 4
3 4 2 1 5
4 5 1 2 3
2 5 4 1 3
3 2 4 1 5
1 2 4 3 5
4 1 2 5 3
5 3 2 4 1
1
2
5
3
4