eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Pizza Hawaii

Pizza Hawaii

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

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.

Вхідні дані

The first line of the input gives the number of test cases t (0 < t20). The first line of each input gives the number n of pizzas on the menu (1n60). The following 3·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 (1m_i20). The rest of the line contains the mi 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.

Вихідні дані

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.

Приклад

Вхідні дані #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
Вихідні дані #1
(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)
Джерело ACM ICPC German Collegiate Programming Contest 2012