Pku3164 Command Network

给定一个有向带权图。以顶点 $1$ 为根，选择若干条有向边，使得图中每个顶点都能从根出发到达，并且所选边的权值之和最小。这样的子图称为该有向图的最小生成树。

每条边的权值为其两个端点之间的曼哈顿距离。对于坐标分别为 $(a,b)$ 和 $(c,d)$ 的两个顶点，它们之间的曼哈顿距离为：

$$|a-c|+|b-d|$$

请计算最小生成树的边权和。如果不存在满足条件的最小生成树，则输出 Poor。

输入格式

输入包含不超过 $3$ 组测试数据，每组测试数据的格式如下：

第一行包含两个整数 $n,m$，分别表示有向图的顶点数和边数。顶点编号为 $1\sim n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $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

样例输出

2
Poor

数据范围

• $n\le 1000$；
• $m\le n\times n$；
• $0\le X_i,Y_i\le 10000$；
• 图中可能存在自环；
• 输入包含不超过 $3$ 组测试数据。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 3
    0 0
    1 0
    2 0
    1 2
    1 3
    2 3
    3 2
    0 0
    1 0
    2 0
    1 2

输出

2
Poor