After many years of art, young Florian wants to work in a conglomerate. This company consists of N employees denoted 1, 2, ..., N, of which some are interns. Florian knows all interns in this company. In the hierarchy, every employee has a single boss, except for one employee (the CEO) who does not have a boss. There is no cycle within the hierarchy; in other words, the hierarchy is a tree. Also, an intern cannot be superior to a non-intern.

Speaking to interns, Florian has collected a wealth of information about parts of the hierarchy. Namely, for every intern he knows who his/her boss is (this boss could also be an intern).

Florian now counts the distance of two interns in the hierarchy, which is the number of bosses between these interns. More precisely, the distance in the hierarchy between two employees is obtained by climbing the hierarchy starting with them, and counting all their direct or indirect superiors up to their first common superior (including him). If one of the observed two employees is superior to another (directly or indirectly), we only count the employees who are strictly between them in the hierarchy.

Help young Florian determine the largest distance of two interns across the hierarchy, if this number can be uniquely determined from the known data.

Input

The first line contains two integers N and M, the total number of employees in the company and the number of interns (2 ≤ M < N ≤ 100 000).

Each of the following M lines contains two integers A and B, intern and his boss (1 ≤ A, B ≤ N, A ≠ B). No intern will have two bosses.

Input

Print the required largest intern distance, or -1 if the answer cannot be determined.

Example

Input:
5 4
2 1
3 2
4 3
5 4

Input:
7 4
1 2
2 3
4 5
5 6 

Input:
3 2
2 1
3 1

Output:
2

Output:
-1

Output:
1