https://www.luogu.com.cn/record/89657325

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct edge {
	int to, w, next;
} e[N];
queue<int> q;
int n, m, u, v, qwq, s, z, cnt, tot, t, a[N], head[N], dis[N];
unordered_map<int, int> S;
bool vis[N];
int disc(int x) {
	return S.count(x) ? S[x] : S[x] = ++ tot;
}
void add(int u, int v, int w) {
	u = disc(u), v = disc(v);
	e[++ cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void SPFA(int s) {
	for (int i = 1; i <= tot; i ++)
		dis[i] = INT_MAX;
	q.push(s), dis[s] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].to;
			if (dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if (!vis[v]) q.push(v), vis[v] = true;
			}
		}
	}
}
int main() {
	while (true) {
		cin >> qwq;
		if (qwq) cin >> m >> n;
		else break;
		memset(head, 0, sizeof head), tot = cnt = 0;
		memset(vis, 0, sizeof vis), S.clear();
		s = 0, a[++ t] = 0, a[++ t] = qwq;
		for (int i = 1; i <= n; i ++)
			cin >> u >> v, add(u, v, 0), a[++ t] = u, a[++ t] = v;
		for (int i = 1; i <= t; i ++)
			for (int j = 1; j <= t; j ++)
				if (a[j] >= a[i]) add(a[i], a[j], ceil(1.0 * (a[j] - a[i]) / m));
		SPFA(disc(0));
		cout << dis[disc(qwq)] << '\n';
	}
	return 0;
}