Arbore și subșir

Se dă un arbore cu $N$ noduri, și rădăcina în nodul $1$. Fiecărui nod $i$, îi este asociat un număr $a_i$. Pentru un arbore $T$ și un nod $u$ fie $v_1, v_2, \dots, v_k$, $v_1 = 1$, $v_k = u$ drumul de la rădăcină, până la nodul $u$ în arborele $T$. Pentru acest nod $u$, definim, cel mai lung subșir strict crescător până în $u$ în arborele $T$, ca fiind, oricare dintre cele mai lungi subșiruri strict crescătoare din șirul de numere: $a_{v_1}, a_{v_2}, \dots, a_{v_k}$.

Se dau $q$ interogări. Pentru a $i$-a intreogare, se dau $k_i$ de numere distincte, $u_1, \dots, u_{k_i}$, care reprezintă noduri în arborele inițial $T$. Fie arborele $T'$, componenta conexă care conține rădăcina, în urma eliminării nodurilor $u_1, \dots, u_k$ din arborele $T$. Pentru a $i$-a interogare, se cere să se afle: cea mai mare dintre lungimile celui mai lung subșir strict crescător până la oricare nod $v$ din $T'$.

Cerință

Să se determine, pentru fiecare interogare, cea mai mare dintre lungimile celui mai lung subșir strict crescător până la oricare nod $v$, din arborele $T'$ asociat interogării $i$.

Date de intrare

Fișierul de intrare arbsub.in conține pe prima linie numărul de noduri $N$, și numărul de interogări, $q$.

Pe următoarea linie, se află cele $N$ numere naturale, $a_i$, $a_i$ fiind ascoiat nodului $i$.

Pe următoarele $N - 1$ linii, se află câte 2 numere, $u_i$ și $v_i$, reprezentând muchiile arborelui.

Pe următoarele $q$ linii, se află informațiie aferente fiecărei interogări. Pe linia $N + 1 + i$, se află numărul $k$, urmat de $k$ numere: $u_1, \dots, u_k$, având semnificația din enunț. Se garantează că nodurile sunt distincte, nu conțin rădăcina arborelui și sunt numere întregi în intervalul $[2, N]$. De observat, că $k$ poate fi $0$.

Date de ieșire

Fișierul de ieșire arbsub.out va conține $q$ linii, linia $i$ conținând răspunsul pentru interogarea a $i$-a.

Restricții și precizări

• $1 \leq N \leq 3 \cdot 10^5$
• $1 \leq a_i \leq 10^9$
• $1 \leq q \leq 3 \cdot 10^5$
• $\sum{}{} k_i \leq 5 \cdot 10^5$

Exemplu

arbsub.in

12 4
2 3 3 4 6 3 5 3 5 7 7 8
6 4
7 4
4 8
1 2
2 4
5 2
10 12
5 10
11 9
9 5
3 1
3 5 6 8
4 9 11 12 10
4 2 4 10 12
0

arbsub.out

4
4
2
5