By Ricardo Oliveira, UFPR Brazil
Jon: "Lord Stark? There are five pups, one for each of the Stark children. The direwolf is the sigil of your House. They were meant to have them."
During a trip, Ned Stark found N direwolf pups and decided to give each pup to one of his N children. Ned wants to make both his children and the direwolves happy, so he wants to find the ideal assignment of children and direwolves.
After playing with the pups for a while, each children gave Ned a list of pups in order of preference, i.e., each children wants to have the pup which is on the top of his/her list; if this is not possible, the children wants the pup which appears second in the list, and so on.
After observing how each direwolf reacts to each children, Ned also deduced, for each direwolf, the list of children it wants to be its owner, also in order of preference.
Ned must find an assignment such that, for any children Ci and any direwolf Dj, it does not happen that Ci prefers Dj over his direwolf and Dj prefers Ci over its owner. If there is more than one possible assignment, Ned wants the assignment such that each children has the best (most preferable) pup he/she can have.
The first line contains the integer N (1 ≤ N ≤ 200). The next N lines describe Ned's children. Each line contains N+1 strings. The first one is the name of the children. The next N strings consists on the name of the pups in order of preference, with the first pup given in the line being the children's most preferable. The next N lines describe the direwolf pups. Each line contains the name of the pup and its lists of children, also in order of preference.
Each string contains at most 10 lowercase and/or uppercase English letters.
Print N lines. Each line must contain two strings Ci and Dj, meaning that children Ci must own the direwolf Dj. Print the children in the same order they are described in the input.
Input Samples | Output Samples |
6 |
Robb GreyWind |