带权并查集
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=10010;
typedef pair<int,int> PII;
unordered_map<int,int> S;
int n,m;
int p[N],d[N];
int get(int x)
{
if(!S.count(x))S[x]=++n;
return S[x];
}
int find(int x)
{
if(p[x]!=x)
{
int root=find(p[x]);//递归调用,注意是p[x]
d[x]^=d[p[x]];
p[x]=root;
}
return p[x];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
n=0;
int res=m;
for(int i=0;i<N;i++)p[i]=i;
for(int i=1;i<=m;i++)
{
int a,b;
string s;
cin>>a>>b>>s;
int t=(s=="odd");
a=get(a-1),b=get(b);
int pa=find(a),pb=find(b);
if(pa==pb)
{
if(d[a]^d[b]!=t)
{
res=i-1;
break;
}
}
else
{
p[pb]=pa;
d[pb]=d[a]^d[b]^t;
}
}
cout<<res<<endl;
return 0;
}