题目背景

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$，表示一个查询。

输出格式

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

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

18
3
3

见 ex_mex1.in/ans
这个样例满足 sub2 的约束条件

见 ex_mex2.in/ans
这个样例满足 sub3 的约束条件

见 ex_mex3.in/ans
这个样例满足 sub4 的约束条件

提示

数据范围

本题采用捆绑测试。

$\text{sid}$	$pts$	$n$	$m$	$q$	$w$	特殊性质
$1$	$5$	$\leq5$	$\leq 10$	$\leq 5$	$\leq 10$	无
$2$	$10$	$\leq100$	$<100$	$\leq 100$		$A$
$3$	$15$	$\leq 10^3$	$<10^3$	$\leq10^3$	$\leq 10^6$
$4$	$10$		$\leq 10^4$	$\leq 10^3$	$\leq10^6$	无
$5$		$\leq 10^5$	$\leq 10^6$	$\leq 10^5$	$\leq 1$
$6$	$15$	$\leq10^5$	$\leq10^6$		$\leq 10^5$	$B$
$7$		$\leq 10^5$	$\leq 10^6$		$\leq 10^6$	无
$8$	$20$	$\leq 2\times10^5$		$\leq2\times 10^5$

特殊性质 $A$：$n=m+1$。

特殊性质 $B$：所有输入的 $w_i$ 是 $n$ 的排列。

对于所有测试数据保证：

• $2 \le n \le 2\times 10^5$，
• $n-1 \le m \le 10^6$，
• $1 \le q \le 2\times10^5$，
• $1 \le u, v, x, y \le n$，
• $1 \le w_i \le 10^6$。

提示

• 图的连通性保证初始无向图是连通的，可能存在重边，自环。
• 本题输入数据较大，建议使用较快的读入方式。