/*
 * Copyright (c) 2004 Kamo Hiroyasu
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 *  A solution of "True Liar"
 *   Author: Kamo Hiroyasu <wd@ics.nara-wu.ac.jp>
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef DEBUG
#define INPUT_FILE	"/dev/stdin"
#else
#define INPUT_FILE	"liar.txt"
#endif

#define NMAX	999
#define P1MAX	299
#define P2MAX	299
#define PMAX	(P1MAX + P2MAX)
#define D_YES	1
#define D_NO	(-1)

static inline int
min(int x, int y)
{
	return x < y ? x : y;
}

void
read_answers(int n, FILE *fp,
	     int num_tribes, signed char answers[num_tribes][num_tribes])
{
	int	x, y;
	char	s[4];
	int	i;

	memset(answers, 0, num_tribes * num_tribes * sizeof(answers[0][0]));
	for (i = 0; i < n; i ++) {
		fscanf(fp, "%d%d%3s", &x, &y, s);
		if (strcmp(s, "yes") == 0) {
			answers[x - 1][y - 1] = answers[y - 1][x - 1] = D_YES;
		} else if (strcmp(s, "no") == 0) {
			answers[x - 1][y - 1] = answers[y - 1][x - 1] = D_NO;
		}
	}
}

void
group_search(int n, int g, int *grouping,
	     int num_tribes, signed char answers[num_tribes][num_tribes])
{
	int	i;

	grouping[n] = g;
	for (i = 0; i < num_tribes; i ++) {
		if (grouping[i] == 0 && answers[n][i] != 0) {
			group_search(i, answers[n][i] * g, grouping,
				     num_tribes, answers);
		}
	}
}

void
group_tribes(int num_tribes, signed char answers[num_tribes][num_tribes],
	     int *grouping, int *num_groups)
{
	int	i;
	int	n;

	memset(grouping, 0, num_tribes * sizeof(grouping[0]));
	n = 0;
	for (i = 0; i < num_tribes; i ++) {
		if (grouping[i] == 0) {
			n ++;
			group_search(i, n, grouping, num_tribes, answers);
		}
	}
	*num_groups = n;
}

int
collect_devine(int num_tribes, int num_devine,
	       const int *grouping, int num_groups, int *devine)
{
	int	populations[num_groups][2];
	char	smaller[num_groups];
	char	table[num_devine + 1];
	char	bitmap[num_devine + 1][num_groups];
	int	p_min;
	int	delta;
	int	i;
	int	j;
	int	k;

	memset(populations, 0, sizeof(populations));
	for (i = 0; i < num_tribes; i ++) {
		populations[abs(grouping[i]) - 1][grouping[i] <= 0] ++;
	}
	p_min = 0;
	for (j = 0; j < num_groups; j ++) {
		smaller[j] = (populations[j][0] > populations[j][1]);
		p_min += populations[j][smaller[j]];
	}
	memset(table, 0, sizeof(table));
	table[p_min] = 1;
	memset(bitmap, 0, sizeof(bitmap));
	for (j = 0; j < num_groups; j ++) {
		delta = abs(populations[j][0] - populations[j][1]);
		for (k = num_devine - delta; k >= p_min; k --) {
			table[k + delta] = min(2, table[k + delta] + table[k]);
			if (table[k] == 1 && table[k + delta] == 1) {
				memcpy(bitmap[k + delta], bitmap[k], j);
				bitmap[k + delta][j] = 1;
			}
		}
	}
	if (table[num_devine] == 2) {
		return 0;
	} else {
		k = 0;
		for (i = 0; i < num_tribes; i ++) {
			int	index;

			index = abs(grouping[i]) - 1;
			if ((bitmap[num_devine][index] ^ smaller[index]
			     ^ (grouping[i] <= 0)) == 0) {
				devine[k] = i + 1;
				k ++;
			}
		}
		return 1;
	}
}

void
liar(int num_answers, int num_tribes, int num_devine, FILE *fp)
{
	signed char	answers[num_tribes][num_tribes];
	int		num_groups;
	int		grouping[num_tribes];
	int		devine[num_devine];
	int		i;

	read_answers(num_answers, fp, num_tribes, answers);
	group_tribes(num_tribes, answers, grouping, &num_groups);
	if (collect_devine(num_tribes, num_devine,
			   grouping, num_groups, devine)) {
		for (i = 0; i < num_devine; i ++) {
			printf("%d\n", devine[i]);
		}
		printf("end\n");
	} else {
		printf("no\n");
	}
}

main(int argc, char *argv[])
{
	const char	*path = INPUT_FILE;
	FILE		*fp;
	int		n;
	int		p1, p2;
	int		i;

	switch (argc) {
	case 2:
		path = argv[1];
	case 1:
		break;
	default:
		fprintf(stderr, "%s: too many arguments\n", argv[0]);
		return 1;
	}
	if ((fp = fopen(path, "r")) == NULL) {
		perror(path);
		return 1;
	}
	while(fscanf(fp, "%d%d%d", &n, &p1, &p2) == 3
	      && n <= NMAX && p1 <= P1MAX && p2 <= P2MAX
	      && !(n == 0 && p1 == 0 && p2 == 0)) {
		liar(n, p1 + p2, p1, fp);
	}
	return 0;
}