#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
using namespace std;

using ll = long long;

vector<int> fen(100'001);

void add(int i, int num) {
    while (i != 0) {
        fen[i] += num;
        i -= i & -i;
    }
}

int ask(int i) {
    int res = 0;
    while (i > 0) {
        res += fen[i];
        i -= i & -i;
    }
    return res;
}
int subsequence(int a, int b) {
    return ask(b) - ask(a-1);
}

vector<bool> wars;

void binary(int a, int b) {
    if(a-b == 0) {
        add(a, 1);
        wars[a] = 1;
        return;
    }
    int summ = subsequence(a, b);
    if(summ == 0) {
        for(int i = a; i <= b; i++) {
            add(i, 1);
            wars[i] = 1;
        }
        return;
    }
    else if(a-b+1 != summ) {
        int half = (a+b+1)/2;
        binary(half, b);
        binary(a, half-1);
    } else return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    wars.resize(n+1);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        binary(a, b);
    }

    int maxx = 0;
    int first = -1;
    int run = 0;
    for(int i = 1; i <= n; i++) {
        if(wars[i]) {
            run = 0;
        } else {
            run++;
            if(maxx < run) {
                maxx = run;
                first = i-run+1;
            }
        }
    }
    if(first == -1) cout << "-1\n";
    else cout << maxx << " " << first;
    return 0;
}