Omiai P84615


Statement
 

pdf   zip

html

Japan is a surprising country where the highest technology lives arm by arm with the most traditional ceremonies and rites. One of such traditions is that of omiai (from miru, see, and au, meet).

In some families, when parents feel that their son or daughter should already be getting married but has not shown any interest (or skill) in doing so, they often decide to contact a professional matchmaker or nakōdo. They give the nakōdo pictures and resumes of their child, and are in turn offered those of the nakōdo’s customers of the opposite sex. The parents and the son or daughter sort the possible mates according to their wealth, education and cultural level. The nakōdo then arranges meetings following these preferences, until a wedding is accorded. It is customary that the groom’s parents pay a visit to the bride’s to offer some money, including the wedding expenses. This form of marriage is more common in rural areas of Japan, where you can breathe tradition in every corner...

However, some groups in the Japanese society advocate for a change of these traditions towards a more modern concept of love. One of them is that of the recently founded PaasoCon-Omiai Co Ltd. A great number of investors have been attracted by the words of its CEO Yoshimura Akira, who claims that he can replace by computers the crew of nakōdo that omiai enterprises usually require. Mr Yoshimura has promised that his computers will be able to match a large number of men and women in a perfect way. He is so sure about it that he has announced a great ceremony with all the couples matched by him.

If during this ceremony a man and a woman meet by chance and start talking, there is the risk that they she prefers him to her computer-found mate, and that he also prefers her to his assigned couple. In this case, they could escape together, which would cause great commotion. Mr Yoshimura is aware of this danger, and has promised that it will not happen.

The investors are enthusiastic, but in fact Mr Yoshimura is not quite sure if his promise can really be done, and so has posted a job looking for a skilled programmer. Were his promises too optimistic, and will he have to face dishonour (and harakiri) in front of his investors?

Input

Input consists of several cases. Every case begins with the number n of men and women in the case. Follow n lines, one for each man, with a list of all the women sorted by decreasing preference. Follow n lines with the same information for the women. A case with n = 0 marks the end of input. You can assume 2 ≤ n ≤ 256.

Output

For every case, print a line for each matched couple, with the number of the man followed by the number of the woman, and sorted by the number of the man. If several matchings are possible, any one of them will be accepted. If no matching is possible, print a single line with “Ii katana wo kaita hoo ga ii.” (You’d better buy a good katana). Print a blank line after every case.

Public test cases
  • Input

    3
    1 2 3
    1 2 3
    1 2 3
    2 3 1
    2 3 1
    2 3 1
    
    0
    

    Output

    1 3
    2 1
    3 2
    
    
  • Information
    Author
    Edgar Gonzàlez
    Language
    English
    Official solutions
    C++
    User solutions
    Event
    Quart Concurs de Programació de la UPC - Semifinal
    Date
    2006-09-20