#include #include struct TT { int x, num; }; signed char mat[600][600]; int n_ans[600]; /* num. of be answered */ struct TT tt[600]; int truth[600], truthsav[600]; int n, p1, p2, p, np1, np2, found; int sub2(); int qsortsub(const void *a, const void *b) { return ((const struct TT*)b)->num - ((const struct TT*)a)->num; } int sub(int x, int tr) { int i, result; /* printf("** %d %d\n", x, tr);*/ if (tr == 1) { if (np1 == p1) return 0; } else { if (np2 == p2) return 0; } for (i = 1; i <= p; i++) { if (truth[i]) { if ((truth[i] * mat[i][x] * tr == -1) || tr * mat[x][i] * truth[i] == -1) { return 0; } } } truth[x] = tr; if (np1+np2 == p-1) { if (found) return -1; for (i = 1; i <= p; i++) { truthsav[i] = truth[i]; } found = 1; truth[x] = 0; return 1; } if (tr == 1) { np1++; } else { np2++; } result = sub2(); if (result == -1) return -1; if (tr == 1) { np1--; } else { np2--; } truth[x] = 0; return result; } int sub2() { int i; for (i = 0; i < p; i++) { int result; if (truth[tt[i].x]) continue; result = sub(tt[i].x, 1); if (result == -1) return -1; result = sub(tt[i].x, -1); return result; } } int main() { FILE *fp = fopen("liar.txt", "r"); while (fscanf(fp, "%d%d%d", &n, &p1, &p2) == 3) { int i, j; if (n == 0 && p1 == 0 && p2 == 0) break; /* init. */ p = p1+p2; for (i = 0; i < 600; i++) { for (j = 0; j < 600; j++) { mat[i][j] = 0; } truth[i] = n_ans[i] = 0; } np1 = np2 = 0; found = 0; /* input */ for (i = 0; i < n; i++) { int x, y; char str[10]; fscanf(fp, "%d%d%s", &x, &y, str); mat[x][y] = ((str[0] == 'y') ? 1 : -1); n_ans[x]++; } for (i = 1; i <= p; i++) { tt[i-1].x = i; tt[i-1].num = n_ans[i]; } qsort(tt, p1+p2, sizeof(struct TT), qsortsub); if (sub2() != -1 && found) { for (i = 1; i <= p; i++) { if (truthsav[i] == 1) printf("%d\n", i); } printf("end\n"); } else { printf("no\n"); } } return 0; }