做通信题做少了，以为回答询问不能记录全局变量，吐血了。

首先，对于不是第一步的情况，我们容易知道来时的那条边的颜色，记录一个变量 ， 每次 Move 完之后更新即可。进而可以知道所有出边的颜色。

首先观察部分分，容易发现这题需要我们解决两个问题： 是一般图 和 是树。我们分开来讲。

对于 Task1，我们不能走错任何一步，所以这要求我们必须把所有在 到当前点 最短路上的边标记为同一种颜色。我们考虑是树的时候怎么做，此时我们只能沿着父亲向上跳。把每条边 按照 染色，在回答询问时，因为我们周围只会出现两种颜色的边，我们就很容易得知自己的 是几，进而算出哪种颜色是指向父亲的那一个。

但 并不一定是树。此时我们考虑求出以 为根的 bfs 树（其实就是最短路树），那么所有非树边 都满足 ，容易用反证说明。对于一个点 ，我们希望从 出发向上的边与同层和向下的边区分开来，那么对于一条非树边 ，我们也将其染成 即可。

主要难点在于 的情况。

时，如果我们沿用黑白染色的想法，那么对于一个度数 的点，我们也容易区分出来哪个是父亲，找到出边中 的颜色 即可。所以，主要难点就在于处理树上的二度点。

容易发现，只要我们有一步走对了，剩下的步都能走对，因为此时对于一个二度点， 数组中只有一个位置有值，直接走过去肯定是对的。度数 的点和叶子也容易处理。

所以我们只要解决起点是二度点的情况。也就是说，我们出生在一条链上，要用 步找到正确的方向。这启示我们对链特殊染色，其它部分黑白染色。

还是考虑以一个串为这条链的周期来进行染色。爆搜可得染成 是可行的，因为 正串和反串的所有循环同构串都不相同。 所以我们只要在链上”看到“ 过至多 个元素，就能知道我们当前在向哪个方向走了。而这只需要最多 步，因为出生时就会看到两个元素，走完第一步就看到 个元素了。发现方向不对时再走 步回头路即可。

具体的染色过程可以用一个 dfs 来实现，在 dfs 时，记录如果是二度点，当前与链顶的距离 ，父亲边的颜色 。如果是二度点就根据 染色，否则染成与 相反的颜色即可。

Move 过程是个比较复杂的分类讨论。细节见代码：https://uoj.ac/submission/674026。