9581: 能量网络

在遥远的星系深处，宇宙探索舰队"星际先锋"正筹划构建覆盖整个星域的超级能量网络。目前，第一阶段已初见成效：部分星球之间已经架设了"能量光束"。每束能量光束连接两个不同的星球，并基于量子纠缠效应实现能量瞬时传输。注意，每对星球之间最多架设一束能量光束，且星球不会与自身连接。 接下来，舰队计划构建"能量网络组"。首先，任意两束能量光束之间都可以建立一个网络组；随后，任何两个共享公共能量光束的网络组均可合并。举例来说，若星球A与星球B之间有能量光束AB，星球C与星球D之间有能量光束CD，星球E与星球F之间有能量光束EF，则可以先构建网络组AB-CD和网络组CD-EF，再将二者合并，最终形成包含三束能量光束AB,CD,EF的整体能量网络组AB-CD-EF。 构建网络组需要消耗能量成本。以构建网络组AB-CD为例，其成本计算公式为min{|xA+xB-xC-xD|,|yA+yB-yC-yD|,|zA+zB-zC-zD|},其中星球A的空间坐标为(xA,yA,zA)，其余星球的坐标依此类推。不过，网络组之间的合并不需要额外成本。现已知每个星球在空间中的坐标，以及已架设能量光束的星球对（星球编号均取自集合{1,2,...,n}），请计算以最小能量成本使所有能量光束均纳入同一能量网络组中的方案。舰队保证该方案一定存在。

多组测试数据。第一行是一个整数T，表示测试数据组数。满足1≤T≤5。 对于每组测试数据，输入格式如下： 第一行包含三个以空格分隔的整数n,m，其中n表示星球总数，m表示已架设能量光束的总数。 对于i=1,…,n，第i+1行包含三个整数xi,yi,zi，表示编号为i的星球在空间中的坐标。任意两个不同星球的坐标均不相同。 对于j=1,…,m，第j+n+1行包含集合{1,2,…,n}中的两个不同整数，表示第j束能量光束连接的两个星球的编号。 数据范围保证1≤n≤10^5、1≤m≤10^5、且对任意i有|xi|,|yi|,|zi|≤10^7，并且保证存在满足要求的方案。另外，保证所有测试数据组中的n的总和不超过2×10^5，m的总和不超过2×10^5。

对于每组测试数据，输出一行，包含一个整数，表示使所有能量光束均纳入同一能量网络组中的最小总能量成本。

构建网络组12-13（即连接能量光束12与光束13的网络组）的成本为2；构建网络组12-23的成本为0；构建网络组13-23的成本为1。因此，通过构建网络组12-23和网络组13-23可以使所有能量光束均纳入同一能量网络组中，总能量成本为1。