You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

给定一棵根为 1 的，包含 $n$ 个点的树。其中第 $𝑖$ 个点的权值为 $𝑎_𝑖$，$𝑑fs$ 序为 $𝑑fn_𝑖$。

现在你需要在这棵树上找到一个连通块，连通块需要满足题目给定的 $𝑚$ 个限制，每个限制用两个正整数 $𝑢$, $𝑣$ 描述。要么$𝑢$, $𝑣$ 不同时存在于这个连通块中，要么 $𝑢$, $𝑣$ 在这个连通块上的$𝑑fs$序相邻。请在这棵树上找到满足题目限制条件的权值之和最大的连通块。

备注 1：

一个结点可能有多个孩子结点，这些孩子是有$𝑑fs$的先后顺序的，$𝑑fs$顺序就是题目输入的顺序。

备注 2：

连通块的 $𝑑fs$序的定义：找到连通块在原树上深度最小的点开始$𝑑fs$，然后仍然根据题目读入的顺序获取每个点的 $𝑑fs$顺序。

【输入格式】

第一行包含两个正整数 $𝑛$, $𝑚$，表示结点的个数和限制的个数；

第二行包含 $𝑛$ 个整数，第 $𝑖$ 个整数为第 $𝑖$ 个结点的权值 $𝑣𝑎l_𝑖(−10^9 \le 𝑣𝑎l_𝑖 \le 10^9)$

接下来的 $𝑛$ 行里，第 $𝑖$ 行的第一个数字为一个非负整数 $s_𝑖$，表示第 $𝑖$ 个结点的孩子个数，然后给出 $s_i$ 个正整数按顺序表示它的所有孩子编号。

接下来的 $𝑚$ 行，每行给出两个正整数 $𝑢$, $𝑣(1 \le 𝑢, 𝑣 \le 𝑛)$ 描述一个约束，表示最终的连通块中 $𝑢$, $𝑣$ 的 $𝑑fs$序不能相邻。

【输出格式】

输出一行一个整数表示答案。

【样例 1 输入】

6 3
2 2 1 3 2 5
2 2 6
3 3 4 5
0
0
0
0
3 4
5 6
2 6

【样例 1 输出】

12