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

hide comments
mehmetin: 2018-05-11 21:34:59

--

Last edit: 2018-05-12 06:57:09
nadstratosfer: 2018-05-11 18:46:28

My bad, I was looking at the first example. The second case is "incomplete", eg. either 1 or 4 is a subordinate of someone else, but we don't know who - hence the answer is -1.

Disclaimer: Just trying to help, I got WA myself and gave up for the time being, unable to find a case where my code breaks. Unusually high ratio of WAs for this problem in general, please post some tricky case if you find one.

Last edit: 2018-05-11 18:53:33
mehmetin: 2018-05-11 09:00:17

I chose the direction of the tree in the other direction, from bosses to interns. Both ways, there are two roots in the second example, and also two CEO's.

Last edit: 2018-05-11 09:03:28
nadstratosfer: 2018-05-11 02:35:02

First integer is the intern, second is the boss. Second example is a tree rooted in 1.

mehmetin: 2018-05-10 18:19:21

The description says there can be only one employee without a boss in the hierarchy. But in the second example it seems like there are two employees without a boss (3 and 6). So I understand there can be many employees without a boss in many hierarchies, only one in each hierarchy, is that correct?

Last edit: 2018-05-10 20:54:30

Added by:Adrian Satja Kurdija
Date:2018-04-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Croatian regionals 2018. by Dominik Gleich. Prepared for SPOJ (with additional test data) by Adrian Satja Kurdija.