话说上一集，大Home_W成功一波操作，奠定了拯救世界的胜局，
回到自己的时间线后，大魔王直接就把小晋扔回去了奇怪的世界，并准备打一个响指让世界恢复原样，
当然了更重要的是让自己富可敌国的商业财团也恢复啦
小A一脸焦急的跟大魔王说道：“快点操作啊，打响指了”
大魔王：“知道啦，这不是准备着吗，总得等战衣冷却一点，不然这一个响指下去，我不得跟着斯塔克一起下棋去了”
小A：“……，你顶不住？那为什么小晋那么猛？打了响指都没事”
大魔王：“可能是蛤蟆天生皮厚？有时间拿他做做实验”
啪
看着大魔王打了响指，小A立刻拿起了手机打给小C
“不对劲啊，我战衣都没有发热”
小A:“???”
小A看着响了n声之后没有人接听的手机，脸色立刻阴沉了下来
愤怒的看着大魔王，大魔王被他盯着冷汗都流了一地
大魔王：“这……我也不知道啊，你看我，我的钱也没有回来啊”
赛文斯：“难道是手套坏了？”
金金金：“不应该啊，难道是小晋动了手脚”
众人刚准备动身去找小晋，突然感觉一个天旋地转，
来到了一个世界当中
小A看着眼前的这个世界，突然感觉有点眼熟：“这难道是去年的那个有灰常多个传送阵的时间？”
大魔王：“那是啥东西？我刚才感受到了是原石送我们来到这个世界的”
大魔王沉下心来静静的感受了原石，说道：“知道了，原来是小晋本来难道将原石摧毁，没想到我们那么快就拿到了手套”
“这个世界上就是原石内部，有n个传送阵，和m对需要创建连接的路径。创建路径的损耗是所连接的两个传送阵的魔法值的异或值。
我可以通过原石知道其中k个点的魔法值，我们可以决定剩下点的魔法值使得最终连接路径的损耗最低，将损耗最低我们就可以用剩下的损耗值去恢复世界（输出这个最低值。）”
小A：“懂了，立刻算”
小A还有四大天王立刻通过交互信息，几分钟后就心算出了答案，
“行，那我们立刻出去”，大魔王立刻操控原石将众人传送出去，
站在城堡面前，大魔王打了响指，然后立刻将手套脱下，扔向了城堡，然后乘着飞机离开了城堡
坐在飞机上，看着远处蘑菇云。小A叹了一口气
突然一阵震动，小A掏出了手机，正是复活的小C打来的电话
输入一个T,表示T组测试案例(约10组)
对于每组测试案例输入n(5<=n<=300),m(1<=m<=3000)表示n个魔法阵，和m对需要连接的魔法阵
接下来m行,每行两个数字u, v (u != v 且 1 <= u,v <= n, 数据保证不重复)
接下来一个数字k(1 <= k <= n) 表示已知k个魔法阵的魔法值
接下来k行每行两个数字u, w (1 <= u <= n, 1 <= w <= 2^31)
表示点的编号，和魔法值的大小
对于每组测试案例，输出答案。
1 3 2 1 2 2 3 2 1 5 3 100
97