EWM Auto Co‐Pilot Control

EWM, a renowned automobile company, has installed its latest auto co‐pilot technology in its vehicles. In this tech, the car drives along a directed graph \(G\) where each vertex represents a location. The car starts at vertex \(s\) and needs to reach the destination vertex \(t\). Under normal operation, at each vertex the car moves on one of its outgoing edges uniformly at random (i.e. if there are 3 outgoing edges, each is chosen with probability \(1/3\)).

To allow the driver some control over the car's movements, EWM offers a mechanism: before the AI chooses its direction, the driver may pay 1 token to force the car to take a specific outgoing edge (this override applies only to that one decision; if the car later revisits the same vertex, the decision is made afresh). Note that the car must always follow the directed edge directions.

Little Ming, the driver, wants to know the minimum number of tokens he must have in order to guarantee that, at any moment before reaching \(t\), the current location always has at least one path to \(t\). In other words, by strategically using tokens to override the random decisions when necessary, he wants to avoid any situation from which \(t\) becomes unreachable.

Your task is to compute the minimum number of tokens required for a given graph \(G\) (with \(n\) vertices and \(m\) edges) and given start and target vertices. If it is impossible to guarantee a safe route, output -1.

The decision process at each vertex \(v\) with outgoing neighbors \(w_1, w_2, \dots, w_k\) works as follows:

• If the driver does not override at \(v\), the car moves randomly and safety is ensured only if every adjacent vertex \(w\) guarantees a safe route (this corresponds to a worst‐case cost \(\max\{f(w): w \in \text{out}(v)\}\)).
• If the driver chooses to override, he pays 1 token and may choose an edge \(v \to w\) such that the remaining required tokens are \(f(w)\). This cost is \(1+\min\{f(w): w \in \text{out}(v)\}\).

Thus, for each vertex \(v\) (other than \(t\)), if \(\text{out}(v)\) is not empty, define:

[ f(v)= \min\Bigl(1+ \min_{w \in \text{out}(v)} f(w),; \max_{w \in \text{out}(v)} f(w)\Bigr), ]

with \(f(t)=0\) and if \(v\) has no outgoing edge (and \(v \neq t\)) then \(f(v)=\infty\). The answer is \(f(s)\) if it is finite; otherwise, output -1.

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of vertices and directed edges respectively. The next \(m\) lines each contain two integers \(u\) and \(v\) indicating a directed edge from \(u\) to \(v\). The last line contains two integers \(s\) and \(t\), the start and target vertices respectively. The vertices are 1-indexed.

outputFormat

Output a single integer: the minimum number of tokens needed to guarantee that before reaching \(t\), at every step the current location has a path to \(t\). If it is impossible to guarantee this, output -1.

sample

3 3
1 2
1 3
2 3
1 3

0