## PODUZECE - Incomplete hierarchy

no tags

After many years of art, young Florian wants to work in one conglomerate.
There are N persons assigned by numbers from 1 to N, of which some interns are. Florijan knows
all the interns in this company and fascinated by the massiveness of the hierarchy.
In the enterprise hierarchy, every employee has a single boss, except the chief boss, ie the director
who does not have a boss over himself. There is no cycle within the hierarchy, ie hierarchy is a tree form. Also worth it
that a trainee can not be superiors to non-trained employees.
Speaking to practitioners, Florian had collected a wealth of information about the layout of a part of the hierarchy.
Namely, for every intern he learned who his boss was (maybe his boss is also a trainee). Florian
now entertains counting the distance of some of the two internships in the hierarchy, which counts as the number of bosses between
these internships.
More precisely, the distance to the hierarchy for two employees is obtained by climbing the hierarchy
starting with them, count all their direct and indirect bosses to their first boss (including
and him). If one of the observed two employees is supervised by another (directly or indirectly),
we only count the bosses who are strictly in the hierarchy between them.
Help young Florian determine the maximum distance of two internships across the hierarchy, if this
number can be determined (not interested in exactly the ones who are exactly the most distant).

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```