Time Limit: 2 second(s) | Memory Limit: 32 MB |
Employment is a contract between two parties, one being the employer and the other being the employee. Now assume that there are n companies who require one employee each and there are n candidates. All the candidates interviewed in each of the companies and eventually they have different preferences over the companies and the companies have different preferences over the candidates.
So, you are given the task to assign each candidate to each company such that the employment scheme is stable. A scheme is stable if there is no pair (candidate_{i}, company_{j}) and (candidate_{x}, company_{y}) where
a) Candidate_{i} prefers company_{y} more than company_{j} and
b) Company_{y} prefers candidate_{i} more than candidate_{x}.
As there can be many solutions, any valid one will do.
Input starts with an integer T (≤ 30), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 100). The candidates are numbered from 1 to n and the companies are numbered from n+1 to 2n.
Each of the next n lines contains n distinct integers from n+1 to 2n, where the i^{th} line contains the company preference for the i^{th} candidate (1 ≤ i ≤ n).
Each of the next n lines contains n distinct integers from 1 to n, where the i^{th} line contains the candidate preference for the company which is denoted by n+i (1 ≤ i ≤ n).
For each case, print the case number and the (candidate, company) pairs. As there can be many solutions any valid one will do. And you can output the pairs in any order but print those as (candidate, company) pair.
Sample Input |
Output for Sample Input |
1 3 4 5 6 6 5 4 5 4 6 2 1 3 1 2 3 3 2 1 |
Case 1: (2 6) (1 4) (3 5) |
This is a special judge problem; wrong output format may cause 'Wrong Answer'.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |