Description

无向图G每个点都有一个权值，规定每条边的权值是连接的两个点的权值Xor。

给出该无向图G和某些点的权值，其他点的权值可以随意规定，要求使得所有边权和最小，求该最小边权和。

Format

Input

第一行一个整数T，表示测试数据组数

对于每组测试数据：

第一行两个整数n，m表示点的个数和图中无向边的个数。

接下来m行，每行两个整数，表示一条边

下面一行一个整数k，表示权值已知点个数

接下来k行每行两个整数表示点的编号和点的权值

Output

对于每组测试数据输出一行，包含一个整数表示最小边权和。

Samples

2
3 2
1 2
2 3
2
1 5
3 100
3 2
1 2
2 3
2
1 5
3 100

97
97

[数据约定] 1<=T<=10,0<N<=500,0<=M<=3000, 点的权值均小于longint