P16411 [Algo Beat Contest 004 G] Go Playing with Reimu

Marisa 像往常一样来到博丽神社找 Reimu 玩耍。今天，她们决定玩一个与以往不同的树上博弈游戏。 Reimu 在纸上画了一棵由 $N$ 个节点组成的树，节点编号为 $1$ 到 $N$，其中 $1$ 号节点是这棵树的根。接着，她在根节点处放置了一枚棋子。 游戏由 Marisa 先手，两人轮流进行操作。在每个回合中，当前行动的玩家必须选择棋子所在节点的一个子节点，并将棋子移动过去。如果当前棋子所在的节点没有任何子节点（即为叶子节点），导致当前玩家无法进行移动，那么该玩家将输掉这场游戏。 两位少女不仅聪明绝顶，而且很快就看穿了初始状态下的必胜策略。为了增加游戏的趣味性，她们决定对这棵树进行 $Q$ 次修改。在第 $i$ 次修改中，她们会选中并删除一个节点 $x_i$。**题目保证每次要删除节点 $x_i$ 时，$x_i$ 尚未被删除，且一定是当前树上的一个叶子节点**。注意，操作是永久性的，即会永久影响树的形态。 请你帮忙判断：在游戏最开始时，以及在每一次修改之后，假设双方都采取最优策略，谁将拥有游戏的必胜策略？

第一行包含一个正整数 $N$，表示树最开始的节点总数。 接下来 $N-1$ 行，每行包含两个正整数 $U_i$ 和 $V_i$，表示节点 $U_i$ 和 $V_i$ 之间有一条边相连。 接下来一行包含一个正整数 $Q$，表示修改的次数。 最后一行包含 $Q$ 个正整数 $x_1, x_2, \dots, x_Q$，依次表示每次修改将要删除的节点编号。

输出共 $Q+1$ 行，每行一个字符串，依次表示最开始以及每次修改后，拥有必胜策略的玩家名字。 具体地，如果当前局面下先手（Marisa）有必胜策略，请输出 `Marisa`；如果后手（Reimu）有必胜策略，请输出 `Reimu`。

#### 【样例解释 #1】 - 初始状态：Marisa 作为先手，只需将棋子移动到 $3$ 号节点。由于 $3$ 号节点是叶子节点，轮到 Reimu 时她将无法进行任何移动，因此 Marisa 获胜。 - 第 $1$ 次修改后：由于 $3$ 号节点依然存在，Marisa 仍可采取上述策略直接走向 $3$ 号节点，Marisa 获胜。 - 第 $2$ 次修改后：整棵树变成了一条链 $1 \to 2 \to 4$。Marisa 第一步只能将棋子移动到 $2$ 号节点，随后 Reimu 只能将棋子移动到 $4$ 号节点。此时 Marisa 无法再进行移动，因此 Reimu 获胜。 - 第 $3$ 次修改后：整棵树变成了 $1 \to 2$。Marisa 第一步将棋子移动到 $2$ 号节点后，Reimu 无法移动，Marisa 获胜。 - 第 $4$ 次修改后：此时树中只剩下根节点 $1$。游戏开始时，棋子位于 $1$ 号节点，先手 Marisa 开局便无法进行任何移动，直接判负，Reimu 获胜。 #### 【数据范围】 - $3 \le Q < N \le 3 \times 10^5$。 - $1\le U_i,V_i\le N$。 - $1 \le x_i \le n$。 - 保证输入是一棵合法的树。 - 保证根节点一定不被删除。 - 保证每次要删除 $x_i$ 号点时，$x_i$ 号点未被删除，且是一个叶子结点。