P7123 [NEERC 2016] Indiana Jones and the Uniform Cave

这是一道 IO 交互题。

现在在一个洞穴里寻宝。这个洞穴有 $n$ 个房间。房间是不可区分的。每个房间都引出 $m$ 个单向道路，终点可以是自己也可以是其它房间。这些单向道路的入口均匀地分布在房间的墙壁上，且每条单向道路也是不可区分的。保证整个有向图是强连通的。你一开始在某一个房间，如果遍历了所有的边，就能找到宝藏。 每个房间有一个石子，这也是你区分房间和道路的唯一工具。一开始石子是在这个房间的某一个通道的入口前，并且是放在中央的。你每到一个房间，可以选择将石子移动到某个通道前，把它放在通道左边或者右边（不能是中间），然后再从某个通道走出去。你不可以把石子带出房间。你并没有携带过多的食物，所以如果你走了超过 $20000$ 条边，你就会因为食物耗尽而饿死。你要在规定步数之内找到宝藏。

共 $m$ 行，每行一个字符串，表示该房间内石头被放置的位置为某个通道的 $"center"$，$"left"$ 或 $"right"$。当第一次到达一个墓室时，石头处在中间(center)。

每行一个非负整数 $st$，表示将石头放在原所在位置顺时针方向第 $st$ 个通道入口；一个字符串，表示将它放在该通道入口 $dir$ 的位置（$"center"$，$"left"$ 或 $"right"$）；一个非负整数 $pa$ ，表示从石子的原来位置顺时针方向第 $pa$ 个通道走出。 通道顺时针从 $0$ 到 $m−1$ 编号。如果石头一开始是在中间（$center$），它会位于随机一个通道入口处。 每走一步，评测机会返回该房间的石头的位置或者 $"treasure"$ （如果您找到了宝藏且所有的通道都被走过时，就会反馈 $"treasure"$ ）。 **举个栗子**：`3 left 1` 表示将石头顺时针移动了 $3$ 个通道，并将其放置在该通道的左侧，然后走向最初石头所在位置的右侧的通道。 你最多可以进行 $20000$ 次操作。

Dr. Jones enters the example cave and sees that the stone in the first chamber is in the center. He marks the chamber by placing the stone to the left of some passage and takes it. He sees the chamber where the stone is to the left of the passage, so he is in the first chamber again. He moves the stone clockwise and takes the passage marked by it. This passage leads to the second chamber. He marks it by placing the stone to the right of some passage and takes another one. He is in the first chamber again, so he returns to the second chamber and takes the remaining passage. This passage leads to the treasure.