根据连接这些岛屿的岛屿和桥梁的地图，我们都知道，汉密尔顿路径是沿着桥梁的路径，这样它就可以访问每个岛屿一次。在我们的地图上，每个岛都有一个正整数值。如果汉密尔顿路径的最大值如下所述，我们称之为最佳三角形汉密尔顿路径。
假设有N个岛。汉密尔顿路径c1c2…cn的值计算为三部分之和。让vi成为ci岛的价值。作为第一部分，我们总结了路径中每个岛的所有vi值。在第二部分中，对于路径中的每个边缘cici+1，我们添加了产品vi*vi+1。第三部分，当路径中三个连续的岛屿ci ci+1ci+2在地图上形成一个三角形，即ci和ci+2之间有一座桥梁时，我们加上产品vi*vi+1*vi+2。
最有可能但不一定的是，您将要找到的最佳三角形Hamilton路径包含许多三角形。很可能有不止一个最佳的三角形Hamilton路径；您的第二个任务是找到这些路径的数量。

输入文件在第一行以一个数字Q（Q<=20）开头，这是测试用例的数量。每个测试用例以一条包含两个整数n和m的行开始，这两个整数分别是图中的岛数和桥数。下一行包含n个正整数，第i个数字是i岛的vi值，每个值不超过100。以下M线的形式为X Y，表示X岛和Y岛之间有一座（双向）桥。岛屿编号从1到N。您可以假设不超过13个岛屿。

对于每个测试用例，输出一行两个数字，用空格分隔。第一个数字是最佳三角形Hamilton路径的最大值；第二个数字应该是不同最佳三角形Hamilton路径的数量。如果测试用例不包含Hamilton路径，则输出必须为“0 0”。


注意：路径可以按相反的顺序写下来。我们仍然认为这是同一条路。

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

状态压缩DP