Description

旅游公司展示了一种新型DIY线路。各线 路都包含一些可由游客自己选择的城市。根据该公司的统计数据，每个城市都有自己的评分，评分越高越有趣。例如，巴黎的评分是$90$，纽约的评分是$70$，等等。世界上不是任何两个城市之间都可以直飞的，因此旅游公司提供了一张地图，告诉游客是否可以在地图上任意两个城市之间直飞。在地图上用一个数字标记每个城市，一个数字较大的城市不能直接飞往数字较小的城市。薇薇从杭州出发（杭州是第1个城市，也是最后1个城市，所以杭州被标记为$1$和$N +1$），它的评分为$0$。薇薇希望尽可能地让游览变得有趣。

Format

Input

第1行是整数$T$ ，表示测试用例数。每个测试用例的第1行都是一个整数$N （2≤N ≤100）$，表示城市数。然后是N 个整数，表示城市的评分。接着是整数M ，后跟M 对整数$A_i$ 、$B_i$ $（1≤i ≤M ）$，表示从城市$Ai$可以直飞到城市$B_i$。

Output

对于每个测试用例，都单行输出评分之和的最大值和最佳DIY线路。在测试用例之间都输出一个空行。

Samples

2
3
0 70 90
4
1 2
1 3
2 4
3 4
3
0 90 70
4
1 2
1 3
2 4
3 4

CASE 1#
points : 90
circuit : 1->3->1

CASE 2#
points : 90
circuit : 1->2->1

`

来源

HDU1224