PODUZECE  Incomplete hierarchy
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 nonintern.
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:
20180511 21:34:59
 Last edit: 20180512 06:57:09 

nadstratosfer:
20180511 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.


mehmetin:
20180511 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: 20180511 09:03:28 

nadstratosfer:
20180511 02:35:02
First integer is the intern, second is the boss. Second example is a tree rooted in 1. 

mehmetin:
20180510 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: 20180510 20:54:30 
Added by:  Adrian Satja Kurdija 
Date:  20180418 
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. 