시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 0 0 0 0.000%

문제

Zadano je stablo: neusmjeren i povezan graf s n vrhova i n − 1 bridova. Vrhovi su označeni brojevima 1, 2, . . . , n.

Zadano je q upita. U svakom upitu odabiremo neki podskup vrhova stabla P = {v1, v2, . . . , vk} i pitamo koliko se bridova nalazi u najmanjem razapinjujućem stablu skupa P? Drugim riječima, koliko bridova pripada barem jednom putu između nekih vrhova skupa P? Pronadite odgovore na sve upite.

입력

U prvom redu nalazi se prirodan broj n (2 ≤ n ≤ 1 000 000), broj vrhova stabla. U svakom od sljedećih n − 1 redova nalaze se dva različita prirodna broja a, b (1 ≤ a, b ≤ n) koji označavaju da su vrhovi a i b povezani bridom.

U sljedećem redu nalazi se prirodan broj q (1 ≤ q ≤ 60 000), broj upita. U svakom od sljedećih q redova nalazi se najprije prirodan broj k (k ≥ 2), veličina skupa, a potom k različitih prirodnih brojeva između 1 i n koji predstavljaju vrhove skupa iz teksta zadatka. Zbroj veličina k za sve upite bit će najviše 300 000.

출력

Za svaki upit u zaseban redak ispišite traženi broj bridova.

예제 입력 1

5
1 2
2 3
3 4
4 5
4
2 1 2
2 3 5
2 1 5
3 1 3 5

예제 출력 1

1
2
4
4

예제 입력 2

10
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
5
2 4 5
3 4 5 6
4 2 4 7 10
4 4 5 9 10
9 1 2 3 5 6 7 8 9 10

예제 출력 2

2
5
7
9
8