每个冬天的间隔，LaLa 都会帮助她的姑姑 Aisha 收获 Biheiril 王国特有的农作物。
该农作物可以建模为一个图，其中边对应分支，顶点对应连接点，每个连接点 $u$ 上生长着美味度为 $T_u$ 的果实。
农作物的培育过程可分为三个阶段：
- 在第一阶段开始时，在开阔的田地上种下一颗种子。种子最终生长形成一个仙人掌图，即一个简单的连通图，其中每条边最多属于一个环。这是唯一会有新连接点生长的阶段。
- 考虑第一阶段生长出的仙人掌图的 DFS 树。在第二阶段开始时，Aisha 用一个环形框架包围农作物，将叶子（度数为 1 的顶点，仅计算 DFS 树中的边，可能包含 DFS 树的根）连接到环上。这迫使农作物生长出额外的分支，连接框架上的相邻连接点，形成一个环图，并开始生产果实。请阅读输入格式说明以获取详细描述。
- 在第三阶段开始时，Aisha 在框架上连接了一个魔法工具，为农作物提供持续的额外营养流。结果，一些新的分支生长出来。在此阶段生长出的分支的并集形成了一棵非常稠密的树：树中每个非叶子顶点的度数均 $\ge 12$。收获在这一阶段结束时开始。
LaLa 的目标是最大化她所收获果实的美味度之和。然而，LaLa 不允许收获两个相邻顶点上的果实，因为这会产生压力并杀死直接连接它们的树干。
编写一个程序，计算 LaLa 可以收获的果实集合，使其美味度之和最大。
输入格式
输入描述了农作物的状态，格式如下：
$N \ M$ $T_0 \ T_1 \ \dots \ T_{N-1}$ $u_0 \ v_0$ $u_1 \ v_1$ $\vdots$ $u_{M-1} \ v_{M-1}$ $K$ $x_0 \ y_0$ $x_1 \ y_1$ $\vdots$ $x_{K-1} \ y_{K-1}$
其中 $N$ 是连接点的数量，编号从 $0$ 到 $N-1$，$M$ 是第一阶段生长出的分支数量，第 $i$ 条分支连接连接点 $u_i$ 和 $v_i$（对于所有整数 $0 \le i < M$）。
考虑在第一阶段生长出的仙人掌图上构建的 DFS 树，其中 DFS 遍历从连接点 $0$ 开始，每个连接点的邻居顺序由输入顺序给出，即遍历优先考虑输入中较早出现的分支。注意，上述描述唯一确定了一个 DFS 遍历及其对应的 DFS 树。令 $c_0, \dots, c_{l-1}$ 为 DFS 序中所有在 DFS 树中度数为 1 的连接点组成的子序列。那么第二阶段生长出的环图由 $l$ 条边 $(c_0, c_1), \dots, (c_{l-1}, c_0)$ 定义。
此外，$K$ 是第三阶段生长出的分支数量，其中第 $i$ 条分支连接连接点 $x_i$ 和 $y_i$（对于所有整数 $0 \le i < K$）。
输入满足以下约束：
- 所有输入数字均为整数。
- $2 \le N \le 500, N - 1 \le M \le 2N, 1 \le K \le \min(N - 1, 100)$
- $1 \le T_u \le 200\,000$（对于所有整数 $0 \le u < N$）
- $0 \le u_i < v_i < N$（对于所有整数 $0 \le i < M$）
- $u_i \neq u_j$ 或 $v_i \neq v_j$（对于所有整数 $0 \le i < j < M$）
- $0 \le x_i < y_i < N$（对于所有整数 $0 \le i < K$）
- $x_i \neq x_j$ 或 $y_i \neq y_j$（对于所有整数 $0 \le i < j < K$）
- 边 $(u_i, v_i)$ 的并集在顶点 $\{0, 1, \dots, N-1\}$ 上形成一个仙人掌图。
- 边 $(x_i, y_i)$ 的并集在顶点 $\{x_0, y_0, x_1, y_1, \dots, x_{K-1}, y_{K-1}\}$ 上形成一棵树，其中每个度数大于 1 的顶点度数至少为 12。
输出格式
输出应按以下格式：
$W \ L$ $s_0 \ s_1 \ \dots \ s_{L-1}$
其中 $W$ 是 LaLa 在不伤害任何分支的情况下可以从农作物中收获的果实集合 $s = \{s_0, \dots, s_{L-1}\}$ 的最大美味度之和。
输出应满足以下约束：
- 所有输出数字均为整数。
- $0 \le L \le N$
- $0 \le s_0 < s_1 < \dots < s_{L-1} < N$
- 对于所有整数 $0 \le i < j < L$，不存在直接连接顶点 $s_i$ 和 $s_j$ 的边。
- $\sum_{i=0}^{L-1} T_{s_i} = W$
样例
样例 1
输入
6 7 1 1 1 1 1 1 0 1 1 2 2 3 2 4 1 5 1 4 0 5 1 2 5
输出
2 2 0 4
说明
下图说明了样例测试中描述的农作物。
- 常规黑色边表示第一阶段生长出的属于 DFS 树的分支。
- 虚线黑色边表示第一阶段生长出的不属于 DFS 树的分支。
- 红色边表示第二阶段生长出的分支。
- 蓝色边表示第三阶段生长出的分支。
注意，可能存在多条直接连接同一对连接点的分支。
