跳棋是我们很多人小时候喜爱的游戏，今天我们尝试改进一下这个游戏使得它更加有趣。

我们设计一个一维的，由很多格子组成的游戏空间，每个格子按照顺序编号为w（1 ≤ w≤ 1000000）。我们在这个游戏空间中可以使用跳跃的方式进行运动，但是每次跳跃的格子数必须不大于s（1 ≤ s ≤ 6），我们的最终目标是用最短的时间从起点0到达终点T（每次跳跃耗时为1）。显然，描述至此，这个问题依然很简单，所以我们现在往其中加入一些传送阵，传送阵具有方向性，也就是说传送阵可以从u传送到v，却并不意味着v能够传送到u，我们定义每次传送的时间为0。当然，作为一个有大局观的人，我们可以在跳到一个传送点后选择不传送。

有多组测试数据。 输入的第1行是三个整数T，s和p，其中p代表传送阵的数量（1 ≤ p ≤ 40）。 输入的第2到p+1行包括两个整数a和b代表有一个传送阵可以使得我们从a点传送到b点。

对应每组测试数据输出一个整数，代表从起点到达终点最少需要的时间。