该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五 十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长 跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。 　　
为了让同学们更好地监督自己，学校推行了刷卡机制。 　　
学校中有n个地点，用1到n的整数表示，每个地点设有若干个刷卡机，且两个地 点之间有跑道相连接。 进行了一次长跑。问一个同学从A出发，最后到达B最多可以刷卡多少次。具体 的要求如下：

当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡 机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。

为了安全起见，每条跑道都需要设定一个方向（每次询问相互独立），这条跑 道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按 照任意路径从A地点到B地点能刷卡的最多次数。
【输入格式】
输入文件名为running.in 第一行两个整数n，m，q表示n个地点和m条跑道有q组询问。 第二行n个数分别表示n个地点的刷卡机个数 然后m行每行两个数a b表示a b两地点之间有一条跑道 然后q行每行两个数A B表示询问从A到B的最多刷卡次数
【输出格式】
输出文件名为running.out Q行，每行一个数表示最多刷卡次数
【样例输入】
3 3 3
1 2 3
1 2
1 3
2 3
1 2
1 3
2 3

【样例输出】
6
6
6
【样例解释】
将图的边按如图所示的方法就可以走过所有的点

【数据范围与约定】
30%的数据满足n，m，q<=13
另20%的数据满足m=n-1， n，m,q<=10^5
100%的数据满足n,q<=10^5 m<=5*10^5
100%的数据满足图联通