Your life Batch Compilation commands

당신이 꿈을 이루는 과정 중에 일어날 수 있는 수많은 상황들의 관계를 그래프로 나타내어 보겠다. 많은 상황을 압축해서 $N$개의 상황이 일어날 수 있다고 하고 1번에서 $N$까지의 번호를 붙였다. 당신은 현재 1번 상황에 있다. 그리고 $N$번 상황은 당신이 이루고자 하는 유일한 꿈이다.

상황은 당신의 선택에 따라 변화할 수 있다. 당신이 선택할 수 있는 변화는 총 $M$개 있으며 $x, y$의 형태로 주어진다. 이는 당신이 상태 $x$에 있는 경우 상태 $y$로 가는 선택을 할 수 있다는 것을 의미하며, $x < y$임이 보장된다.

당신은 꿈을 이룰 수 있을까? 이룰 수 있다면 당신의 상황이 변화하는 횟수를 최소한으로 줄이면 몇 번 만에 꿈을 이룰 수 있을까?

입력 형식

첫 번째 줄에는 두 개의 자연수 $N$, $M$($0 \le M \le 200,000$)이 주어진다.

이후 $M$개의 줄에는 두 개의 자연수 $x$, $y$($1 \le x < y \le N$)가 공백으로 구분되어 주어진다

쉬운 문제에서는 $1 \le N \le 100$인 입력이 주어진다.

어려운 문제에서는 $1 \le N \le 100,000$인 입력이 주어진다.

출력 형식

당신이 꿈을 이룰 수 있다면 꿈을 이루기 위해 필요한 상황 변화 수의 최솟값을 출력하고, 이룰 수 없다면 -1을 출력한다.

입력

4 4
1 2
2 3
3 4
2 4

출력

2

$1 \rightarrow 2 \rightarrow 4$로 상황을 바꾸면 두 번 상황이 바뀐 후 꿈을 이루게 된다.