题目描述

给定一个由岛屿和连接岛屿的桥梁组成的地图，哈密顿路径是指沿着桥梁访问每个岛屿恰好一次的路径。地图中每个岛屿都有一个正整数值。我们称一条哈密顿路径为最佳三角形哈密顿路径，当且仅当它能最大化以下描述的值：

假设存在$n$个岛屿，哈密顿路径$C_1C_2\ldots C_n$的价值由三部分组成：

1. 路径中每个岛屿的价值之和，即$\sum_{i=1}^n V_i$，其中$V_i$为岛屿$C_i$的价值。
2. 对于路径中的每条边$C_iC_{i+1}$，加上$V_i \times V_{i+1}$的乘积。
3. 当路径中连续三个岛屿$C_iC_{i+1}C_{i+2}$在地图中构成三角形（即$C_i$和$C_{i+2}$之间有桥梁）时，加上$V_i \times V_{i+1} \times V_{i+2}$的乘积。

你需要找到价值最大的最佳三角形哈密顿路径，并统计其数量。注意，路径的逆序视为同一条路径。若不存在哈密顿路径，输出`0 0'。

输入格式

• 第一行包含一个整数$q$（$q \leq 20$），表示测试用例数量。
• 每个测试用例以两个整数$n$和$m$开头，分别表示岛屿数和桥梁数。
• 接下来一行包含$n$个正整数，第$i$个数为岛屿$i$的价值$V_i$（$V_i \leq 100$）。
• 后续$m$行每行包含两个整数$x$和$y$，表示岛屿$x$和$y$之间有双向桥梁。岛屿编号从1到$n$，且$n \leq 13$。

输出格式

• 对每个测试用例，输出一行两个整数，用空格分隔。第一个数是最佳三角形哈密顿路径的最大价值，第二个数是该价值的路径数量。若无哈密顿路径，输出'0 0'。

输入样例 1

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

输出样例 1

22 3
69 1

来源

上海2004年相关问题