#include #include int n, p1, p2, p; int gr[600], attr[600], n_gr, m_gr[600][2], truth[600], truthsav[600], found; int sub(int x, int sp1, int sp2) { int i, j, r; if (x == n_gr) { /*for (i = 0; i < n_gr; i++) printf("%d ", truth[i]);*/ /*printf("%d,%d\n", sp1, sp2);*/ if (found) return -1; found = 1; for (i = 0; i < n_gr; i++) { truthsav[i] = truth[i]; } return 1; } for (i = 0; i < 2; i++) { j = 1-i; if (sp1+m_gr[x][j] <= p1 && sp2+m_gr[x][i] <= p2) { truth[x] = j; r = sub(x+1, sp1+m_gr[x][j], sp2+m_gr[x][i]); if (r == -1) return -1; } } return 0; } int chk() { int i, j; for (i = 0; i < n_gr; i++) { if (m_gr[i][0] == m_gr[i][1]) return 0; for (j = i+1; j < n_gr; j++) { if (m_gr[i][0] == m_gr[j][0] && m_gr[i][1] == m_gr[j][1]) return 0; if (m_gr[i][0] == m_gr[j][1] && m_gr[i][1] == m_gr[j][0]) return 0; } } return 1; } 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. */ for (i = 0; i < 600; i++) { gr[i] = i-1; attr[i] = 1; m_gr[i][0] = 0; m_gr[i][1] = 1; } p = n_gr = p1+p2; found = 0; /* input / grouping */ for (i = 0; i < n; i++) { int x, y, tr, gx, gy; char str[10]; fscanf(fp, "%d%d%s", &x, &y, str); tr = ((str[0] == 'y') ? 1 : 0); gx = gr[x]; gy = gr[y]; if (gx != gy) { int inv = (attr[x] == attr[y]) ^ tr; for (j = 1; j <= p; j++) { if (gr[j] == gy) { gr[j] = gr[x]; if (inv) attr[j] = !attr[j]; } } if (inv) { m_gr[gr[x]][0] += m_gr[gy][1]; m_gr[gr[x]][1] += m_gr[gy][0]; } else { m_gr[gr[x]][0] += m_gr[gy][0]; m_gr[gr[x]][1] += m_gr[gy][1]; } n_gr--; if (n_gr != gy) { for (j = 1; j <= p; j++) { if (gr[j] == n_gr) gr[j] = gy; } m_gr[gy][0] = m_gr[n_gr][0]; m_gr[gy][1] = m_gr[n_gr][1]; } } } /*for (i = 0; i < n_gr; i++) printf("(%d %d)", m_gr[i][0], m_gr[i][1]);*/ if (chk() && sub(0,0,0) != -1 && found) { int lst[600]; j = 0; for (i = 1; i <= p; i++) { if (attr[i] == truthsav[gr[i]]) { printf("%d\n", i); } } printf("end\n"); } else { printf("no\n"); } } return 0; }