题目描述

在时空中有 $n$ 个时空节点，有 $n-1$ 条时空通道将所有时空节点连接成一个连通块，每条时空通道连接着两个时空节点。

你初始在 $1$ 号时空节点，你每次可以选择一条时空通道来穿梭到另一个时空节点，由于时空穿梭的特殊性，每条时空通道至多通过一次。

每个时空节点有一个风景，第 $i$ 个时空节点的风景为 $a_i$。一段风景序列由若干个风景构成，一个长度为 $k$ 的风景序列为 $a_{i_1}a_{i_2}\dots a_{i_k}$。你可以通过若干次时空穿梭经过若干时空节点，这些时空节点按照经过顺序构成了一个风景序列，记这个风景序列为重现的风景。

定义一个风景序列 A 在风景序列 B 中的出现次数为：最多将风景序列 B 分为多少个连续且不相交的部分，使得风景序列 A 是每个部分的子串。

你有 $q$ 段留恋的风景，每段留恋的风景是一个风景序列，记第 $i$ 段留恋的风景为 $s_i$，其长度为 $m_i$，记 $s_i$ 中的第 $j$ 个风景为 $s_{i,j}$。对于每段留恋的风景，你都需要从 $1$ 号时空节点出发进行时空穿梭，得到重现的风景，你需要求出该留恋的风景在重现的风景中的出现次数的最大值。

注：

• 每段留恋的风景所对应的重现的风景相互独立。
• 原序列中任意个连续的数字组成的序列称为该序列的子串。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行 $2$ 个正整数 $n,q$。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示 $u$ 和 $v$ 之间存在一条时空通道。

接下来 $q$ 行，每行先输入一个正整数 $m_i$，然后输入 $m_i$ 个正整数，表示 $s_i$。

输出格式

对于每组数据：

输出 $q$ 行，表示每段留恋的风景对应的答案。

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

3
1
2
1
1
1
0
1
1
0

提示

$1\le T\le10^5$，$1\le n,q,m_i\le10^5$，$1\le a_i,s_{i,j},u,v\le n$，$\sum n,\sum q,\sum m_i\le10^5$。

注意本题不寻常的时空限制。