小Z是一个非常喜欢冒险的美食家，经常游走在各地寻找美食。这一天，他像往常一样前往城镇A寻找远近闻名的甜甜花酿鸡，却不慎掉入了异次元空间(不是提瓦特大陆)，他想尽快找到出口，却发现这里和真实的世界有些不同...

这个世界有许多城镇，每一个城镇都有一个二维坐标，某两个城镇之间有道路相连，道路的长度不一定是欧氏距离(直线距离)，而是$Lk$范数。小Z的初始位置在城镇$A$，异次元空间出口所在的位置在城镇$Z$，现在问你小Z应该最少走多远才能到达出口。

关于$Lk$范数：对于任意两个城镇$A(x1,y1),B(x2,y2)$的$Lk$范数为 (|x₁-x₂|^k+|y₁-y₂|^k)^1/k

提示：若存在三个城镇$A$、$B$、$C$，$Pk(X,Y)$表示城镇$X$和$Y$的$Lk$范数，则$Pk(A,C)\le Pk(A,B)+Pk(B,C)$（三角不等式）

第一行三个整数$n,m,k(2\le n\le 10000,0\le m\le min(n(n-1)/2,10000),1\le k\le 6)$
分别表示异次元空间中一共存在$n$个村庄，$m$条道路，$Lk$范数中的$k$

随后$n$行每行两个整数$x,y(-200\le x,y\le 200)$表示$n$个城镇的坐标
城镇$A$在第二行，城镇$Z$在第$n+1$行

接着$m$行每行两个数$u,v(1\le u,v\le n)$表示城镇$u$和城镇$v$之间存在道路

不保证数据不存在自环、重边、重点

一个数字表示从城镇 $A$ 到城镇 $Z$ 的最短距离，保存两位小数；若无法到达输出-1.00

由于k=1，因此两城镇间的距离计算公式为∣x₁−x₂∣+∣y₁−y₂∣。三个城镇的坐标分别为A(0,0)、B(1,0)、Z(1,1)，并且两两之间存在道路连接，因此城镇A可以直接到达城镇Z，距离为2.00。

18新利直播 2022级新生程序设计大赛暨省内高校邀请赛