print1962. Синонимы

printСинонимы

Ограничения: время – 200ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Имеется словарь, содержащий некоторое количество слов. Для некоторых пар слов известно, что они являются синонимами. Известно также, что рассматриваемый язык обладает следующим свойством: если слова `a` и `b` — синонимы, слова `b` и `c` — тоже синонимы, то тогда слова `a` и `c` также являются синонимами.
Требуется написать программу, которая по заданному слову находит его синонимы.
В первой строке входного файла записано через пробел целое число `M` (`1\ ≤\ M\ ≤\ 10\ 000`). В каждой из следующих `M` строк записана через пробел пара слов, для которых известно, что они являются синонимами. Слова содержат только строчные латинские буквы, длина каждого слова не превышает 10 символов.
Следующая строка содержит целое число `Q` — количество запросов (`1\ ≤\ Q\ ≤\ 1000`). Каждая из следующих `Q` строк содержит слово, для которого нужно выполнить поиск синонимов, и через пробел целое число `K_i` — количество синонимов для вывода в данном запросе (`1\ ≤\ K_i\ ≤\ 10\ 000`).
Выведите в выходной файл `Q` строк (по одной строке на каждый запрос). В каждой строке сначала выведите общее количество синонимов указанного слова и затем через пробел его первые `K_i` синонимов в лексикографическом порядке. Если количество синонимов слова меньше, чем `K_i`, то выведите их все.
Примечание. Гарантируется, что общее количество выведенных слов во всех ответах не превысит `10\ 000`.

Пример ввода

4
aba caba
daba vaba
caba vaba
maba zaba
4
caba 100
caba 1
zaba 5
laba 2

Пример ввода

3 aba daba vaba
3 aba
1 maba
0
Источник: XVI межвузовская олимпиада по программированию, Вологда, 2013
loading