Islands and Bridges

You are given a map of islands connected by bridges. A Hamilton path is a path that travels along the bridges and visits every island exactly once. Each island also carries a positive integer value. Among all Hamilton paths we look for the one that maximizes the score defined below; we call it the best triangular Hamilton path.

Suppose there are $n$ islands. For a Hamilton path $C_1 C_2 \ldots C_n$, let $V_i$ be the value of island $C_i$. The score of the path is the sum of three parts:

• First part: the sum of $V_i$ over every island on the path.
• Second part: for every consecutive pair $C_i C_{i+1}$ on the path, add the product $V_i \cdot V_{i+1}$.
• Third part: for every three consecutive islands $C_i C_{i+1} C_{i+2}$ that form a triangle on the map (that is, there is also a bridge directly between $C_i$ and $C_{i+2}$), add the product $V_i \cdot V_{i+1} \cdot V_{i+2}$.

Your first task is to report the maximum possible score. Because several different Hamilton paths may reach this maximum, your second task is to report how many best triangular Hamilton paths exist.

The first line contains an integer $q$ ($q \le 20$), the number of test cases. Each test case is given as follows:

• A line with two integers $n$ and $m$: the number of islands and the number of bridges. There are at most $13$ islands.
• A line with $n$ positive integers; the $i$-th of them is the value $V_i$ of island $i$. Each value is at most $100$.
• $m$ lines, each of the form x y, meaning there is a two-way bridge between island $x$ and island $y$. Islands are numbered from $1$ to $n$.

For each test case, print one line with two numbers separated by a space: first the maximum score of a best triangular Hamilton path, then the number of distinct best triangular Hamilton paths. If the map has no Hamilton path at all, print 0 0.

A path written in reverse order is considered the same path.