OI题库

【问题描述】

虫族已经消灭了神族。邪恶的虫族还想消灭人族，于是又向人族发起了战争。经过激烈的战斗，人族凭着团结的精神，视死如归的斗志把虫族打得落花流水。然而事情还没结束，虫族是天生邪恶的，一有机会它们便要消灭人族，为了人族子孙后代的幸福，人族不能放过余下的虫族，一只也不能放过!
当时战斗形势是：所有余下虫族集中在一个星球上，虫族也意识到它们不是顽抗的时候，逃跑是它们惟一的出路，而且为了能有所生还，它们会分散的逃跑，但人族早有准备，军师派出多名探子，探出虫族逃跑的所有可能经过的路线，派兵在其中若干条路上等待并消灭虫族。
虫族所在星球编号为0，另外还有N个星球，分别编号为1，2，…，N-1，N。建立一个原点在0号星球的三维坐标系，另N个星球的坐标为(Xi，Yi，Zi)，i=1，2，…，N-1，N。虫族已经建立了在这(N+1)个星球之间的交通设备，具体地说，有某种不明交通工具M架，每架能且只能连接两个不同的星球，使虫族能从连接的两个星球中的任一个到达另一个。探子已经探出这M架交通工具连接的星球对。
军师要派兵在若干个虫族的通路中埋伏，使所有虫无路可逃，但是要在某条通路中埋伏，派兵的数目等于该通路连接的两个星球的距离的平方，军师希望用最少的兵力达到不让一只虫逃掉的目的，你要帮他算算最少用兵数目。军师指出，若有某一只虫能逃离星球0到达另一个星球i，并且星球i与星球0的距离大于R，则该虫就逃掉了，那时它能用某种不明方法逃到很远很远的地方，然后重新繁衍出虫族，再来消灭人族，这正是人族要避免的。注意人族可以派兵埋伏于与星球O距离大于R的地方。

【输入格式】

输入格式(输入文件名starwar.in)
N M R
X₁ Y₁ Z₁
X₂ Y₂ Z₂
......
X_N Y_N Z_N
T_1a T_1b
T_2a T_2b
......
T_ma T_mb
以上的输入均为整数，同行整数用1个或多个空格隔开。
第1行中N(1≤N≤50)为除星球0外的星球数；M(0≤M≤N(N+1)/2)为虫族交通工具数目，R(1≤R≤10000)为虫族逃离界限，意义见上。
接下来的N行中(Xi，Yi,Zi)分别描述星球i的坐标，i=1，2，…，N-1，N。(-1000≤Xi,Yi,Zi≤1000)
再往下M行中T_ia，T_ib 分别描述第i个交通工具连接的两个星球。0≤T_ia，T_ib≤N且T_ia≠T_ib，并且若TiaTib出现了，以后就不会再出现T_iaT_ib或T_ibT_ia，既每对点最多出现一次。

【输出格式】

输出格式(输出文件名starwar.out)
仅一个整数，即所用的最少用兵数。

【输入输出样例1】
输入(starwar.in)
1 1 2
1 1 1
0 1
输出(starwar.out)
0

【输入输出样例2】

输入(starwar.in)
1 1 1
1 1 1
0 1

输出(starwar.out)
3