SP13091 PCPC12E - Snakes and Ladders

蛇梯棋是一种古老的印度游戏，现在已成为全球经典。游戏在一个网格状的棋盘上进行，棋盘上有编号的方格。棋盘上画有多个“梯子”和“蛇”，每个它们都连接着两个特定的方格。游戏的目标是将玩家的棋子从起点（底部方格）移动到终点（顶部方格），在此过程中，玩家可能会因为梯子而更快前进，也可能因为蛇而后退。历史上，这款游戏还寓意着人生之旅，梯子象征美德，而蛇则代表恶习。玩家掷骰子后，如果棋子落在“梯子”的低端，玩家便可以沿梯子移动到高端；如果落在“蛇”的高端，玩家就必须滑落到蛇的低端。此类方格被称为不稳定方格，否则为稳定方格。 这个游戏是一个简单的竞速比赛，因其不需要技巧，非常受小朋友的欢迎。 在这个问题中，你需要计算玩家从起点（底部方格）到达终点（顶部方格）所需的最小骰子投掷次数。 **游戏详细描述** 棋盘以 $N \times M$ 的网格排列，并由方格 1 到 $N \times M$ 编号。最后一个方格（编号 $N \times M$）为终点方格。每位玩家的棋子从位置 0（位于编号为 1 的方格旁边的一个虚拟空间，即底部方格）开始，该位置总是稳定的。所以棋盘总共有 $N \times M + 1$ 个方格。每回合玩家通过掷出骰子决定向前移动的步数。如果移动后的方格超过了终点方格，棋子则不移动。如果棋子最终停在不稳定的方格，会根据梯子或蛇的指示继续移动，直到抵达一个稳定的方格。可以假定任何方格都能到达一个稳定方格。如果最终稳定方格为终点方格，则游戏结束，玩家获胜。

输入包含多个测试用例。每个测试用例第一行给出四个整数 $N$、$M$、$S$ 和 $L$，分别表示棋盘的行数、列数、蛇的数量和梯子的数量，其中 $0 < N \leq 100$, $0 < M \leq 100$。接下来的 $S$ 行描述蛇的位置，每行给出两个整数：$h$ 表示蛇头的位置，$t$ 表示蛇尾的位置（$0 < t < h \leq N \times M$）。接下来的 $L$ 行描述梯子的位置，每行给出两个整数：$p$ 表示梯子的底部位置，$q$ 表示梯子的顶部位置（$0 < p < q < N \times M$）。 输入以文件结束符标示结束。 **注意**：可能会有多个蛇或梯子从同一个方格出发，在这种情况下，应使用输入中最后一次指定的蛇或梯子进行处理。

针对每个测试用例，输出从起点到终点所需的最小的骰子投掷次数。如果无法到达终点方格，则输出 -1。 ``` 样例输入 1 1 0 0 1 2 1 0 2 1 5 10 3 5 16 6 47 26 49 11 1 38 4 14 9 31 40 42 36 44 ``` ``` 样例输出 1 -1 3 ``` **本翻译由 AI 自动生成**