Lesson 14

Programming problem. Implement an algorithm for finding a stable matching between \(n\) students and \(n\) companies (both sides 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 the preference list of the corresponding student. These are followed by the \(n\) preference lists of the companies. Output a permutation of \([n]\) (the \(i\)-th element of this permutation is the index of the company to be paired with the \(i\)-th student).

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

2 1 3