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

Отже, є простий орієнтований граф з \(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