删边游戏
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一个游戏，你需要在一张无向连通图中删除某一条边。这张图由n个结点组成，由m条道路连接，并且每一个结点都有一个价值v_i。

在这个游戏中，你只能删除恰好一条道路，这也就意味着你不能一条道路都不删除，也不能删除大于等于两条道路，显然，你有总共m种选择。

假设你选择连接结点x和y的边进行删除，那么你在本次游戏的得分就是删除这条边之后，结点x所在的连通块的结点价值之和与结点y所在的连通块的结点价值之和的乘积。

现在，你需要求出，你在这个游戏中可能得到的最低得分和最高得分分别是多少。

输入描述:

输入的第一行包含一个整数 t(1 \leq t \leq 10)表示测试用例的数量。然后是测试用例的描述：
第一行包含两个整数 n 和 m (2 \leq n \leq 10^5,1 \leq m \leq 2 \cdot 10^5)。
第二行包含 n 个整数 v_i (1 \leq v_i \leq 10 ^ 4)，表示每个结点的价值。
接下来的 m行，每行包含两个整数 x 和 y，表示结点 x 和 y 之间有一条道路连接。
数据保证每对结点之间最多只有一条道路连接，没有任何一条道路连接同一个结点。

输出描述:

对于每组测试用例，输出一行用一个空格分隔开的两个整数，分别表示最低得分和最高得分。
示例1

输入

复制 
2
3 3
1 2 3
1 2
2 3
1 3
4 4
1 2 3 4
1 2
2 3
1 3
1 4

输出

复制 
36 36
24 100