题意

这是一个在未知图上进行探索并重构图结构的交互题。我们需要：

1. 探索整个图：从起点开始，通过移动和查询了解图的结构
2. 记录图信息：记录每个房间的连接关系和标识
3. 计算距离分布：计算所有点对之间的最短距离，统计每个距离值的点对数量

核心挑战

1. 房间不可区分：度数相同的房间看起来一样
2. 有限的颜色标记：只有 $X$ 种颜色可用于标记状态
3. 移动次数限制：最多 $1,500,000$ 次移动
4. 需要完全探索：必须找到所有房间和边

关键思路

1. 使用DFS进行系统探索

采用深度优先搜索的策略，利用颜色标记来记录访问状态：

• 未访问：颜色1（初始颜色）
• 正在访问：颜色2（当前DFS路径）
• 已完全探索：颜色3（该房间的所有邻居都已探索）

2. 房间标识方案

由于房间不可区分，我们需要建立自己的标识系统：

• 使用路径签名：从起点到房间的路径作为唯一标识
• 度数信息：结合房间的度数辅助识别
• 连接关系：通过已知的连接关系推断房间身份

3. 图重构策略

在探索过程中逐步构建图的邻接表。

4. 距离计算

在完全探索图结构后：

1. 构建邻接矩阵
2. 使用Floyd-Warshall或BFS计算所有点对最短路径
3. 统计距离分布：对每个距离 $d$，统计有多少点对的距离为 $d$

算法步骤

阶段1：图探索

1. 从起点房间1开始
2. 进行DFS遍历，用颜色标记访问状态
3. 记录每个房间的所有出边和对应的目标房间
4. 确保访问所有房间

阶段2：图重构

1. 基于探索数据建立完整的图结构
2. 解析房间的身份（处理同构房间）
3. 验证图的连通性

阶段3：距离计算

1. 计算所有点对之间的最短距离
2. 统计每个距离值的点对数量
3. 调用 Answer(D, A) 报告结果

优化技巧

1. 颜色使用优化（特别是X=3）

• 状态编码：用3种颜色编码探索状态
• 路径标记：在回溯时改变颜色以标记特定路径

2. 移动次数优化

• 避免重复访问：仔细记录已探索的边
• 智能回溯：只在必要时回溯
• 批量处理：一次移动完成多个信息收集

3. 房间识别

• 度数匹配：首先按度数分类房间
• 连接模式：通过邻居关系进一步区分
• 路径唯一性：确保从起点到每个房间有唯一路径标识

具体实现考虑

对于X=100的情况（子任务1）

有充足的颜色可以使用：

• 可以用不同颜色标记不同的DFS树分支
• 实现相对简单，颜色资源充足

对于X=3的情况（子任务2、3）

这是真正的挑战：

• 需要用3种颜色编码复杂的探索状态
• 可能需要更复杂的状态管理方案
• 移动次数需要更加优化

复杂度分析

• 时间复杂度：$O(N^3)$（Floyd-Warshall）或 $O(N \times M)$（多次BFS）
• 移动复杂度：$O(M)$ 但常数较大，因为需要回溯
• 空间复杂度：$O(N^2)$ 存储图结构和距离矩阵

关键实现细节

1. 回溯机制：正确使用 LastRoad() 实现回溯
2. 状态一致性：确保颜色标记与探索状态一致
3. 错误处理：处理意外的图结构
4. 边界情况：处理各种特殊的图结构（链、环、树等）