e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Breadth First Search

Maximum by minimum

An oriented unweighted graph is given. Find in it a vertex, the shortest distance from which to the given one is maximum, and print this distance.

Input

First line contains three positive integers n, m и s (1sn5000, 1m20000) - the number of vertices and edges in the graph and the number of given vertex. In the next m lines the graph edges are given. Each edge is given with the pair of numbers - the starting and the ending point.

Output

Print the required shortest distance.

Time limit 2 second
Memory limit 128 MiB
Input example #1
3 5 3
1 2
2 1
3 1
2 3
3 3
Output example #1
2
Input example #2
5 4 5
1 2
2 3
3 4
4 5
Output example #2
4