记录编号	593677	评测结果	A
题目名称	[POJ 1417]真正的说谎者	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2024-09-07 22:11:38	内存使用	39.32 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,p,q;
struct DSU{
	int fa[N];
	void build(){for(int i = 1;i <= n * 2;i++)fa[i] = i;}
	int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
	bool merge(int x,int y){
		x = find(x),y = find(y);
		if(x == y)return 1;
		return fa[x] = y,0;
	}
}U;


char op[10];
pii la[2010][310];
ll now[2010],s[2010],f[2010][2010];
bool v[N];
void work(){
	memset(s,0,sizeof s);
	memset(now,0,sizeof now);
	memset(v,0,sizeof v);
	memset(la,0,sizeof la);
	memset(f,0,sizeof f);
	n = p + q;
	U.build();
	for(int i = 1;i <= m;i++){
		int x = read(),y = read();
		scanf("%s",op);
		if(op[0] == 'n')U.merge(x,y + n),U.merge(x + n,y);
		else U.merge(x,y),U.merge(x + n,y + n);
	}
	for(int i = 1;i <= n;i++)
		if(U.find(i) == U.find(i + n))return printf("no\n"),void();
	for(int i = 1;i <= n;i++)s[U.find(i)]++;
	int cnt = 0;
	memset(f,0,sizeof f);
	f[0][0] = 1;
	for(int x = 1;x <= n;x++){
		if(x != U.find(x))continue;
		cnt++;
		now[cnt] = x;
		int s1 = 0,s2 = 0;
		for(int i = 0;i <= n;i++){
			if(i >= s[x] && f[cnt-1][i - s[x]]){
				f[cnt][i] += f[cnt-1][i - s[x]];
				la[cnt][i] = {i-s[x],0};
			}
			if(i >= s[x + n] && f[cnt-1][i - s[x + n]]){
				f[cnt][i] += f[cnt-1][i - s[x + n]];
				la[cnt][i] = {i-s[x + n],1};
			}
		}
	}
	if(f[cnt][p] != 1)return printf("no\n"),void();
	pii x = la[cnt][p];
	for(int i = cnt;i >= 1;i--){
		if(x.se == 0)v[now[i]] = 1;
		else v[now[i] + n] = 1;
		x = la[i-1][x.fi];
	}
	for(int i = 1;i <= n;i++)	
		if(v[U.find(i)])printf("%d\n",i);
	printf("end\n");
}
int main(){
	freopen("trueliars.in","r",stdin);
	freopen("trueliars.out","w",stdout);
	while(1){
		m = read(),p = read(),q = read();
		if(!m && !p && !q)break;
		work();
	}

	return 0;

}