#2481. Pku3164 Command Network

题目描述

MST（最小生成树）：对于无向带权图<V，E>，若其导出子图的边权和最小，且原图V中对应的任意两个顶点间有且仅有一条通路，则称此图为原图的MST。

你的任务很简单，对于给定的有向带权图，求出其"最小生成树"，即指定一个根以后，每个点都是从根出发可达的。

输入格式

输入文件最多包含3组测试数据，对于每组测试数据：

第一行为两个数n,m，表示有向带权图的顶点数和边数，点编号为1~n。

接下来n行，每行两个整数X_i,Y_i，表示i个顶点在直角坐标系中的坐标。

接下来m行，每行两个正整数x,y，表示存在一条由点x指向点y的有向边，边权为两顶点的曼哈顿距离（定义见下）。

输出格式

对于每组测试数据，输出一行：

如果不存在"最小生成树"，输出"Poor"；

否则输出最小边权和。

样例

样例输入

    3 3  

    0 0  

    1 0  

    2 0  

    1 2  

    1 3  

    2 3  

    3 2  

    0 0  

    1 0  

    2 0  

    1 2  

    3 2  

样例输出

2  

Poor  

数据范围与提示

100%的数据，n≤1000，m≤n*n，0≤X_i,Y_i≤10000。  

可能存在自环。  

【温馨提示】

对于两个点(a,b)，(c,d)，它们的曼哈顿距离定义如下：

l=|a-c|+|b-d|