k.cpp

#include <cassert>
#include <cstring>

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAXN = 1e6 + 123;

vector<int> E[MAXN];

int nc, ni;
int maxjump[MAXN];

struct Ret { int k, min_range_start, min_range_len; };

Ret solve(int start) {
  int dist = 0;
  int k = 0;

  int min_L = 1e9;
  int min_x = -123;

  for (int pos = start; dist < nc; ) {
    int L = maxjump[pos];
    if (L < min_L) tie(min_L, min_x) = make_tuple(L, pos);
    tie(pos, dist, k) = make_tuple((pos+L)%nc, dist+L, k+1);
  }

  return {k, min_x, min_L};
}

int main(void)
{
  scanf("%d %d", &nc, &ni);
  int init_jump = 0;

  REP(i, ni) {
    int a, b; scanf("%d %d", &a, &b); --a;
    if (a >= b) {
      init_jump = max(init_jump, b);
      E[a].push_back(b+nc-a);
    } else {
      E[a].push_back(b-a);
    }
  }

  int j = init_jump;
  REP(i, nc) {
    for (int len : E[i]) j = max(j, len);
    if (j > 0) maxjump[i] = j--;
    else { puts("impossible"); exit(0); }
  }

  auto init = solve(0);
  int ans = init.k;
  REP(ib, init.min_range_len+1) {
    int val = solve((init.min_range_start + ib) % nc).k;
    ans = min(ans, val);
  }

  printf("%d\n", ans);
  return 0;
}