记录编号	585245	评测结果	AAAAAAAAAA
题目名称	[CEOI 1999] 奇偶性游戏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-12-02 10:24:11	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
//并查集题集 
#define ll long long
const int N = 2e4+10;
int n,m;
int c[N],cnt,fa[N];
struct made{
	int l,r,op;
}a[N];
int find(int x){
	if(x == fa[x])return x;
	return fa[x] = find(fa[x]);
}
void merge(int x,int y){
	x = find(x),y = find(y);
	if(x == y)return;
	fa[x] = y;
}
int main(){
	freopen("parity.in","r",stdin);
	freopen("parity.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		char ch[10];
		scanf("%d%d%s",&a[i].l,&a[i].r,ch);
		a[i].op = ch[0] == 'o';
		c[++cnt] = a[i].l-1,c[++cnt] = a[i].r;
	}
	sort(c+1,c+1+cnt);
	n = unique(c+1,c+1+cnt) - (c+1);
	for(int i = 1;i <= 2*n;i++)fa[i] = i;
	for(int i = 1;i <= m;i++){
		int l = lower_bound(c+1,c+1+n,a[i].l-1) - c;
		int r = lower_bound(c+1,c+1+n,a[i].r) - c;
		if(a[i].op){
			if(find(l) == find(r)){
				printf("%d\n",i-1);
				return 0;
			}
			merge(l,r+n);
			merge(l+n,r);
		}
		else{
			if(find(l+n) == find(r)){
				printf("%d\n",i-1);
				return 0;
			}
			merge(l,r);
			merge(l+n,r+n);
		}
	}
	printf("%d\n",m);
	
	return 0;
}