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。

Sample Input

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

Sample Output

4

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int f[100010],dis[100010],num;
char s[5];
int findf(int x)
{
    if(f[x]==-1)
        return x;
    int temp=findf(f[x]);
    dis[x]=dis[x]+dis[f[x]];
    f[x]=temp;
    return temp;
}
int main()
{
    int n,m,a,b,a1,b1,flag=0;
    scanf("%d %d",&n,&m);
    memset(f,-1,sizeof(f));
    memset(dis,0,sizeof(dis));
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %s",&a,&b,s);
        a--;
        if(flag)
            continue;
        if(s[0]=='e')
            num=2;
        else num=1;

        a1=findf(a);
        b1=findf(b);
        if(a1!=b1)
        {
            f[b1]=a1;
            dis[b1]=dis[a]-dis[b]+num;
        }
        else if((dis[b]-dis[a])%2!=(num%2))
        {
            flag=i;
        }
    }
    if(flag)
        printf("%d\n",flag);
    else printf("-1\n");
    return 0;
}