「惑星」を頂点，「航路」を辺とした有向グラフを考えます．

各頂点について，そこから直接辺で結ばれた頂点のリストを作り，空でないならばそのうち番号最小の頂点につながる辺を重み \(0\)，他の頂点につながる辺を重み \(1\) とします．このとき，各辺を通るときの「燃料の消費量」は，その辺の重みとして得られます．

この有向グラフ上で，頂点 \(S\) から頂点 \(T\) への最短路を求めればよいです．これは Dijkstra 法や 01-BFS などのアルゴリズムによって実現できます．時間計算量は Dijkstra 法の場合は \(O(N + M \log N)\) 時間，01-BFS の場合は \(O(N + M)\) 時間です．

実装例 (C++)

この実装例では 01-BFS を採用しています．なお，各頂点から直接辺で結ばれた番号最小の頂点を求める部分でソートをしているため，時間計算量は \(O(N + M (\log N + \log M))\) になっています．

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <cassert>
using std::min;
using std::max;
#include <deque>
using std::deque;



#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

using ll = int64_t;
using P = pair<ll, ll>;

const ll INF = 1'000'000'000'000'000'009LL;

ll n, m, s, t;
vector<ll> a, b;

inline void output (const ll x) {
	cout << x << "\n";
}



void solve() {
	vector<vector<P> > g(n);
	for (ll i = 0; i < m; i++) {
		g[a[i]].emplace_back(b[i], 1);
	}
	for (ll i = 0; i < n; i++) {
		if (g[i].size() > 0) {
			sort(g[i].begin(), g[i].end());
			g[i][0].second = 0;
		}
	}

	vector<ll> d(n, INF);
	deque<P> que;
	d[s] = 0;
	que.push_front({d[s], s});
	while (!que.empty()) {
		P p = que.front();
		que.pop_front();

		ll dv = p.first;
		ll v = p.second;
		if (d[v] < dv) continue;

		for (auto &[u, len] : g[v]) {
			if (d[u] > dv + len) {
				d[u] = dv + len;
				if (len == 0) {
					que.push_front({d[u], u});
				} else {
					que.push_back({d[u], u});
				}
			}
		}
	}

	if (d[t] == INF) {
		output(-1);
	} else {
		output(d[t]);
	}
	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n >> m >> s >> t;
	--s;
	--t;
	a.resize(m);
	b.resize(m);
	for (ll i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
	}

	solve();

	
	return 0;
}