#include <iostream> #include <cstdio> using namespace std; const int INF = 1000000000; const int MaxN = 10000; const int MaxM = 200000; struct halfEdge { int u; halfEdge *next; }; halfEdge adj_pool[MaxM * 2], *adj_tail = adj_pool; inline void addEdge(halfEdge **adj, int v, int u) { adj_tail->u = u, adj_tail->next = adj[v], adj[v] = adj_tail++; } bool forb[MaxN + 1]; void bfs(halfEdge **adj, int sv, int *dist) { int q_n = 0; static int q[MaxN]; if (!forb[sv]) dist[sv] = 0, q[q_n++] = sv; for (int i = 0; i < q_n; i++) { int v = q[i]; for (halfEdge *e = adj[v]; e; e = e->next) if (dist[e->u] == INF && !forb[e->u]) dist[e->u] = dist[v] + 1, q[q_n++] = e->u; } } int main() { //freopen("road.in", "r", stdin); //freopen("road.out", "w", stdout); int n, m; static halfEdge *origG[MaxN + 1]; static halfEdge *oppoG[MaxN + 1]; cin >> n >> m; for (int i = 0; i < m; i++) { int v, u; scanf("%d %d", &v, &u); addEdge(origG, v, u); addEdge(oppoG, u, v); } int sv, ev; scanf("%d %d", &sv, &ev); static int dist[MaxN + 1]; fill(dist + 1, dist + n + 1, INF); bfs(oppoG, ev, dist); for (int v = 1; v <= n; v++) for (halfEdge *e = origG[v]; e; e = e->next) if (dist[e->u] == INF) forb[v] = true; fill(dist + 1, dist + n + 1, INF); bfs(origG, sv, dist); printf("%d\n", dist[ev] != INF ? dist[ev] : -1); return 0; } /************************************************************** Problem: 2338 User: admin Language: C++ Result: Accepted Time:162 ms Memory:8572 kb ****************************************************************/