time limit per test: 1
memory limit per test: 65536
Travel agency decides to make a summer trip to Petrozavodsk for its best clients. N men and N women were selected to take part in this trip. There are N cars in the travel agency and in each car there are exactly two places for passengers, and one for driver. The head of the customer service of agency decided to place one man and one woman in each car, that's why they decided to ask customers to prepare their preference lists.
The preference list for each person is a list of persons of opposite sex in order from best to worst. So, each man lists all women in the order of preference, and vice versa.
Suppose we've assigned woman and men in such a way that each man has got exactly one woman and each woman has got exactly one man. We'll call this situation a 'perfect assignment'.
If in a perfect assignment there is a pair of man and woman not assigned to each other and they prefer each other to the current partners, this pair is called 'unstable'. Given men and women preference lists, you should create a perfect assignment without unstable pairs.
First line of input file contains one number N (1 <= N <= 800). The following N lines contain men preference lists in the form: <man> <woman1> ... <womanN>.
The following N lines contain woman preference lists in the form: <woman> <man1> ... <manN>. Names consist of lowercase and uppercase English letters with length no more than 10 characters.
It's guaranteed that there are exactly N distinct man names and N distinct woman names in the input file.
First line on output file should be 'YES' if requested assignment exists and 'NO' otherwise. If the answer is 'YES', you should output the requested assignment - N lines with pairs <man> <woman> in any order. If multiple solutions exist, you can choose any one of them.
Vasya Anna Elena Katya
Petya Elena Anna Katya
Egor Anna Elena Katya
Anna Petya Vasya Egor
Elena Vasya Petya Egor
Katya Vasya Petya Egor
This problem has huge tests. Some read/write routines work very slow in several compilers (especially, C/C++: try to use getc() putc() functions to avoid IO troubles).
|Author:||Roman V. Alekseenkov
|Resource:||Saratov SU Contest: Golden Fall 2004
|Date:||October 2, 2004
|Server time: 2017-09-22 15:42:11||Online Contester Team © 2002 - 2016. All rights reserved.|