P12983 [GCJ 2022 Qualification] Twisty Little Passages

你正在调查一个洞穴。洞穴中有 $\mathbf{N}$ 个房间，某些房间之间通过双向的地下通道相连。每个房间至少连接一条通道。没有通道从一个房间指向自身，且任意两个房间之间最多只有一条通道。 当身处某个房间时，你可以识别当前所在的房间编号并查看它连接了多少条通道，但无法区分具体是哪条通道。你需要估算洞穴中存在的通道总数。你最多可以进行 $\mathbf{K}$ 次操作，每次操作可以是以下两种之一： * **魔法传送**：立即传送到任意一个你选择的房间。 * **随机行走**：从当前房间随机选择一条连接通道走过去（所有通道被选中的概率均等），到达该通道另一端的房间。 你从任意一个房间开始调查。通过最多 $\mathbf{K}$ 次操作，估算洞穴中房间之间的通道总数。 设 $E$ 是你的估算值，$P$ 是实际通道数量，当且仅当满足 $P \cdot 2/3 \leq E \leq P \cdot 4/3$ 时，你的答案被视为正确。要通过一个测试集，至少需要答对该测试集中 90% 的测试用例。 ### 交互协议 这是一个交互题。 初始时，你的程序需读取一个整数 $\mathbf{T}$，表示测试用例数量。接着处理 $\mathbf{T}$ 个测试用例。 对于每个测试用例，你的程序首先读取一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{K}$，分别表示洞穴中的房间数量和允许的最大操作次数。房间编号为 $1$ 到 $\mathbf{N}$。洞穴结构在测试用例开始时确定，不会在探索过程中改变。之后，程序需处理最多 $\mathbf{K} + 1$ 次交互。 第 $i$ 次交互开始时，你需要读取一行包含两个整数 $\mathbf{R}_i$ 和 $\mathbf{P}_i$，表示当前所在房间编号及其连接的通道数量。接着，输出以下三种指令之一： * 单个大写字母 $\mathbf{W}$：表示选择随机行走。 * 单个大写字母 $\mathbf{T}$ 和一个整数 $S$：表示传送到房间 $S$。 * 单个大写字母 $\mathbf{E}$ 和一个整数 $E$：表示结束探索并估算通道总数为 $E$。 在输出估算指令后，无论估算是否正确，裁判将立即开始下一个测试用例（如果存在）。如果没有更多测试用例，裁判将静默等待程序结束。 如果裁判在任何时刻收到非法格式的输入，或某测试用例的第 $(\mathbf{K} + 1)$ 次交互未输出估算指令，裁判将输出 $-1$ 并终止交互。若此时程序仍在等待输入，将因超时被判为 **Time Limit Exceeded**。注意：需确保程序及时退出以避免超时错误。若内存超限或程序运行时错误，将得到相应判果。

见交互协议。

见交互协议。

**样例解释** （可以证明，实际的通道数为 4 或 5。该测试用例的两种可能图示如下图所示。）  可通过本地测试工具或平台进行调试。本地测试时需同时运行交互工具（如我们提供的交互运行器）。更多说明详见工具文件内的注释。 测试工具的使用说明已内嵌在注释中。建议添加自定义测试用例。请注意：该工具**并非**真实评测系统，实际行为可能存在差异。 **限制条件** **测试集 1（29 分，可见判果）** - $1 \leq \mathbf{T} \leq 100$。 - $2 \leq \mathbf{N} \leq 10^5$。 - $K = 8000$。 - 每个房间至少连接一条通道。 翻译由 DeepSeek V3 完成