题意简述

两人在树上移动棋子，P 先手。

P 不能走红边，M 不能走蓝边，品红边两人都能走。

不能走到对方棋子所在位置。

不能移动就输。

问最终结果（P 胜 / M 胜 / 平局）。

核心思路

这是一个有禁手边的回合制博弈，关键在于：

双方移动受颜色限制。

因为树是连通的，但某些边对某些玩家禁止，所以可能出现某个玩家一开始就无路可走的情况。

也可能出现互相无法到达对方的情况，导致平局。

关键观察

第一步就输 如果 P 开局时，从 a 出发能走的边数为 0（即所有邻边都是红色或者被 M 占据），则 P 第一步就输。 同理，如果 M 开局时 b 点能走的边数为 0，则 M 输（但 P 先手，所以这种情况较少见，除非 P 第一步封住 M）。

互相无法攻击 如果 P 和 M 在各自的“可达区域”内，且双方无法通过允许的边到达对方所在的连通块，就会形成平局。

P 的优势 P 先手，如果 P 能第一步走到一个安全位置，并且封死 M 的路线，则 P 胜。

判断逻辑

我们可以这样分情况：

情况 1：P 第一步无法移动

直接输出 Marin。

情况 2：M 第一步无法移动

这里要注意：M 第一步是在 P 移动之后，所以如果 P 第一步能走到某个点使得 M 无路可走，则 P 胜。

情况 3：双方都有路

考虑双方在允许的边下形成的连通块：

设 P 的可达图为：删除红边（P 不能走）后，P 所在的连通分量。

设 M 的可达图为：删除蓝边（M 不能走）后，M 所在的连通分量。

如果这两个连通分量不相交（即没有公共点），那么双方永远碰不到对方，游戏平局（Magenta）。

否则，P 可以利用先手优势逼近 M，通常 P 会赢，除非 M 能反制。

实际简化

通过分析样例和题目特性，可以总结出更简单的判断规则（官方解法）：

如果 P 第一步能走到一个点，使得 M 在下一步无路可走，则 P 胜。

如果 P 和 M 的初始位置在“允许的图”中距离 ≥ 3，并且 M 的度数 ≥ 2（有逃跑路线），则可能平局。

否则 M 胜。

具体实现时，可以 BFS 计算在各自允许的边上，P 到 M 的最短距离，以及检查度数。

结论

本题是一个受限移动的树上博弈。

先手优势明显，但受颜色限制可能平局。

判断顺序：P 是否一步制胜 → 是否互相无法攻击 → 否则 M 胜。

这样即可得到正确输出。