题目描述

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

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

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

现在你拥有 $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

2 1 1
1 2 no
2 1 no

• $n=2$ 次提问，总共有 $p_1=1$ 个天神，$p_2=1$ 个恶魔。
• 提问 1：问居民 1 “居民 2 是天神吗？”，回答“no”。
• 提问 2：问居民 2 “居民 1 是天神吗？”，回答“no”。
• 分析：假设 1 是天神，则他说真话 ⇒ 2 不是天神 ⇒ 2 是恶魔 ⇒ 2 说假话 ⇒ 1 不是天神，矛盾。假设 1 是恶魔，则他说假话 ⇒ 2 是天神 ⇒ 2 说真话 ⇒ 1 是天神，矛盾。所以信息矛盾或不足。
• 输出 no。

测试用例 2

3 2 1
1 1 yes
2 2 yes
3 3 yes

• $p_1=2$ 天神，$p_2=1$ 恶魔，共 3 人。
• 每个人被问自己是不是天神，都回答“yes”。
• 如果 1 是天神，他说真话 ⇒ 1 是天神，成立。
• 如果 1 是恶魔，他说假话 ⇒ 1 不是天神，即 1 是恶魔，成立。
• 同理，2 和 3 的身份无法唯一确定，因为有两种可能的分配方式（2 天 1 魔）满足条件。
• 输出 no。

测试用例 3

2 2 1
1 2 yes
2 3 no

• 总人数 $p_1 + p_2 = 3$，编号 1,2,3。
• 提问 1：1 说 2 是天神。
• 提问 2：2 说 3 不是天神。
• 分析：如果 1 是天神 ⇒ 2 是天神 ⇒ 2 说真话 ⇒ 3 不是天神 ⇒ 3 是恶魔。此时有 1,2 是天神（2 个），3 是恶魔（1 个），符合 $p_1=2, p_2=1$。
• 如果 1 是恶魔 ⇒ 1 说假话 ⇒ 2 不是天神 ⇒ 2 是恶魔 ⇒ 2 说假话 ⇒ 3 是天神。此时有 3 是天神，1,2 是恶魔，但 $p_1=2$ 不满足（只有 1 个天神）。所以只有第一种可能成立。
• 因此可以确定身份：1 和 2 是天神，3 是恶魔。
• 输出天神编号 1 和 2，然后 end。

测试用例 4

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

• 总人数 $p_1 + p_2 = 7$，编号 1~7。
• 通过约束可以唯一确定身份：天神是 3,4,5,6，恶魔是 1,2,7。
• 输出天神编号 3,4,5,6，然后 end。

数据范围

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

算法提示

这是一个逻辑推理问题，可以用 并查集 或 扩展域并查集 建模。

建模思路

对于每个居民 $i$，我们定义两个状态：

• $i_A$：表示 $i$ 是天神
• $i_B$：表示 $i$ 是恶魔

对于一次提问：向 $x$ 询问 $y$ 是不是天神，回答为 $ans$（yes 或 no）。

根据 $x$ 的身份和 $ans$ 可以推断 $y$ 的身份：

1. 如果 $x$ 是天神（说真话）：

   • $ans$ = yes ⇒ $y$ 是天神
   • $ans$ = no ⇒ $y$ 是恶魔

2. 如果 $x$ 是恶魔（说假话）：

   • $ans$ = yes ⇒ $y$ 不是天神 ⇒ $y$ 是恶魔
   • $ans$ = no ⇒ $y$ 是天神

总结规律：

• 当 $ans$ = yes 时，$x$ 和 $y$ 身份相同（同为天神或同为恶魔）。
• 当 $ans$ = no 时，$x$ 和 $y$ 身份相反。

这样，每个提问就给出了 $x$ 和 $y$ 身份相同或相反的关系。

算法步骤

1. 用扩展域并查集维护这些关系：每个居民 $i$ 对应两个节点 $i$（表示是天神）和 $i + N$（表示是恶魔）。
2. 对于每个提问 $(x, y, ans)$：
   • 如果 $ans$ = yes：合并 $(x, y)$，合并 $(x+N, y+N)$
   • 如果 $ans$ = no：合并 $(x, y+N)$，合并 $(x+N, y)$
3. 检查一致性：如果存在 $i$ 使得 $i$ 和 $i+N$ 在同一集合，则信息矛盾，输出 no。
4. 如果不矛盾，则根据连通分量统计可能的天神/恶魔分配方案数，用动态规划判断是否能唯一确定天神集合，且恰好有 $p_1$ 个天神。

输出

如果能唯一确定，升序输出天神编号，然后输出 end；否则输出 no。