#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
#define LL long long
#define UL unsigned long long
#define BASE 1000000000000000000ull
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >
#define vi vector <int>
#define vii vector <vi>
#define vp vector <ii>
#define vpp vector <vp>
#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , n , x) for(int i = n ; i >= x ; --i)
#define FORC(v , a) for(auto v : a)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define lovethi ios::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define fill_a(x , i) memset(x , i ,sizeof x) ;
#define ar array
const int oo = 1e9 + 7 ;
const int N = 3e4 + 5 ;
const int MOD = 1e9 + 7 ;
int n, m;
map <int, int> dp[N];
vector <int> a[N];
void bfs() {
REP(i, n) REP(j, n) dp[i][j] = oo;
priority_queue <iii, vector <iii>, greater <iii>> pq;
FORC(v, a[0]) pq.push(iii(0, ii(0, v))), dp[0][v] = 0;
while(pq.size()) {
int u = pq.top().se.fi, nxt = pq.top().se.se, cost = pq.top().fi;
pq.pop();
if(dp[u][nxt] < cost) continue;
if(u + nxt < n && dp[u + nxt][nxt] > dp[u][nxt] + 1) {
dp[u + nxt][nxt] = dp[u][nxt] + 1;
pq.push(iii(dp[u + nxt][nxt], ii(u + nxt, nxt)));
}
if(u - nxt >= 0 && dp[u - nxt][nxt] > dp[u][nxt] + 1) {
dp[u - nxt][nxt] = dp[u][nxt] + 1;
pq.push(iii(dp[u - nxt][nxt], ii(u - nxt, nxt)));
}
FORC(v, a[u]) {
if(u + v < n && dp[u + v][v] > dp[u][nxt] + 1) {
dp[u + v][v] = dp[u][nxt] + 1;
pq.push(iii(dp[u + v][v], ii(u + v, v)));
}
if(u - v >= 0 && dp[u - v][v] > dp[u][nxt] + 1) {
dp[u - v][v] = dp[u][nxt] + 1;
pq.push(iii(dp[u - v][v], ii(u - v, v)));
}
}
}
set <int> res;
REP(i, n) {
if(dp[1][i] != oo) res.insert(dp[1][i]);
}
if(res.size()) {
cout << *res.begin();
return;
} cout << 0;
}
signed main() {
lovethi
cin >> n >> m;
FOR(i, 1, m) {
int u, v;
cin >> u >> v;
a[u].pb(v);
}
bfs();
}
/*
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▄▀▀▀▀▄▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▀▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▀▄▄▄▄▀▒▒▒▒▒▒▒▒
▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▌░░▒▒▒▒▒▒▒▒▒▒▒▄▄▄▄▄▒▒▒▒▒▒▒▒▒
▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄███▀░░░░▒▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░▄█░░░░▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░▄████████▀░░░░▒▒▒▒▒▒▒▒▒█▀▀▀▀▒▒▒▒▒▒▒▒▒
▒▒░░░░░░░░░░░░░░░░░░░░░░░░▄█████████░░░░░░░▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░░░░░░▄███████▌░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░░░░▄█████████░░░░░░░░▒▒▒▒▒▒▒▒█▀▒▒▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░▄███████████▌░░░░░░░░▒▒▒▒▒▒▒▒█▒█▒▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░▄▄▄▄██████████████▌░░░░░░░░▒▒▒▒▒▒▒▒█▒▒█▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░▄▄███████████████████▌░░░░░░░░░▒▒▒▒▒▒▒▒█▒▒▒▄█▒▒▒▒▒▒▒▒
▒░░░░░░░░░▄██████████████████████▌░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░████████████████████████░░░░░░░░░░▒▒▒▒▒▒▒▒█▀▀▀▀▄▒▒▒▒▒▒▒▒
▒█░░░░░▐██████████▌░▀▀███████████░░░░░░░░░░▒▒▒▒▒▒▒▒█▄▄▄▄▀▒▒▒▒▒▒▒▒
▐██░░░▄██████████▌░░░░░░░░░▀██▐█▌░░░░░░░░░▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒██████░█████████ ░░░░░░░░░░▐█▐█▌░░░░░░░░░▒▒▒▒▒▒▒▒▒█▄▄▄▄▀▒▒▒▒▒▒▒▒
▒▒▀▀▀▀░░░██████▀░░░░░░░░░░░░▐█▐█▌░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒░░░░▐█████▌░░░░░░░░░░░░▐█▐█▌░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒░░░░███▀██░░░░░░░░░░░░░█░█▌░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒░▐██░░░██░░░░░░░░▄▄████████▄▄▄▄▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒██▌░░░░█▄░░░░░░▄███████████████████▄▄▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▐██▒▒░░░██▄▄████████████████████████████████████████████
▒▒▒▒▒▒▒▒▒▒▐██▒▒▄█████████████████████████████████████████████████
▒▒▒▒▒▒▒▒▒▒▄▄█████████████████████████████████████████████████████
█████████████████████████████████████████████████████████████████
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2380 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
