Description

你正在调查一个洞穴。洞穴中有 $\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。注意：需确保程序及时退出以避免超时错误。若内存超限或程序运行时错误，将得到相应判果。

Input Format

见交互协议。

Output Format

见交互协议。

1
5 3
4 1

5 2

4 1

1 3

T 5

W

T 1

E 5

Hint

样例解释

（可以证明，实际的通道数为 4 或 5。该测试用例的两种可能图示如下图所示。）

可通过本地测试工具或平台进行调试。本地测试时需同时运行交互工具（如我们提供的交互运行器）。更多说明详见工具文件内的注释。

测试工具的使用说明已内嵌在注释中。建议添加自定义测试用例。请注意：该工具并非真实评测系统，实际行为可能存在差异。

限制条件

测试集 1（29 分，可见判果）

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{N} \leq 10^5$。
• $K = 8000$。
• 每个房间至少连接一条通道。

翻译由 DeepSeek V3 完成