提交记录

#include <bits/stdc++.h>
#define LL long long

using namespace std;

int n, m, t[] = {-1, 1}, tb, sb;
bool v[30010];
queue <tuple <int, int, int>> q;
bitset <30010> vis[30010];
vector <int> a[30010];

int main () {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int b, p;
        scanf("%d%d", &b, &p);
        a[b].emplace_back(p);
        if (i == 0) {    
            sb = b;
        }
        if (i == 1) {
            tb = b;
        }
    }
    v[sb] = 1;
    for (auto i : a[sb]) {
        q.emplace(sb, i, 0);
    }
    if (sb == tb) {
        cout << 0;
        return 0;
    }
    while (q.size()) {
        int b = get <0> (q.front()), p = get <1> (q.front()), s = get <2> (q.front());
        q.pop();
        // cout << b << " " << p << " " << s << "\n";
        if (tb == b + p || tb == b - p) {
            cout << s + 1;
            return 0;
        }
        for (int i = 0; i < 2; i++) {
            int bb = b + t[i] * p;
            if (bb < 0 || bb >= n) continue;
            if (!vis[bb].test(p)) {
                vis[b].set(p);
                q.emplace(bb, p, s + 1);
            }
            if (!v[bb]) {
                v[bb] = 1;
                for (auto j : a[bb]) {
                    q.emplace(bb, j, s + 1);
                }
            }
        }
    }
    cout << -1;
    return 0;
}