Maximum by minimum

Input

The first line contains three positive integers $n$, $m$, and $s$ (1 \le s \le n \le 5000, 1 \le m \le 20000) — the number of vertices, the number of edges in the graph, and the index of the specified vertex, respectively. Each of the next $m$ lines contains two integers, the start and end vertices of an edge.

Output

Print the maximum shortest distance from any vertex to $s$.

Examples