Minimum Problems to Solve

You are given n problems numbered from 1 to n and m dependencies between them. Each dependency is represented by a pair of integers (u, v) which indicates that problem u must be solved before problem v can be attempted.

Your task is to determine the minimum number of problems that must be solved before starting the target problem t. In other words, you need to compute the level (or distance) of problem t in the dependency graph using a topological sorting approach.

If the target problem is independent (i.e. it has no prerequisites), then the answer is 0.

The relationship among the problems can be mathematically represented as follows:

\( \text{level}(t) = \begin{cases} 0, & \text{if } t \text{ has no prerequisites}\\ \min_{u \rightarrow t} \{ \text{level}(u) + 1 \}, & \text{otherwise} \end{cases} \)

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains three integers: n (number of problems), m (number of dependencies) and t (the target problem).
• The next m lines each contain two integers u and v, representing that problem u must be solved before problem v.

outputFormat

Output a single integer on standard output (stdout) that represents the minimum number of problems that must be solved before starting to solve problem t.

5 4 5
1 2
2 3
2 4
4 5

3