Дмитрик захопився вивченням графів і сьогодні він намагається розв'язати задачу, яка його особливо захопила.

Отже, є простий орієнтований граф з ~N~ вершинами та ~M~ ребрами. Вершини пронумеровані від 1 до ~N~. ~I~-те ребро (~1 \le i \le M~) спрямоване від вершини ~a_i~ до вершини ~b_i~.

Дмитрик хоче визначити, чи існує такий цикл, що містить вершину 1, і якщо такі цикли існують, то треба знайти мінімальну кількість ребер серед таких циклів.

Обмеження

• ~2 \le N \le 2 \times 10^5~
• ~1 \le M \le min(\frac{N(N-1)}{2},2 \times 10^5)~
• ~1 \le a_i \le N~
• ~1 \le b_i \le N~
• ~a_i \neq b_i~
• ~(a_i, b_i) \neq (a_j, b_j)~ і ~(a_i,b_i) \neq (b_j,a_j)~, якщо ~i \neq j~
• Усі вхідні значення є цілими числами.

Input

Перший рядок вхідного потоку містить цілі числа ~N, M~.

Наступні ~M~ рядків містять цілі числа ~a_i, b_i~. Числа розділяються пропуском.

Output

Якщо існують цикли, які містять вершину 1, то виведіть мінімальну кількість ребер серед таких циклів або -1 у випадку, коли такого циклу немає.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

3

Sample Input 2

3 2
1 2
2 3

Sample Output 2

-1

Sample Input 3

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

Sample Output 3

4