AT_tkppc4_2_j.ドライブ旅行

在パ研王国有 $N$ 个城镇，$M$ 条道路连接着这些城镇。第 $i$ 条道路是从城镇 $A_i$ 到城镇 $B_i$ 的单向道路。此外，有 $P$ 个城镇各自拥有一个观景台，城镇 $C_i$ 的观景台建在海拔 $D_i$ 的位置。

ZRK 君计划去自驾游。他将从城镇 $S$ 的观景台出发，经过若干道路，最终在城镇 $T$ 的观景台结束自驾游。途中可以多次经过同一个城镇或道路。

每当 ZRK 君经过一个有观景台的城镇时，必定会停留。ZRK 君的“开心值”初始为 $0$，每当（除了出发时）停留在观景台 $i$ 时，他的开心值会增加与上一次停留的观景台 $j$ 的海拔差的绝对值 $|D_i - D_j|$。

他希望自驾游结束时的开心值至少为 $K$。请你求出满足条件的路线的最小长度。

这里，路线的长度定义为所有道路经过的总次数。例如，若路线为 $3 \to 5 \to 2 \to 4 \to 3 \to 5 \to 4$，则长度为 $6$。

如果不存在开心值至少为 $K$ 的路线，请输出 $-1$。

输入以如下格式从标准输入读入。

$N$ $M$ $P$ $S$ $T$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ ... $A_M$ $B_M$ $C_1$ $D_1$ $C_2$ $D_2$ ... $C_P$ $D_P$

请输出满足条件的路线的最小长度。
如果不存在这样的路线，请输出 $-1$。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 50$
• $1 \leq M \leq N(N-1)$
• $1 \leq P \leq N$
• $1 \leq S, T \leq N$
• $1 \leq K \leq 10^9$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$
• $A_i \neq B_i$ $(1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j)$ $(i \neq j)$
• $1 \leq C_i \leq N$ $(1 \leq i \leq P)$
• $1 \leq D_i \leq 10^5$ $(1 \leq i \leq P)$
• $C_i \neq C_j$ $(i \neq j)$
• 存在 $i$ 使得 $C_i = S$，存在 $j$ 使得 $C_j = T$。

子任务

本题有 $2$ 个子任务。

1. (300 分) 满足 $K \leq 20$。
2. (700 分) 无额外限制。

由 ChatGPT 4.1 翻译