#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 100010
#define qmod(x) (x>mod?x-mod:x)
#define id(x,y) ((x - 1) * n + y)
inline ll read(){
    ll x = 0,f = 1;
    char c = getchar();
    while(c < '0'||c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0'&&c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
vector <ll> vec;
struct node_qs{
    ll l,r,w;
}qs[MAXN];
ll n,q;


struct node_dsu{
    ll fa[MAXN];
    void make(ll x){
        for(int i = 0;i <= x; ++i)fa[i] = i;
    }
    ll get(ll x){
        if(fa[x] == x)return x;
        else return fa[x] = get(fa[x]);
    }
    void merge(ll x, ll y){
        x = get(x);
        y = get(y);
        if(x == y)return;
        fa[x] = y;
    }
}dsu;


int main(){
    freopen("parity.in", "r", stdin);
    freopen("parity.out", "w", stdout);
    n = read(),q = read();
    for(int i = 1;i <= q; ++i){
        qs[i].l = read();
        qs[i].r = read();
        vec.push_back(qs[i].l - 1);
        vec.push_back(qs[i].r);
    }
    vec.push_back(0);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    n = vec.size() - 1;
    dsu.make(n * 2);
    for(int i = 1;i <= q; ++i){
        ll l = lower_bound(vec.begin(), vec.end(), qs[i].l - 1) - vec.begin();
        ll r = lower_bound(vec.begin(), vec.end(), qs[i].r) - vec.begin(); 
        // cout << l << " " << r << endl;
        if(qs[i].w == 1){
            if(dsu.get(id(1,l)) == dsu.get(id(1,r))){
                cout << i - 1;
                return 0;
            }
            dsu.merge(id(1,l), id(1,r));
            dsu.merge(id(2,l), id(2,r));
        }else{
            if(dsu.get(id(1,l)) == dsu.get(id(2,r))){
                cout << i - 1;
                return 0;
            }
            dsu.merge(id(1,l), id(2,r));
            dsu.merge(id(2,l), id(1,r));
        }
    }
    cout << n << endl;
    return 0;
}