Constrained Shortest Path in Directed Graph

You are given a directed graph \(G\) with \(n\) vertices and \(m\) edges. Each edge has a length of \(1\). The graph may contain multiple edges and self-loops. It is guaranteed that the target vertex \(t\) has no outgoing edges.

Given a starting vertex \(s\) and a target vertex \(t\), find a shortest path from \(s\) to \(t\) that satisfies the following condition:

1. For every vertex \(v\) on the path, every vertex \(w\) such that there is an edge \(v \to w\) must have a (direct or indirect) path to \(t\). In other words, all out-neighbors of \(v\) must be connected to \(t\) in \(G\).
2. Among all paths satisfying condition 1, the path should be the shortest in terms of the number of edges.

If such a path exists, output its length. Otherwise, output \(-1\).

Note: Self-loops and multiple edges may be present in \(G\). The guarantee that \(t\) has no outgoing edges ensures that no vertex reachable from \(t\) will violate the condition by having an edge leaving to a vertex that cannot reach \(t\).

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), and \(t\) where \(1 \leq s, t \leq n\) and \(1 \leq n, m \leq 10^5\). \(s\) is the start vertex and \(t\) is the target vertex.

The following \(m\) lines each contain two integers \(u\) and \(v\) (\(1 \leq u, v \leq n\)) representing a directed edge from vertex \(u\) to vertex \(v\). Note that there can be multiple edges between the same pair of vertices and self-loops. It is guaranteed that the target vertex \(t\) has no outgoing edges.

outputFormat

Output a single integer representing the length (number of edges) of the shortest valid path from \(s\) to \(t\) that satisfies the condition. If no such path exists, output \(-1\).

sample

3 3 1 3
1 2
1 3
2 3

1