{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eTravel 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\u0027s why they decided to ask customers to prepare their preference lists. \u003cbr\u003eThe 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. \u003cbr\u003eSuppose we\u0027ve 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\u0027ll call this situation a \u0027perfect assignment\u0027. \u003cbr\u003eIf 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 \u0027unstable\u0027. Given men and women preference lists, you should create a perfect assignment without unstable pairs. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eFirst line of input file contains one number N (1 \u0026lt;\u003d N \u0026lt;\u003d 800). The following N lines contain men preference lists in the form: \u0026lt;man\u0026gt; \u0026lt;woman1\u0026gt; ... \u0026lt;womanN\u0026gt;. \u003cbr\u003eThe following N lines contain woman preference lists in the form: \u0026lt;woman\u0026gt; \u0026lt;man1\u0026gt; ... \u0026lt;manN\u0026gt;. Names consist of lowercase and uppercase English letters with length no more than 10 characters. \u003cbr\u003eIt\u0027s guaranteed that there are exactly N distinct man names and N distinct woman names in the input file. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eFirst line on output file should be \u0027YES\u0027 if requested assignment exists and \u0027NO\u0027 otherwise. If the answer is \u0027YES\u0027, you should output the requested assignment - N lines with pairs \u0026lt;man\u0026gt; \u0026lt;woman\u0026gt; in any order. If multiple solutions exist, you can choose any one of them. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e3 \u003cbr\u003eVasya Anna Elena Katya \u003cbr\u003ePetya Elena Anna Katya \u003cbr\u003eEgor Anna Elena Katya \u003cbr\u003eAnna Petya Vasya Egor \u003cbr\u003eElena Vasya Petya Egor \u003cbr\u003eKatya Vasya Petya Egor \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eYES \u003cbr\u003eVasya Anna \u003cbr\u003ePetya Elena \u003cbr\u003eEgor Katya \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eNote\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThis 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). \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eRoman V. Alekseenkov \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003eSaratov SU Contest: Golden Fall 2004 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eOctober 2, 2004 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}