二维旅行

题目描述

Piggy生活在一个无限的平面上，平面上设有笛卡尔坐标系。

平面上有$n$个城市，编号为$1$到$n$，前$k$个城市被定义为大城市。第$i$个城市的坐标是$(x_i,y_i)$。

作为一名经验丰富的旅行者，Piggy在中考之后希望享受一段放松的旅行。现在，他在城市$a$，他希望乘飞机前往城市$b$。他可以在任何两个城市之间飞行，并且可以以任何顺序访问多个城市，但最后的目的地必须是城市$b$。

由于大城市之间的贸易活跃，因此可以免费乘飞机在它们之间旅行。具体来说，两个城市$i$和$j$之间的机票价格$f(i,j)$定义如下：

$$f(i,j)= \begin{cases} 0, & \text{如果城市 }i \text{ 和 }j \text{ 都是大城市} \\ |x_i-x_j|+|y_i-y_j|, & \text{其他情况} \end{cases}$$

Piggy不在乎节省时间，但他希望节省金钱。所以你需要告诉他如果他可以选择任意数量的航班，所有机票总价格的最小值是多少。

输入格式

输入的第一行包含一个整数$t$($1 \le t \le 10^4$) - 测试用例的数量。以下是测试用例的描述。

每个测试用例的第一行包含4个整数$n$、$k$、$a$和$b$($2 \le n \le 2 \cdot 10^5， 0 \le k \le n， 1 \le a, b \le n， a \ne b$) - 表示城市的数量、大城市的数量，以及起始和终点城市的编号。

然后接下来的$n$行，第$i$行包含两个整数$x_i$和$y_i$($-10^9 \le x_i, y_i \le 10^9$) - 第$i$个城市的坐标。前$k$行描述大城市。保证所有的坐标都是两两不同的。

保证所有测试用例总城市数量之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 - 所有机票的总价格的最小值。

示例 #1

示例输入 #1

5
6 2 3 5
0 0
1 -2
-2 1
-1 3
2 -2
-3 -3
2 0 1 2
-1000000000 -1000000000
1000000000 1000000000
7 5 4 2
154 147
-154 -147
123 456
20 23
43 20
998 244
353 100
3 1 3 1
0 10
1 20
2 30
4 3 2 4
0 0
-100 100
-1 -1
-1 0

示例输出 #1

4
4000000000
0
22
1

提示

在第一个测试用例中:

大城市被标记为红色。选择航班的最佳方式是: $3\rightarrow 1 \rightarrow 2 \rightarrow 5$，这将花费$3+0+1=4$。注意，航班$1\rightarrow 2$的费用是$0$，因为城市$1$和$2$都是大城市。

在第二个测试用例中，由于只有$2$个城市，唯一的方式就是从城市$1$飞往城市$2$。

在第三个测试用例中，由于城市$2$和$4$都是大城市，Piggy可以直接从城市$2$飞往城市$4$，花费为$0$。

在第四个测试用例中，Piggy可以选择以下航班: $3\rightarrow 2\rightarrow 1$，费用为$11+11=22$。