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