time limit per test: 1 sec. memory limit per test: 65536 KB
input: standard output: standard
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.
3 Vasya Anna Elena Katya Petya Elena Anna Katya Egor Anna Elena Katya Anna Petya Vasya Egor Elena Vasya Petya Egor Katya Vasya Petya Egor
YES Vasya Anna Petya Elena Egor Katya
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).
Roman V. Alekseenkov
Saratov SU Contest: Golden Fall 2004
October 2, 2004
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov