给定一个地图，地图中包含很多岛和连接它们的桥。

汉密尔顿路径是指沿着桥访问每个岛屿恰好一次的路径。

在我们的地图上的每个岛都具有一个权值，它是一个正整数。

假设一共有 $n$ 个岛，第 $i$ 个岛的权值为$V\_i$。

现在规定一个汉密尔顿路径的总价值为以下三个价值的和：

1. 每个岛屿的权值之和。
2. 汉密尔顿路径中，每一条边连接的相邻岛屿的权值乘积之和。
3. 如果在汉密尔顿路径中存在相邻的三个岛屿可以构成环形，则将所有满足条件的相邻岛屿三元组权值的乘积相加求和。

任务一：请你找出汉密尔顿路径的总价值最大可以为多少。

任务二：请你找出满足最大总价值的汉密尔顿路径共有多少条。

输入格式

第一行包含整数 $q$，表示共有 $q$ 组测试数据。

每组数据第一行包含两个整数 $n,m$，分别表示小岛数和桥数。

第二行包含 $n$ 个不超过 $100$ 的正整数，表示每个岛屿的权值。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示岛 $a$ 和岛 $b$ 之间存在一个双向桥。

岛屿的编号从 $1$ 到 $n$。

输出格式

每组数据输出一行，两个整数，分别表示汉密尔顿路径的最大总价值，以及满足最大总价值的汉密尔顿路径条数。

如果不存在汉密尔顿路径，则输出 0 0。

注意：将一条路径按相反的顺序输出而成的路径，视为与原路径是同一条路径。例如 1-2-3 和 3-2-1 为同一条路径。

数据范围

$2 \le n \le 13$,

$1 \le m \le \frac{n(n-1)}{2}$,

$1 \le a,b \le n$,

$a \neq b$。

任意两岛之间最多存在一个桥直接连接它们。

样例

2
3 3
2 2 2
1 2
2 3
3 1
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

22 3
69 1