STABLEMP  Stable Marriage Problem
There are given n men and n women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange n marriages in such a way that if a man m prefers some woman w more than his wife, then w likes her husband more than m. In this way, no one leaves his partner to marry somebody else. This problem always has a solution and your task is to find one.
Input
The first line contains a positive integer t <= 100 indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer n <= 500 (the number of marriages to find). The next n lines are the woman's preferences: ith line contains the number i (which means that this is the list given by the ith woman) and the numbers of men (the first choice of ith woman, the second choice,...). Then, the men's preferences follow in the same format.
Output
For each test case print n lines, where each line contains two numbers m and w, which means that the man number m and the woman number w should get married.
Example
Input: 2 4 1 4 3 1 2 2 2 1 3 4 3 1 3 4 2 4 4 3 1 2 1 3 2 4 1 2 2 3 1 4 3 3 1 2 4 4 3 2 4 1 7 1 3 4 2 1 6 7 5 2 6 4 2 3 5 1 7 3 6 3 5 7 2 4 1 4 1 6 3 2 4 7 5 5 1 6 5 3 4 7 2 6 1 7 3 4 5 6 2 7 5 6 2 4 3 7 1 1 4 5 3 7 2 6 1 2 5 6 4 7 3 2 1 3 1 6 5 4 3 7 2 4 3 5 6 7 2 4 1 5 1 7 6 4 3 5 2 6 6 3 7 5 2 4 1 7 1 7 4 2 6 5 3 Output: 1 3 2 2 3 1 4 4 1 4 2 5 3 1 4 3 5 7 6 6 7 2Warning: large Input/Output data, be careful with certain languages
hide comments
AKSHAY TANEJA:
20201205 20:40:02
AC in one go :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150808 09:35:06
Nice problem :D


Shubham Somani:
20130112 09:37:48
Had a blast while solving this problem!!! :D :D (almost lyk the best prob evr :P) 

Lai Manh Tuan:
20130111 09:18:04
This is the first problem mentioned in the book "Algorithm Design". 

amit:
20120614 19:15:42
the problem statement is different from the same question on codechef...its wrong here..please see there.. 
Added by:  Darek Dereniowski 
Date:  20041213 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  problem known as the Stable Marriage Problem 