如果$x$是天使,回答$y$为yes,那么y也是天使。
同理,yes时,$x,y$是同类,no时,$x,y$互为异类。
那么每一个集合中,都有与根是同类或异类的点,把这些点分成两个小集合。
之后进行背包,判断天使的可能方案,如果方案数为1,才有确切解。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int fa[N],d[N],pos[N];bool v[N];
int w0[N],w1[N];
int f[650][650],ans[N];
int get(int x)
{
    if(fa[x]==x)return x;
    int root=get(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=root;
}
/*
整体思路就是将各个并查集中的元素分为两类,然后背包处理求解,
f[i][j]表示前i个集合中好人(来自各个集合的w0[i],w0[j])有j个的方案数。
方程就是:f[i][j]=f[i-1][j-w0[i]+f[i-1][j-w1[i]];
*/
int main()
{
    //freopen("d1.in","r",stdin);
    //freopen("d1.ans","w",stdout);
    int n,p1,p2;
    while(scanf("%d%d%d",&n,&p1,&p2)&&(n+p1+p2))
    {
        memset(ans,0,sizeof(ans));
        memset(d,0,sizeof(d));memset(v,0,sizeof(v));
        memset(w0,0,sizeof(w0));memset(w1,0,sizeof(w1));
        memset(f,0,sizeof(f));
        for(int i=1;i<=p1+p2;i++)fa[i]=i;
        for(int i=1;i<=n;i++)
        {
            int x,y;char s[5];
            scanf("%d%d%s",&x,&y,&s);
            int p=get(x),q=get(y);fa[p]=q;
            if(s[0]=='y')d[p]=d[x]^d[y];
            else d[p]=d[x]^d[y]^1;
        }
        int cnt=0;
        for(int i=1;i<=p1+p2;i++)
            if(!v[i])
            {
                int p=get(i);++cnt;
                for(int j=1;j<=p1+p2;j++)
                    if(get(j)==p&&!v[j])
                    {
                        v[j]=1;
                        if(d[j])++w1[cnt];
                        else ++w0[cnt];
                    }
                pos[cnt]=p;
            }
        f[0][0]=1;
        for(int i=1;i<=cnt;i++)
        {
            int mn=min(w0[i],w1[i]);
            for(int j=p1+p2;j>=mn;j--)
                f[i][j]=f[i-1][j-w0[i]]+f[i-1][j-w1[i]];
        }
        if(f[cnt][p1]!=1){puts("no");continue;}
        int last=p1,len=0;
        for(int i=cnt;i>=1;i--)
            if(f[i-1][last-w0[i]]==1)
            {
                for(int j=1;j<=p1+p2;j++)
                    if(get(j)==pos[i]&&d[j]==0)ans[++len]=j;
                last-=w0[i];
            }
            else
            {
                for(int j=1;j<=p1+p2;j++)
                    if(get(j)==pos[i]&&d[j]==1)ans[++len]=j;
                last-=w1[i];
            }
        sort(ans+1,ans+len+1);
        for(int i=1;i<=len;i++)qw(ans[i]),puts("");
        puts("end");
    }
    return 0;
}