당신의 인생

꿈을 이루는 과정에서 일어날 수 있는 상황의 관계를 그래프로 나타낸다. 수많은 상황을 $N$개로 압축하고 1번부터 $N$번까지 번호를 붙였다. 당신은 지금 1번 상황에 있고, $N$번 상황이 당신이 이루려는 유일한 꿈이다.

상황은 당신의 선택에 따라 바뀐다. 선택할 수 있는 변화는 모두 $M$개이며 $x$, $y$ 형태로 주어진다. 이는 $x$번 상황에 있을 때 $y$번 상황으로 가는 선택을 할 수 있다는 뜻이고, $x < y$가 보장된다.

당신은 꿈을 이룰 수 있는가? 이룰 수 있다면 상황이 바뀌는 횟수를 최소로 줄였을 때 몇 번 만에 꿈을 이루는가?

첫째 줄에 자연수 $N$과 $M$이 공백으로 구분되어 주어진다. $1 \le N \le 100000$이고 $0 \le M \le 200000$이다.

다음 $M$개의 줄에 자연수 $x$와 $y$가 공백으로 구분되어 주어진다. $1 \le x < y \le N$이다. 같은 변화가 두 번 이상 주어질 수 있다.

꿈을 이룰 수 있으면 필요한 상황 변화 횟수의 최솟값을 출력하고, 이룰 수 없으면 -1을 출력한다.

첫 번째 예제에서는 1번에서 2번으로, 다시 2번에서 4번으로 상황을 바꾸면 두 번 만에 꿈을 이룬다.