题目描述

译自 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。

3
1 3
3 2 magenta
2 1 magenta

Paula

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

Marin

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

Magenta

数据范围与提示

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