题目描述

一个岛上存在着两种居民，一种是天神，一种是恶魔。

天神永远都不会说假话，而恶魔永远都不会说真话。

岛上的每一个成员都有一个整数编号（类似于身份证号，用以区分每个成员）。

现在你拥有n次提问的机会，但是问题的内容只能是向其中一个居民询问另一个居民是否是天神，请你根据收集的回答判断各个居民的身份。

输入格式

输入包含多组测试用例。

每组测试用例的第一行包含三个非负整数n,$p_1,p_2$，其中n是你可以提问的总次数，$p_1$是天神的总数量，$p_2$是恶魔的总数量。

接下来n行每行包含两个整数$x_i,y_i$以及一个字符串$a_i$，其中$x_i,y_i$是岛上居民的编号，你将向编号为$x_i$的居民询问编号为$y_i$的居民是否是天神，

$a_i$是他的回答，如果$a_i$为“yes”，表示他回答你“是”，如果$a_i$为“no”，表示他回答你“不是”。

$x_i,y_i$可能相同，表示你问的是那个人自己是否为天神。

当输入为占据一行的“0 0 0”时，表示输入终止。

输出格式

对于每组测试用例，如果询问得到的信息足以使你判断每个居民的身份，则将所有天神的编号输出，每个编号占一行，在输出结束后，在另起一行输出“end”，表示该用例输出结束。

如果得到的信息不足以判断每个居民的身份，则输出“no”，输出同样占一行。

数据范围

$1 \le x_i,y_i \le q_1+q_2$,
$0 \le n < 1000, 0 \le p_1,p_2 < 300$

输入样例：

2 1 1
1 2 no
2 1 no
3 2 1
1 1 yes
2 2 yes
3 3 yes
2 2 1
1 2 yes
2 3 no
5 4 3
1 2 yes
1 3 no
4 5 yes
5 6 yes
6 7 no
0 0 0

输出样例：

no
no
1
2
end
3
4
5
6
end

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解