小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$ 之间存在道路

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

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