P15253 [NOSOI R1] Raining Mex

> Mex 不知道，但它在哭泣。

给定一个 $n$ 个点 $m$ 条边的无向连通图。每个点 $i$ 有一个权值 $w_i$。 定义一条从 $x$ 到 $y$ 的路径的权值如下： 1. 令路径上经过的所有点的权值构成一个可重集合 $S$（注意：即使路径重复经过同一个点，该点的权值在 $S$ 中只出现一次；但由于不同点可能具有相同权值，因此 $S$ 中可能包含重复元素）。 2. 考虑 $S$ 的所有子集（包括空集），每个子集的权值之和构成一个集合 $T$。例如 $S=\{1,2,3\}$ 则 $T=\{0,1,2,3,4,5,6\}$。 3. 该路径的权值定义为集合 $T$ 的 $\text{mex}$。一个集合的 $\text{mex}$ 是指该集合中未出现的最小自然数。例如 $\operatorname{mex}\{0,1,2,4\}=3$。 你需要处理 $q$ 个查询。每个查询给定两个整数 $x, y$。表示一次查询的起点和终点。 首先，你需要将原图的每条边定向，将原无向图转为有向图。对于一种定向方案，如果存在从 $x$ 到 $y$ 的路径（路径允许重复经过顶点和边），则定义该方案的权值为所有从 $x$ 到 $y$ 的路径的权值的最大值，你需要输出所有定向方案中权值的最大值。 **注意：对于每组查询，边定向是独立重新进行的**，即每次查询时你可以自由选择边的方向以最大化权值。

- 第一行包含两个整数 $n,m,sid$。分别表示点数，边数，子任务编号。 - 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$，表示每个点的权值。 - 接下来 $m$ 行，每行包含两个整数 $u, v$，表示一条连接点 $u$ 和点 $v$ 的边。 - 下一行包含一个整数 $q$，表示查询数量。 - 接下来 $q$ 行，每行包含两个整数 $x,y$，表示一个查询。

对于每个查询，输出一行一个整数，表示所有定向方案中权值的最大值。

#### 数据范围 **本题采用捆绑测试**。 |$\text{sid}$|$pts$|$n$|$m$|$q$|$w$|特殊性质| |--|--|--|--|--|--|--| |$1$|$5$|$\leq5$|$\leq 10$|$\leq 5$|$\leq 10$|无| |$2$|$10$|$\leq100$|$