黑白边游戏

Problem Description

小Q和小T在一张 $n$ 个点的完全无向图上玩游戏。在游戏的一开始，图中所有边都是黑色。他们会轮流操作 $m$ ($m\bmod 2=0$) 轮，小Q先手，即小Q将操作第 $1,3,5,\dots,m-1$ 轮，小T将操作第 $2,4,6,\dots,m$ 轮。每轮的操作方需要在图中选择恰好一条边，将其颜色进行反转，即由黑变白或者由白变黑，然后操作方将获得 $\sum_{i=1}^n\sum_{j=1}^n dis(i,j)$ 点得分，其中 $d i s ( i , j )$ 表示点 $i$ 到点 $j$ 的最短路径的长度。在所有 $m$ 轮操作结束之后，谁总分高谁就获胜。 在第 $i$ 轮中，每条黑边的长度都为 $a_i$，每条白边的长度都为 $b_i$。小Q和小T双方都知道所有 $m$ 轮的 $a,b$ 数据，且他们都会以最优策略进行操作，目标是让自己的总分减去对手的总分尽可能大。作为观战方的你，能否写一个程序预测最后双方的分差？

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 50$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($2\leq n\leq 8$, $2\leq m\leq 300$, $m\bmod 2=0$)，分别表示图中的点数以及游戏的轮数。 接下来 $m$ 行，每行两个正整数 $a_i,b_i$ ($1\leq a_i,b_i\leq 5$)，依次表示每轮中黑边和白边的长度。 输入数据保证 $\sum m\leq 2000$。

Output

对于每组数据输出一行一个整数，即最后小Q的总分减去小T的总分的值。

Sample Input

2
2 4
1 2
3 1
5 3
2 5
5 4
1 1
2 2
3 5
5 2

Sample Output

0
-56

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）