섬과 다리

다리로 연결된 섬들의 지도가 주어집니다. 해밀턴 경로는 다리를 따라 이동하면서 모든 섬을 정확히 한 번씩 방문하는 경로입니다. 각 섬에는 양의 정수 값이 하나씩 붙어 있습니다. 모든 해밀턴 경로 중에서 아래에 정의된 점수를 최대로 만드는 경로를 찾으며, 이런 경로를 최적 삼각 해밀턴 경로라고 부릅니다.

섬이 $n$개 있다고 합시다. 해밀턴 경로 $C_1 C_2 \ldots C_n$에 대해 $V_i$를 섬 $C_i$의 값이라 하면, 이 경로의 점수는 다음 세 부분의 합입니다.

• 첫째 부분: 경로 위의 모든 섬에 대한 $V_i$의 합.
• 둘째 부분: 경로에서 이웃한 모든 쌍 $C_i C_{i+1}$에 대해 곱 $V_i \cdot V_{i+1}$을 더합니다.
• 셋째 부분: 경로에서 연속한 세 섬 $C_i C_{i+1} C_{i+2}$가 지도 위에서 삼각형을 이루면(즉 $C_i$와 $C_{i+2}$ 사이에도 다리가 있으면) 곱 $V_i \cdot V_{i+1} \cdot V_{i+2}$을 더합니다.

첫 번째로 가능한 최대 점수를 구하세요. 이 최댓값에 도달하는 해밀턴 경로가 여러 개일 수 있으므로, 두 번째로 최적 삼각 해밀턴 경로가 몇 개인지도 구하세요.

첫 줄에 테스트 케이스의 수 $q$ ($q \le 20$)가 주어집니다. 각 테스트 케이스는 다음과 같이 주어집니다.

• 섬의 수 $n$과 다리의 수 $m$이 공백으로 구분되어 한 줄에 주어집니다. 섬은 최대 $13$개입니다.
• 다음 줄에 $n$개의 양의 정수가 주어지며, $i$번째 수는 섬 $i$의 값 $V_i$입니다. 각 값은 $100$ 이하입니다.
• 이어서 $m$개의 줄에 각각 x y가 주어지며, 섬 $x$와 섬 $y$ 사이에 양방향 다리가 있음을 뜻합니다. 섬은 $1$번부터 $n$번까지 번호가 매겨집니다.

각 테스트 케이스마다 두 수를 공백으로 구분하여 한 줄에 출력합니다. 첫 번째 수는 최적 삼각 해밀턴 경로의 최대 점수이고, 두 번째 수는 서로 다른 최적 삼각 해밀턴 경로의 개수입니다. 지도에 해밀턴 경로가 하나도 없으면 0 0을 출력합니다.

경로를 거꾸로 뒤집어 쓴 것은 같은 경로로 봅니다.