Lesson 14

Programming problem. Implement an algorithm for finding a stable matching between \(n\) men and \(n\) women (both parts are indexed by \([n]\)). The first line of the input contains an integer \(1 \le n \le 100\). Each of the next \(n\) lines specifies a list of the corresponding men preferences. It is followed by \(n\) preference lists of women. Output a permutation of \([n]\) (the \(i\)-th element of this permutation is the index of the woman to be paired with the \(i\)-th man).

3
2 1 3
1 2 3
2 3 1
1 2 3
2 1 3
3 1 2

2 1 3