PODUZECE - Incomplete hierarchy

no tags 

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