7. Найти склад

Не решаласьЛёгкая

Торговая сеть <<Руки из плеч>> состоит из нескольких магазинов-складов. В складской системе учёта они обозначены уникальным целочисленным идентификатором. $N$ пар магазинов-складов объединены в кластеры по территориальному принципу.

Периодически нужного товара не оказывается на определенном складе, и тогда товар может быть доставлен с другого склада, но только из своего кластера, т.к. доставка товаров со складов другого кластера нерентабельна.

Напишите программу, которая будет показывать, с какого на какой склад может быть доставлен необходимый товар.

Формат ввода

Первая строка содержит целое число $N$ ($0 \le N \le 10^6$) — количество связей между складами.

Следующие $N$ строк описывают связи между складами. Каждая из них содержит целые числа $U_i$ и $V_i$ ($1 \le U_i, V_i \le 10^9$) — идентификаторы соединённых складов.

Следующая строка содержит целое число $T$ ($1 \le T \le 10^3$) — количество запросов на доставку товара на склад для доставки покупателю.

Следующие $(2 \cdot T)$ строк описывают запросы. Первая строка каждой пары содержит целые числа $X_i$ и $K_i$ ($1 \le X_i \le 10^9$, $1 \le K_i \le 100$) — соответственно идентификатор склада, на который нужно доставить товар, и количество складов, содержащих товар. Вторая строка каждой пары содержит $K_i$ целых чисел $Y_{ij}$ ($1 \le Y_{ij} \le 10^9$) — идентификаторы складов с товаром.

Формат вывода

Для каждого запроса в отдельной строке выведите сначала целое число $R_j$ — количество складов, откуда можно доставить товар. Затем выведите $R_j$ целых чисел — номера складов, откуда можно доставить товар. Номера складов следует выводить в том порядке, в котором они перечислены в описании соответствующего запроса во входных данных.

Ограничения

Ограничение времени

2 с

Ограничение памяти

256 МБ

Пример 1

Ввод
8
54578972 99368556
79699669 54578972
64508306 99368556
56554555 64508306
27101564 81480071
89445516 27101564
93762227 81480071
89808815 93762227
4
56554555 2
93762227 79699669
99368556 2
64508306 56554555
27101564 2
99368556 79699669
93762227 2
56554555 54578972
Вывод
1 79699669
2 64508306 56554555
0 
0 

Пример 2

Ввод
10
85619126 64616465
98159933 85619126
73978229 85619126
29978081 64616465
72404745 29978081
97698445 75243921
36815728 97698445
18360411 97698445
66445821 75243921
92142380 66445821
4
97698445 4
75243921 92142380 98159933 73978229
66445821 4
29978081 92142380 73978229 97698445
18360411 4
29978081 92142380 98159933 97698445
36815728 4
64616465 92142380 97698445 29978081
Вывод
2 75243921 92142380
2 92142380 97698445
2 92142380 97698445
2 92142380 97698445

Теги

Нужно войти, чтобы отправить решение.Войти