题目描述

一轮正在玩空洞骑士，他现在在速通苦痛之路，里面有 $n$ 个点，编号从 $1$ 到 $n$，$m$ 条双向路径，但是里面的每条路径上都有锋利的电锯阻挡他过去。

幸好，这些电锯不会一直不变，它们是有规律的运转的，每个点都会有一个对应的整数时机 $d$，若当前秒是 $d$ 的倍数时(不包括 $0$)，其他与该点直接连接的点都可以耗费 $1$ 秒到达此点。

现在，一轮想知道开始时间为 $0$ 秒时，他从 $u$ 点到 $v$ 点的最小耗时秒。他总共会提出 $q$ 次询问，所以你要告诉他 $q$ 次最小耗时秒。

输入格式

第一行三个整数，分别是 $n,m,q$。

第二行包含 $n$ 个整数 $d_1,d_2,d_3……d_n$，表示每个点的时机。

接下来 $m$ 行，每行包含两个正整数 $a$ 和 $b$，表示点 $a$ 和点 $b$ 有一条路径相连，保证没有重边和自环。

接下来 $q$ 行，每行包含两个正整数 $u$ 和 $v$，询问点 $u$ 到点 $v$ 的最小耗时秒。

输出格式

共 $q$ 行，每行输出对应答案，表示最小耗时秒，如果到达不了则输出 -1。

3 2 1
3 4 5
1 2
2 3
1 3

6

解释 #1

点 1 到点 2 耗时 5 秒，到点 3 又耗时 1 秒，总共 6 秒。

数据范围

$2 \le n \le 150,1 \le m \le n(n-1)/2,1 \le q \le 2*10^5$。

$1 \le a,b,u,v \le n,1 \le d \le 10^9$。