题意回顾

• 给定 $N$ 个点 $M$ 条边的无向连通图
• 游戏过程：
  1. Ankica 猜测 Branko 在某个点 $a_i$，猜中则游戏结束
  2. 若未猜中，Branko 必须沿一条边移动到相邻点（不能停留）
• 判断 Ankica 是否有必胜策略（无论 Branko 初始位置和移动方式，都能在有限轮内抓住）
• 若有，输出最少轮数 $k$ 和猜测序列 $a_1, a_2, \dots, a_k$

关键结论

经过分析，本题有重要结论：

Ankica 有必胜策略当且仅当图是一棵树，且这棵树不是一条长度 ≥ 3 的路径。

证明思路

1. 如果有环 → 无必胜策略

• Branko 可以在环上无限躲避
• 例如三角形：Branko 总可以移动到与猜测不同的相邻点

2. 如果是链（路径）且长度 ≥ 3 → 无必胜策略

• 对于路径 $1-2-3-\dots-N$（$N \ge 3$）
• Branko 初始在 $2$：第一轮猜 $2$ 不中，Branko 到 $1$ 或 $3$
• 之后 Branko 总能在两端之间来回躲避

3. 如果是星形或有度数 ≥ 3 节点的树 → 有必胜策略

• 核心思路：利用"夹击"策略
• 找到树的一条直径，沿直径来回猜测可以保证抓住 Branko

算法步骤

步骤 1：判断图类型

1. 检查 $M = N-1$（树）且连通（题目已保证连通）
2. 如果 $M \ge N$，输出 NO（有环，无必胜策略）

步骤 2：如果是树，检查是否为链

• 计算每个点的度数
• 如果所有点度数 ≤ 2 且 $N \ge 3$，则是链，输出 NO
• 特殊情况：
  • $N = 1$：直接猜 1（但题目 $N \ge 2$）
  • $N = 2$：路径 1-2，有必胜策略

步骤 3：构造必胜策略（对于非链的树）

3.1 找直径

1. 从任意点 $u$ 出发 BFS 找到最远点 $v$
2. 从 $v$ 出发 BFS 找到最远点 $w$
3. $v$ 到 $w$ 的路径就是直径

设直径长度为 $L$（边数），节点序列为 $p_1, p_2, \dots, p_{L+1}$

3.2 构造猜测序列

最优策略长度 $k = 2L - 1$
序列：$p_1, p_2, \dots, p_L, p_{L-1}, \dots, p_1$

原理：沿直径来回扫描，Branko 在直径上会被"夹击"抓住，不在直径上也会被逼到直径上。

复杂度分析

• BFS 找直径：$O(N + M)$
• 构造序列：$O(N)$
• 总复杂度：$O(N + M)$，满足 $N \le 1000$

总结

本题的关键在于识别出只有非链的树才有必胜策略，并利用树的直径构造猜测序列。通过沿直径来回扫描的策略，可以确保在 $2L-2$ 轮内抓住 Branko，其中 $L$ 是直径的节点数。