边带权比较好做，然后dp方案
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
int n, pu, pv, uu, vv, fa[605], gx[605], cnt, bel1[605], bel2[605], dp[605][305];
char ss[15];
vector<int> vec[605][2], ans;
int myfind(int x){
if(x==fa[x]) return x;
int t=myfind(fa[x]);
gx[x] ^= gx[fa[x]];
fa[x] = t;
return t;
}
int main(){
while(scanf("%d %d %d", &n, &pu, &pv)!=EOF){
if(!n && !pu && !pv) break;
for(int i=1; i<=pu+pv; i++){
fa[i] = i;
gx[i] = 0;
}
for(int i=1; i<=cnt; i++) vec[i][0].clear(), vec[i][1].clear();
ans.clear();
cnt = 0;
for(int i=1; i<=n; i++){
scanf("%d %d %s", &uu, &vv, ss);
int p=myfind(uu), q=myfind(vv);
if(p==q) continue;
gx[p] = gx[uu] ^ gx[vv] ^ (ss[0]=='n');
fa[p] = q;
}
for(int i=1; i<=pu+pv; i++)
if(fa[i]==i){
bel1[i] = ++cnt;
bel2[i] = 0;
vec[cnt][0].push_back(i);
}
for(int i=1; i<=pu+pv; i++)
if(fa[i]!=i){
int p=myfind(i);
int q=gx[i]^bel2[p];
vec[bel1[p]][q].push_back(i);
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i=1; i<=cnt; i++)
for(int j=0; j<=pu; j++){
if(j>=vec[i][0].size()) dp[i][j] += dp[i-1][j-vec[i][0].size()];
if(j>=vec[i][1].size()) dp[i][j] += dp[i-1][j-vec[i][1].size()];
}
if(dp[cnt][pu]!=1) printf("no
");
else{
for(int i=cnt; i>=1; i--){
int p=vec[i][0].size(), q=vec[i][1].size();
if(dp[i-1][pu-p]==1){
pu -= p;
for(int j=0; j<p; j++) ans.push_back(vec[i][0][j]);
}
else{
pu -= q;
for(int j=0; j<q; j++) ans.push_back(vec[i][1][j]);
}
}
sort(ans.begin(), ans.end());
int p=ans.size();
for(int i=0; i<p; i++) printf("%d
", ans[i]);
printf("end
");
}
}
return 0;
}