U180005 Tingtime 老师等地铁

`Tingtime` 老师带着他的学生们去某不知名省份的某不知名赛区参赛了。在地铁站，`Tingtime` 老师觉得等地铁太无聊了，他注意到了地铁线路图，于是他想理性愉悦一下。

线路图上有 $z$ 个地铁站（从 $1$ 到 $z$ 编号）。在线路图上有几条已经建好的铁路，还有几条没有正在建的铁路。连接两个地铁站的铁路有 $n$ 条，连接两个地铁站的在建铁路有 $m$ 条。 `Tingtime` 老师想要从起点 $s$ 到 终点 $t$，但是他嫌地铁太慢了。`Tingtime` 老师有 $k$ 个时间加速器，可以立刻修好任意两个相邻两个站点之间正在修建的铁路（如果没有正在修建的铁路则无法使用）。`Tingtime` 老师想要知道他最少需要经过多少个站点（如果有重复的则计算两次）。

第一行四个整数 $n、m、z、k$。 接下来 $n$ 行，每行两个整数 $u$，$v$（$0 \lt u,v \le z$），表示编号为 $u$ 和 $v$ 的地铁站之间有一条铁路（已经建好的）。 接下来 $m$ 行，每行两个整数 $u$，$v$（$0 \lt u,v \le z$），表示编号为 $u$ 和 $v$ 的地铁站之间有一条铁路（正在修建的）。 最后一行两个整数 $s$ 和 $t$。（$0 \lt s,t \le z$）

输出一个整数，表示`Tingtime` 老师需要经过的站点数量的最小值。若无法到达，则输出 $-1$

### 样例说明：  将节点 $4$ 和 $5$ 之间的铁路加速修建，经过的节点数最少为$4$。 ### 数据范围 $0 \lt n+m \le 5 \times 10^{4}$ $0 \lt k \le 10$ $0 \lt z \le 2 \times 10^{4}$ 题目存在重边与自环