URI Online Judge | 1852

Stark Direwolves

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

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

Robb GreyWind Summer Ghost Nymeria Lady Shaggydog
Jon Shaggydog GreyWind Summer Lady Ghost Nymeria
Sansa Summer Lady Ghost GreyWind Nymeria Shaggydog
Arya GreyWind Shaggydog Ghost Nymeria Lady Summer
Bran GreyWind Lady Summer Ghost Shaggydog Nymeria
Rickon Shaggydog Lady Ghost GreyWind Summer Nymeria
GreyWind Rickon Robb Arya Bran Sansa Jon
Ghost Jon Arya Sansa Bran Rickon Robb
Lady Sansa Robb Rickon Jon Arya Bran
Nymeria Rickon Bran Sansa Robb Arya Jon
Summer Rickon Bran Robb Arya Sansa Jon
Shaggydog Sansa Rickon Arya Jon Robb Bran

Robb GreyWind
Jon Ghost
Sansa Lady
Arya Nymeria
Bran Summer
Rickon Shaggydog