Stable Marriage Problem

Problem code: STABLEMP

All submissions for this problem are available.

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, and w prefers m more then her husband a new marriage occurs between w and m. If w prefers her husband more, then she stays married to him. 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 2

Warning: large Input/Output data, be careful with certain languages

Author: admin
Date Added: 1-12-2008
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

"This problem always has a

chicodroid @ 15 Oct 2009 10:45 AM

"This problem always has a solution and your task is to find one." does that mean that a test case could have two answers?

Yes.

triplem @ 15 Oct 2009 11:26 AM

Yes.

my code is taking around 2.7

manib @ 25 Oct 2009 12:51 PM

my code is taking around 2.7 sec on my laptop for n==500.

Still while submitting am getting Time Limit Exceeded

I have checked the corner cases and i dont think my code will go in infinite loop in any of them.

P.S. am assuming n > 0

Any pointers is much appreciated. submission Id: 115016

Is the preferences of

manib @ 25 Oct 2009 01:04 PM

Is the preferences of women/men given sequentially (1,2,3,4 ... so on) as shown in problem sample input?

or coult it be like this too?

4 4 3 1 2
1 4 3 1 2
3 1 3 4 2
2 2 1 3 4



@admin for the case where

bsong @ 5 Feb 2010 11:12 PM

@admin for the case where n=7, isn't

 

1 4

2 7

3 1

4 6

5 5

6 3

7 2

 

a solution?

"if a man m prefers some

bsong @ 5 Feb 2010 11:19 PM

"if a man m prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m. If w prefers her husband more, then she stays married to him."

 

in case of n=7 and m=2, the solution given is w=5.

 

man 2 prefers woman 5 over his wife, however woman 5 prefers her own husband over man 2.

 

how is the solution correct?

This problem should be in the

boxer @ 20 Feb 2010 09:06 PM

This problem should be in the "Easy" section.

I am getting a WA , working

gunjanbansal @ 20 May 2010 08:15 PM

I am getting a WA , working fine for test cases above , any corner cases , i even tried to add an extra n in last solution.

Something that i may be missing ??

any hints ?? corner cases ??

gunjanbansal @ 21 May 2010 07:36 PM

any hints ?? corner cases ?? code worrks fine for above cases .

still looking for workarounds

gunjanbansal @ 24 May 2010 12:10 AM

still looking for workarounds ..

I dont seem to find any

gunjanbansal @ 31 May 2010 10:24 PM

I dont seem to find any corner cases in this one . I am getting WA , code is working for above two test cases .

@admin -  isn't the point

jimmy valentine @ 28 Jan 2011 02:12 AM

@admin -  isn't the point made by Shreyas above correct ? isn't the second test case incorrect ? Kindly reply.

Shreyas' point makes no

triplem @ 28 Jan 2011 04:00 AM

Shreyas' point makes no sense. Man 2's wife IS woman 5, so how could he prefer woman 5 to his wife?

Thanks for reply

jimmy valentine @ 28 Jan 2011 04:11 AM

Thanks for reply Stephen....but how can you say man 2's wife is 5? It is just that 2's first preference is 5. I am assuming in the beginning that (before this input) ith man is married ith woman, is that assumption correct ?

You have to decide who

triplem @ 28 Jan 2011 04:52 AM

You have to decide who marries who in a way that satisfies the conditions. In the sample output, man 2 is married to woman 5, and doesn't prefer any other woman who prefers him to their husband. I'm not really sure what you're asking.

got you, thanks...I am

jimmy valentine @ 29 Jan 2011 04:00 AM

got you, thanks...I am getting correct answer for the above inputs but it's giving wrong answer here. some corner test cases may help.

Since it is very easy to

triplem @ 29 Jan 2011 07:10 AM

Since it is very easy to check whether an output is correct or not, you can generate your own test cases and check your answer is correct very easily, even for n=500. There aren't really any corner cases that are more special than others.

"If w prefers her husband

vivek.cs.iitr @ 31 Jan 2011 06:08 PM

"If w prefers her husband more, then she stays married to him."

But where is it given that i'th woman husband is j'th man ?

You have to output a set of

triplem @ 1 Feb 2011 06:16 AM

You have to output a set of marriages that is stable; ie where nobody would marry somebody else due to those conditions.

can a man marry twice?

ascending @ 26 May 2011 05:10 PM
can a man marry twice?

in the first sample test

cyberax @ 30 Apr 2012 10:08 PM
in the first sample test case, the man n°3 prefers the woman n°3 than the woman n°1. but in the proposed solution, he's been married to her anyway. i don't understand... "if a man m prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m" marriage (3, 1) shouldn't have occurred ! any hint ?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions