将区间x~y中1个数是偶数还是奇数转变成1~x-1和1~y两个区间里面的奇偶性相反的问题。然后通过扩展域并查集求解。 
#include <bits/stdc++.h>


using namespace std;

unordered_map<int, int> mp;

int find(int x) {
    return x==mp[x]? x : mp[x]=find(mp[x]);
}

void Merge(int x, int y) {
    mp[find(x)] = find(y);
}

int main() {
    int n, m;
    cin>>n>>m;
    n++;
    int i;
    int x1, y1;
    string op;
//     mp[2] = 2;
    for (i=0; i<m;i++) {
        cin>>x1>>y1;
        if (!mp.count(x1-1)) {
//             cout<<"s"<<endl;
            mp[x1-1] = x1-1;
            mp[x1+n-1] = x1+n-1;
        }
//         cout<<(mp.find(y)!=mp.end())<<endl;
        if (!mp.count(y1)) {
//             cout<<"s"<<endl;
            mp[y1] = y1;
            mp[y1+n] = y1+n;
        }
        cin>>op;
        if (op=="even") {
            if (find(x1-1)==find(y1+n)) {
                break;
            }
            Merge(x1-1, y1);
            Merge(x1+n-1, y1+n);
        } else {
            if (find(x1-1)==find(y1)) break;
            Merge(x1-1, y1+n);
            Merge(x1+n-1, y1);
        }
    }
    cout<<i;
    
    return 0;
}