小A和小B在玩一个游戏。
首先，小A写了一个由0和1组成的序列S，长度为N。
然后，小B向小A提出了M个问题。
在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。
机智的小B发现小A有可能在撒谎。
例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。
请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。
即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。
#include<bits/stdc++.h> #define N 40010 #define M N/2 using namespace std; int n,m; int fa[N],d[N]; map<int,int>s; int get(int x) { if(s.count(x)==0)s[x]=++n; return s[x]; } int found(int x) { if (fa[x]!=x) fa[x]=found(fa[x]); return fa[x]; } int main() { cin>>n>>m;n=0; int a,b;string type; for(int i=0;i<N;i++)fa[i]=i; for(int i=1;i<=m;i++) { cin>>a>>b>>type; a=get(a-1),b=get(b); if(type=="even") { if(found(a+M)==found(b)){cout<<i-1;return 0;} fa[found(a)]=found(b); fa[found(a+M)]=found(b+M); } else { if(found(a)==found(b)){cout<<i-1;return 0;} fa[found(a+M)]=found(b); fa[found(a)]=found(b+M); } } cout<<m; return 0; }