Algorithm Complexity#4342
Petr wants to use his own algorithm to solve a very important problem for a directed graph with vertices and arcs. Unfortunately, Petr cannot calculate a complexity of his algorithm. He only knows that the complexity depends on the order of growth of value which denotes the number of walks of length from vertex to vertex in . Petr wants to bound with a polynomial of minimal degree, that is, to find the minimal non-negative integer such that for some fixed number inequality F(n) \le C \cdot n^k holds for any positive .
Help him to do it.
The first line contains four integers , , , (1 \le n, m \le 10^5). The vertices are numbered from to . Each of the next lines contains two space-separated integers - numbers of starting and ending vertices of the current arc. The graph doesn't contain multiple arcs but may contain loops.
Output the minimal integer that satisfies the problem statement. If there are no such numbers, output "".
Example 1
Example 2