在著名的电子游戏《Wizards & Wyvern》中,主角发现自己身处某种迷宫结构中,必须找到出路。每一层关卡都由若干洞穴、平台、房间或其他有趣的地点组成,这些地点通过不同类型的路径相连。在每个地点,都有一个独特且可辨识的文物,英雄可以激活它。为了逃离某一层,玩家必须按正确的顺序激活正确的文物。隐藏在迷宫中的谜题可以帮助他通关。
第一个样例的迷宫概览。
你讨厌谜题,因此从网上获取了一张单层关卡的地图及其解法。你只需要找出这张地图是否代表你当前所在的关卡。
在地点之间穿梭时,玩家可以看到当前地点的文物以及所有通往外部的路径。游戏实现了 26 种不同类型的路径,例如铺砌道路(P)、桥梁(B)或土路(D)。在每个地点,所有通往外部的路径类型各不相同。
这是一个交互式问题。你不知道你的初始位置,但你总是可以决定走哪条路径。对于你访问的每个地点,你都会获知该处的文物名称以及通往外部的路径类型。你的任务是找出该关卡是否与你地图上的关卡匹配。
交互协议
你的程序将与一个名为 grader 的特殊程序进行交互。这意味着你的程序的输出会被发送给 grader,而 grader 的输出会被发送到你程序的标准输入。这种交互必须遵循特定的协议:
grader 首先发送地图的描述:
一个整数 $n$ ($2 \le n \le 1\,000$),表示地图上的地点数量。
$n$ 行,第 $i$ 行包含一个整数 $k$,后跟 $k$ 个对 $t_1 m_1, \dots, t_k m_k$,描述从地点 $i$ 通往外部的路径。每条路径由其类型 $t_j$($t_j$ 为大写字母)和目的地 $m_j$ ($1 \le m_j \le n, m_j \neq i$) 给出。
所有路径都是双向的,且在输入中出现两次,即每个方向各一次。你可以确信迷宫中所有地点都是从任何位置可达的。
随后,游戏按回合进行。在每一回合中,grader 会按以下格式发送你当前所在位置的描述:
* 一行包含一个由小写字母组成的字符串 $a$ ($1 \le |a| \le 20$) 和一个由大写字母组成的字符串 $s$ ($1 \le |s| \le 26$),分别表示你在该地点看到的文物名称以及通往外部的路径描述。没有两个地点会有相同的文物。字符串 $s$ 中的所有字母各不相同且为大写,顺序不固定。再次进入同一地点时,顺序可能会发生变化。
你的程序必须做出以下响应之一:
W c —— 你想沿着类型为 $c$ 的路径行走,其中 $c$ 是一个有效的路径类型字符。
R i —— 你确定该关卡与地图对应。整数 $i$ ($1 \le i \le n$) 应为你认为你当前所在的初始地图上的地点编号。
R ambiguous —— 该关卡与地图匹配,但匹配结果不唯一。
R no —— 该关卡与你的地图不对应。
在每次以 W 开头的有效响应后,grader 会给出你当前所在新地点的描述。你最多只能进行 $250\,000$ 次移动。在以 R 开头的响应后,游戏结束。如果你发送了无效响应,游戏结束,你的提交将被判为“Wrong Answer”。在你发送每条命令后,应刷新标准输出,以确保其被发送到游戏中。例如,在 C++ 中可以使用 fflush(stdout),在 Java 中使用 System.out.flush(),在 Python 中使用 sys.stdout.flush()。
样例
输入格式 1
3 2 D 2 B 3 2 P 3 D 1 2 P 2 B 1 fountain DB obelisk PD crystals PB fountain DB
输出格式 1
W D W P W B R 1
输入格式 2
3 2 D 2 B 3 2 P 3 D 1 2 P 2 B 1 obelisk PD fountain LD
输出格式 2
W D R no
输入格式 3
2 2 P 2 D 2 2 D 1 P 1 fountain PD obelisk PD fountain PD
输出格式 3
W P W D R ambiguous
说明
在上述交互示例中,左侧为 grader 的输出,右侧为提交程序的一种可能的正确输出。两侧的空行仅用于强调请求和回答的时间顺序。grader 永远不会输出任何空行。