sgu264：Travel(稳定婚姻问题)

题目大意：

有n个男人和n个女人，每个男人都在心中有对n个女人的喜欢程度，每个女人亦然。求出一种完备匹配的方案使得任意一对男女(除去匹配的n对)，满足这对男女之间的喜欢程度不都大于喜欢自己配对对象的程度。-264. Travel



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　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 th