Maximum by minimum

Directed 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(1\le s\le n\le 5000,1\le m\le 20000)$ — 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.

Examples