題目：給出p1+p2個人，其中p1個是好人，p2個是壞人。然後有一些關系 ，a說b是好人(壞人).其中沒有矛盾的，判斷是否有唯一解判斷哪些人是好人，哪些人是壞人。
其中比較重要的是，好人總說真話，壞人總說假話。不需要判斷矛盾。
其中好人說真話，壞人說假話這點很重要。
那麼如果一個人說另一個人是好人，那麼如果這個人是好人，說明 對方確實是好人，如果這個是壞人，說明這句話是假的，對方也是壞人。
如果一個人說另一個人是壞人，那麼如果這個人是好人，說明對方是壞人，如果這個是壞人，說明 對方是好人。
也就是如果條件是yes說明這兩個是相同集合的，否則是兩個不同的集合。
用r[i]表示i結點與根結點的關系，0為相同集合，1為不同集合。這是一個經典的並查集問題。
這樣處理之後，還需要判斷是否唯一
我們通過並查集，可以將所有人分為若干個集合，其中對於每一個集合，又分為兩個集合（好人和壞人，但是不知道哪些是好人，哪些是壞人，我們只有相對關系）
接下來就是從所有大集合中的兩個小集合取一個，組成好人集合，判斷是否唯一。
背包問題，dp[i][j]表示前i個大集合，好人為j個的方案有多少種，或者dp[i][j]表示當前好人i個，壞人j個的情況有多少種
如果dp[cnt][p1]！=1說明方案不唯一，或者無解。
如果為1題目還需要輸出方案，這點比較糾結。用後一種DP的時候WA了好多次，而這題又卡內存，不能開三維數組，其實可以兩次DP解決。
後來采用前者DP，不斷從dp[cnt][p1]往前遞推，遞推的結果也必須是某個前趨狀態的dp值為1.
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 60005
#define N 605
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
using namespace std;
int pre[N],r[N];
int p1,p2,p;
bool vis[N];
int dp[N][N/2];
int cnt; //最後分為幾個集合
int a[N][2]; //a[i][0],a[i][1]分別表示把第i個集合分成的兩個部分
vector<int> b[N][2];
int find(int x)
{
if(x!=pre[x])
{
int f=pre[x];
pre[x]=find(pre[x]);
r[x]=r[x]^r[f];
}
return pre[x];
}
void Init()
{
for(int i=1; i<=p1+p2; i++) pre[i]=i,r[i]=0;
mem(vis,false);
cnt=1;
mem(a,0);
for(int i=0; i<N; i++)
{
b[i][0].clear();
b[i][1].clear();
}
}
int main()
{
while(scanf("%d%d%d",&p,&p1,&p2)!=EOF&&p+p1+p2)
{
Init();
while(p--)
{
int u,v;
char str[10];
scanf("%d%d%s",&u,&v,str);
int k=(str[0]=='n');
int ra=find(u),rb=find(v);
if(ra!=rb)
{
pre[ra]=rb;
r[ra]=r[u]^r[v]^k;
}
}
for(int i=1; i<=p1+p2; i++)
{
if(!vis[i])
{
int f=find(i);
for(int j=i; j<=p1+p2; j++)
{
if(find(j)==f)
{
vis[j]=true;
b[cnt][r[j]].pb(j);
a[cnt][r[j]]++;
}
}
cnt++;
}
}
mem(dp,0);
dp[0][0]=1;
for(int i=1; i<cnt; i++)
{
for(int j=p1; j>=0; j--)
{
if(j-a[i][0]>=0)
dp[i][j]+=dp[i-1][j-a[i][0]];
if(j-a[i][1]>=0)
dp[i][j]+=dp[i-1][j-a[i][1]];
}
}
if(dp[cnt-1][p1]!=1)
{
printf("no\n");
continue;
}
else
{
vector<int>ans;
ans.clear();
for(int i=cnt-1; i>=1; i--)
{
if(p1-a[i][0]>=0&&p2-a[i][1]>=0&&dp[i-1][p1-a[i][0]]==1)
{
for(int j=0; j<b[i][0].size(); j++)
{
ans.pb(b[i][0][j]);
}
p1-=a[i][0];
p2-=a[i][1];
}
else if(p1-a[i][1]>=0&&p2-a[i][0]>=0&&dp[i-1][p1-a[i][1]]==1)
{
for(int j=0; j<b[i][1].size(); j++)
{
ans.pb(b[i][1][j]);
}
p1-=a[i][1];
p2-=a[i][0];
}
}
sort(ans.begin(),ans.end());
for(int i=0; i<ans.size(); i++) printf("%d\n",ans[i]);
printf("end\n");
}
}
return 0;
}
