Piggy 生活在一个无限平面上,其上有笛卡尔坐标系。
飞机上有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$,前$$$k$$$个城市定义为主要城市。第 $$$i$$$ 个城市的坐标为 $$$(x_i,y_i)$$$。
小猪作为一名经验丰富的旅行者,希望在中考结束后来一次轻松的旅行。目前,他在城市 $$$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} $$$$$$
小猪不想节省时间,但他想省钱。所以你需要告诉他,如果他可以乘坐任意数量的航班,那么所有机票总费用的最小值是多少。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^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$$$ 行描述了主要城市。保证所有坐标都是成对不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 所有机票总价的最小值。
示例
输入 #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$$$。
在第四个测试用例中,小猪可以选择乘坐以下航班:$$$3\rightarrow 2\rightarrow 1$$$,费用为$$$11+11=22$$$。