ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Algorithm Complexity

Time limit: 1.0 second
Memory limit: 64 MB
Petr wants to use his own algorithm to solve a very important problem for a directed graph G with n vertices and m arcs. Unfortunately, Petr cannot calculate a complexity of his algorithm. He only knows that the complexity depends on the order of growth of value F(N) which denotes the number of walks of length N from vertex s to vertex t in G. Petr wants to bound F(N) with a polynomial of minimal degree, that is, to find the minimal non-negative integer k such that for some fixed number C inequality F(N) ≤ CNk holds for any positive N. Help him to do it.


The first line contains 4 space-separated integers n, m, s, t (1 ≤ n, m ≤ 100000). The vertices are numbered 1 to n. Each of the next m 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 k which satisfies the problem statement. If there are no such numbers, output “−1”.


2 3 1 2
1 1
1 2
2 2
3 6 1 2
1 2
2 1
1 3
3 1
2 3
3 2
Problem Author: Ivan Burmistrov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1691. Algorithm Complexity