题目描述

译自 COCI 2020/2021 Contest #5 T3「Magenta」

有一棵 $n$ 个点的树，有两个玩家小 P 和小 M 将在上面做一个回合制游戏。

在游戏开始前，他们对树上的每一条边进行了染色，颜色有三种：蓝、红、品红。

初始时，两人都有一个棋子，小 P 的棋子在 $a$ 点，小 M 的棋子在 $b$ 点。

游戏规则如下：

• 小 P 先手。
• 当现在处于某个玩家的回合，他必须按如下规则移动自己的棋子：
  • 移动到自己的棋子所在的点所相邻的位置，且这个移动到的节点没有棋子。
  • 如果目前这名玩家是小 P，那他的棋子不能经过红色的边；如果目前这名玩家是小 M，那他的棋子不能经过蓝色的边。注意，品红色的边两者均能经过。
• 如果无法移动棋子，则这名玩家判负。

如果小 P 与小 M 都是绝顶聪明的，问这个游戏谁必胜，如果这个游戏无法在有限个回合内得到结束，判定为和局。

输入格式

第一行为一个整数 $n$。

第二行为两个整数 $a$ 和 $b$。

接下来 $n-1$ 行，一行两个整数 $x$ 和 $y$，和一个字符串 $S$。

• 若这个字符串为 plava，则这条由 $x$ 到 $y$ 的边为蓝色。
• 若这个字符串为 crvena，则这条由 $x$ 到 $y$ 的边为红色。
• 若这个字符串为 magenta，则这条由 $x$ 到 $y$ 的边为品红色。

输出格式

• 若小 P 必胜，输出 Paula。
• 若小 M 必胜，输出 Marin。
• 若平局，输出 Magenta。

样例 1

输入 3 1 3 3 2 magenta 2 1 magenta

text

输出 Paula

text

小 P 先移动到节点 $2$，那么小 M 将无路可走，判负。

样例 2

输入 5 3 5 1 2 magenta 1 3 magenta 2 4 plava 2 5 crvena

text

输出 Marin

text

如图，小 P 必须先移动到点 $1$，然后小 M 会移动到点 $2$，此时小 P 只能退回点 $3$，小 M 再移动到点 $1$，小 P 无路可走，判负。

样例 3

输入 5 1 4 2 1 plava 1 3 crvena 5 2 plava 4 1 magenta

text

输出 Magenta

text

数据范围与提示

对于所有子任务，有 $2 \le n \le 10^5$，$1 \le a,b,x,y \le n$，$a \ne b$，$S$ 只可能是 plava、crvena、magenta 中的一个。

子任务编号	特殊限制	分值
1	$n \le 100$	$30/110$
2	$S$ 为 magenta
3	无