|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||9||7||7||77.778%|
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 < t ≤ 20). The first line of each input gives the number n of pizzas on the menu (1 ≤ n ≤ 60). 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 mi, giving the number of ingredients of the pizza on the menu (1 ≤ mi ≤ 20). 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 (w1, w2) where w1 is an ingredient in the foreign language that could be the same ingredient as w2 because w1 and w2 appear on the same set of pizzas. Sort the pairs in increasing lexicographical order by w1, and in case of a tie in increasing lexicographical order by w2. Print a blank line between different test cases.
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)