Parity

你的朋友写下一串包含1和0的串让你猜，你可以从中选择一个连续的子串（例如其中的第3到第5个数字）问他，该子串中包含了奇数个还是偶数个1，他会回答你的问题，然后你可以继续提问......你怀疑朋友的答案可能有错，或说同他之前的答案相互矛盾，例如：1 - 2 奇数，3 - 4 奇数，那么可以确定1 - 4 一定是偶数，如果你的朋友回答是奇数，就产生了矛盾。给出所有你朋友的答案，请你找出第一个出现矛盾的答案。

Input

第1行：2个数N, Q，N为串的长度，Q为询问的数量。（2 <= N <= 100000, 2 <= Q <= 50000)
第2 - Q + 1行：每行包括两个数以及一个字符串来描述朋友的回答，2个数中间用空格分隔，分别表示区间的起点和终点，后面的字符为"even"或"odd"，表示朋友的答案。

Output

输出1个数，表示朋友的答案中第一个错误答案的位置，如果所有答案均不矛盾，则输出-1。

Input示例

10 5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Output示例

4

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1e5;
int n, q, fa[MAXN * 2 + 5];

int getFather(int x)
{
    if (fa[x] != x)
    {
        fa[x] = getFather(fa[x]);
    }
    
    return fa[x];
}

int main()
{
    cin >> n >> q;
    for (int i = 0; i <= 2 * n; i++)
    {
        fa[i] = i;
    }
    
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        char ch[10];
        cin >> l >> r >> ch;
        int l1 = getFather(l - 1);
        int l2 = getFather(l - 1 + n);
        int r1 = getFather(r);
        int r2 = getFather(r + n);
        if (ch[0] == 'e')
        {
            if (l1 == r2 && l2 == r1)
            {
                cout << i << endl;
                return 0;
            }
            
            fa[l1] = r1;
            fa[l2] = r2;
        }
        else
        {
            if (l1 == r1 && l2 == r2) 
            {
                cout << i << endl;
                return 0;
            }
            
            fa[l1] = r2;
            fa[l2] = r1;
        }
    }
    
    cout << -1 << endl;
    return 0;
}