Stable Marriage

In mathematics, the stable marriage problem (SMP) is as follows: Given n men (numbered 0 .. n-1) and n women (numbered 0 .. n-1), where each person has ranked all members of the opposite sex with a unique number between 0 and n-1 in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable". It has been proven that one (or more solutions) to the SMP always exist.

Write a program that finds any stable marriage.

Input: marriage.in

The input file (marriage.in) will contain an unknown number of problems. Each problem starts with an integer n (1 ≤ n ≤ 100) that denotes the number of men and women who must be paired. This number is followed by a blank line. The next n lines show the preferences (in descending order) for man 0, man 1, ... man n-1. After another blank line, the next n lines show the preferences (in descending order) for woman 0, woman 1, ... woman n-1. If there is another problem in the input file, a blank line will follow the preferences of the women.

Sample Input File

4

0 1 2 3
0 1 2 3
0 1 2 3
0 1 2 3

3 2 1 0
3 2 1 0
3 2 1 0
3 2 1 0

9

6 2 7 8 5 3 1 0 4
4 3 7 2 0 1 5 6 8
3 7 2 8 6 4 5 0 1
8 6 3 1 4 7 2 0 5
1 5 3 8 7 6 4 0 2
1 6 7 5 4 2 3 0 8
0 5 1 2 7 4 3 8 6
4 5 8 0 1 7 3 2 6
5 0 3 6 4 7 2 8 1

2 0 4 1 7 6 5 8 3
8 3 7 0 6 5 2 1 4
2 0 7 8 4 3 1 5 6
7 6 4 2 1 5 3 8 0
5 8 1 4 0 3 6 2 7
1 3 4 0 5 7 2 8 6
8 2 7 1 6 4 3 5 0
5 2 1 0 7 3 4 8 6
7 1 5 3 8 0 2 6 4

1

0

0

Output: marriage.out

The first line of output should read Stable Marriage For each problem, the first line should be a blank line, the second line should indicate the number of people, and the next n lines should show the pairings for man 0, man 1, ... man n. The final line of output should read End of Stable Marriage. Match the output file format below exactly.

Sample Output File

Stable Marriage

4 people
Pair man 0 with woman 3
Pair man 1 with woman 2
Pair man 2 with woman 1
Pair man 3 with woman 0

9 people
Pair man 0 with woman 2
Pair man 1 with woman 4
Pair man 2 with woman 3
Pair man 3 with woman 1
Pair man 4 with woman 5
Pair man 5 with woman 7
Pair man 6 with woman 0
Pair man 7 with woman 8
Pair man 8 with woman 6

1 people
Pair man 0 with woman 0

End of Stable Marriage