Раздел Империи
(Время: 5 сек. Память: 64 Мб Сложность: 75%)
Великий император Виталиус Демидович вскоре уйдёт на покой. Во владениях он имеет империю, которая представляет из себя N стран, соединённых N - 1 дорогой так, что из каждой страны есть путь в любую другую.
Придворный оракул императора рассказал, что некоторые страны могут ослабеть и исчезнуть с лица Земли. Теперь Виталиус не находит покоя. Ведь если некоторые страны исчезнут, то империя может распасться на несколько новых. А именно, после исчезновения страны вслед за ней исчезают и все дороги, которые к ней примыкали. Все оставшиеся страны объединяются по новым империям по следующему правилу: если две страны всё ещё достижимы друг от друга по оставшимся дорогам, то они будут находиться в одной империи.
Император беспокоится о величии новых империй, а именно его интересует размер наибольшей из образовавшихся империй после удаления некоторых стран. Придворный картограф Виталиуса, то есть Вы, теперь завален запросами для некоторых множеств стран. Для каждого такого множества вычислите наибольший размер новой империи, если заданные страны исчезнут.
Входные данные
В первой строке входного файла INPUT.TXT содержится целое число N — размер империи (1 ≤ N ≤ 200 000).
В следующих N - 1 строках содержится по паре чисел ai и bi означающих, что соответствующие страны соединены дорогой (1 ≤ ai, bi ≤ N; ai ≠ bi).
Далее записано целое число M — количество запросов (1 ≤ M ≤ 500 000).
В следующих M строках идёт описание запросов. Каждый запрос содержится в отдельной строке и начинается с целого числа k, следом за которым идут k целых различных чисел vi — номера стран для удаления (1 ≤ k, vi ≤ N).
Гарантируется, что сумма всех k в одном тесте не превосходит 500 000.
Выходные данные
В выходной файл OUTPUT.TXT выведите M целых чисел — для каждого множества стран в отдельной строке выведите максимальный размер новой империи.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 14
1 2
1 3
2 6
2 7
3 4
3 5
6 8
8 9
8 10
7 11
7 12
7 13
12 14
4
1 2
3 1 7 8
4 2 3 8 12
4 9 10 14 5 | 5
3
3
10 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|