Hide

Problem H
Pizza Hawaii

You are travelling in a foreign country. Although you are also open to eat some regional food, you just cannot resist after you have found an Italian restaurant which offers pizza. Unfortunately the menu is written in the foreign language, so the list of ingredients of the pizzas are incomprehensible to you. What will you do?

One thing that you notice is that each pizza has an Italian name, which sounds quite familiar to you. You even remember for each named pizza what the ingredients of this pizza usually are. You want to use that information to figure out what the possible meaning of each word on the list of ingredients is.

Input

The first line of the input gives the number of test cases $t$ ($0 < t \le 20$). The first line of each input gives the number $n$ of pizzas on the menu ($1 \le n \le 60$). The following $3 \cdot n$ lines describe the pizzas on the menu. Each pizza description starts with one line containing the name of the pizza. The name of the pizza consists of between $3$ and $20$ uppercase and lowercase letters. The next line starts with an integer $m_ i$, giving the number of ingredients of the pizza on the menu ($1 \le m_ i \le 20$). The rest of the line contains the $m_ i$ ingredients separated by spaces. Each ingredient is a word consisting of between $2$ and $20$ lowercase letters. The third line of each pizza description gives the ingredients in your native language in the same format. Note that the number of ingredients may differ, because each restaurant may use slightly different ingredients for pizzas with the same name, so the ingredients you remember for a pizza with that name may not match the actual ingredients.

Output

For each test case print all pairs of words ($w_1, w_2$) where $w_1$ is an ingredient in the foreign language that could be the same ingredient as $w_2$ because $w_1$ and $w_2$ appear on the same set of pizzas. Sort the pairs in increasing lexicographical order by $w_1$, and in case of a tie in increasing lexicographical order by $w_2$. Print a blank line between different test cases.

Sample Input 1 Sample Output 1
2
3
Hawaii
4 tomaten schinken ananas kaese
4 pineapple tomatoes ham cheese
QuattroStagioni
6 tomaten kaese salami thunfisch spinat champignons
6 mushrooms tomatoes cheese peppers ham salami
Capricciosa
6 champignons kaese tomaten artischocken oliven schinken
5 cheese tomatoes mushrooms ham artichoke
1
Funghi
3 tomaten kaese champignons
3 cheese tomatoes mushrooms
(ananas, pineapple)
(artischocken, artichoke)
(champignons, mushrooms)
(kaese, cheese)
(kaese, ham)
(kaese, tomatoes)
(oliven, artichoke)
(salami, peppers)
(salami, salami)
(spinat, peppers)
(spinat, salami)
(thunfisch, peppers)
(thunfisch, salami)
(tomaten, cheese)
(tomaten, ham)
(tomaten, tomatoes)

(champignons, cheese)
(champignons, mushrooms)
(champignons, tomatoes)
(kaese, cheese)
(kaese, mushrooms)
(kaese, tomatoes)
(tomaten, cheese)
(tomaten, mushrooms)
(tomaten, tomatoes)

Please log in to submit a solution to this problem

Log in