#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
vector<pair<int, int> > g[N];
bool vis[N][2];
struct S {
  int node;
  int st;
  int a, b;
  S(int node, int st, int a, int b) {
    this->a = a;
    this->b = b;
    this->node = node;
    this->st = st;
  }
  bool operator<(const S& other) const {
    if (a == other.a) return b > other.b;
    return a > other.a;
  }
};
priority_queue<S> q;
bool vis2[N][20];
struct S2 {
  int node;
  int val;
  int cost;
  S2(int node, int val, int cost) {
    this->val = val;
    this->cost = cost;
    this->node = node;
  }
  bool operator<(const S2& other) const { return (cost > other.cost); }
};
priority_queue<S2> q2;
int main() {
  scanf("%d%d", &n, &m);
  for (int u, v, i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    g[u].push_back(make_pair(v, 0));
    g[v].push_back(make_pair(u, 1));
  }
  q.push(S(1, 0, 0, 0));
  int node;
  int st;
  int a, b;
  while (!q.empty()) {
    node = q.top().node;
    st = q.top().st;
    a = q.top().a;
    b = q.top().b;
    q.pop();
    if (vis[node][st]) continue;
    vis[node][st] = true;
    if (node == n) break;
    if (!vis[node][st ^ 1]) q.push(S(node, st ^ 1, a + 1, b));
    for (int i = 0; i < (int)g[node].size(); i++) {
      if (g[node][i].second != st) continue;
      if (!vis[g[node][i].first][st]) q.push(S(g[node][i].first, st, a, b + 1));
    }
  }
  if (a >= 20) {
    int ans = b;
    int cur = 1;
    for (int i = 0; i < a; i++) {
      ans += cur;
      if (ans >= 998244353) ans -= 998244353;
      cur += cur;
      if (cur >= 998244353) cur -= 998244353;
    }
    printf("%d\n", ans);
    return 0;
  }
  int ans = b;
  for (int i = 0; i < a; i++) {
    ans += (1 << i);
  }
  q2.push(S2(1, 0, 0));
  int val, cost;
  while (!q2.empty()) {
    node = q2.top().node;
    cost = q2.top().cost;
    val = q2.top().val;
    q2.pop();
    if (vis2[node][val]) continue;
    vis2[node][val] = true;
    if (node == n) ans = min(ans, cost);
    if (val + 1 < 20 && !vis2[node][val + 1])
      q2.push(S2(node, val + 1, cost + (1 << val)));
    for (int i = 0; i < (int)g[node].size(); i++) {
      if (g[node][i].second != (val & 1)) continue;
      if (!vis2[g[node][i].first][val])
        q2.push(S2(g[node][i].first, val, cost + 1));
    }
  }
  cout << ans << endl;
  return 0;
}
