题目描述

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

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

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

现在你拥有 $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，输出同样占一行。

样例

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

数据范围

$1≤x_i,y_i≤p_1+p_2, 0≤n<1000,0≤p_1,p_2<300$

来源

• POJ1417
• 算法竞赛进阶指南