Taco: Minimum Maximum Moves on a Directed Acyclic Graph

Amelia and Ben are playing a modified game on a directed acyclic graph (DAG) with n vertices. The vertices are numbered from 1 to n. Amelia starts at vertex 1, and Ben starts at vertex y (1 ≤ y ≤ n). In each move, a player can traverse from the current vertex to any adjacent vertex following the directed edges. The game ends when both players can meet at some vertex that is reachable from both starting points.

Let d_A(i) be the shortest distance (number of moves) from vertex 1 to vertex i, and d_B(i) be the shortest distance from vertex y to vertex i. The objective is to determine the minimum number M such that there exists a vertex i with both d_A(i) and d_B(i) finite and M = \(\min_{i=1}^{n} \max(d_A(i), d_B(i))\).

Input Format: The input begins with two integers n and y separated by spaces on one line. The next line contains an integer m, representing the number of directed edges in the graph. The following m lines each contain two integers a and b, indicating a directed edge from vertex a to vertex b.

Output Format: Output one integer—the minimum number of moves required, as defined above.

inputFormat

The first line contains two integers n and y (1 ≤ y ≤ n), representing the number of vertices and the starting vertex for Ben, respectively.

The second line contains an integer m, the number of directed edges.

Each of the next m lines contains two space-separated integers a and b representing a directed edge from vertex a to vertex b.

outputFormat

Print a single integer representing the minimum number of moves required for both players to meet, based on the minimal maximum distance from the starting vertices to a common reachable vertex.

5 4
5
1 2
1 3
2 4
3 5
4 5

2