描述

有$N$个岛屿，记为1、2、3、...、N。有$M$座巨大弹弓，瞄准了另外一个岛屿，并且由于需要精密计算，目标岛屿不能更改。

现在你在1号岛屿，需要利用这些弹弓把包裹寄到$K$号岛屿，问，能否到达？如果能，请找出最少需要使用多少个弹弓，如果不能，请输出-1.

现在每个岛屿可以安装多个弹弓

输入输出格式

输入

第一行为两个以空格隔开的正整数$N$ $K$， 其中$N$表示一共有几个岛屿，$K$表示包裹的目的地岛屿编号。 ( $1≤K≤N<1,000$ )

第二行为一个正整数$M$，表示一共有多少座弹弓。 ( $1 ≤ M < N$ )

随后$M$行，每行为两个以空格分割的正整数$a$, $b$，表示$a$岛屿上有一个瞄准了$b$岛屿的弹弓。 ( $1 ≤ a ≤ N, 1 ≤ b ≤ N$ )

输出

一行，一个整数，如果能到达，则输出最少需要使用的弹弓数量，否则输出-1。

样例

5 3
3
1 2
2 3
2 4

2