题目描述

给定 $n$ 个点，$n-1$ 条边的连通图，结点编号 $1\sim n$。

这 $n-1$ 条边被涂上了颜色，颜色为“蓝色、红色和紫色”三种之一。

小 A 和小 B 的棋子分别从结点 $a$ 和 $b$ 出发。两人轮流行走，小 A 先走。

小 A 的棋子只能沿着蓝色或紫色的边走，而小 B 的棋子只能沿着红色或紫色的边行走。任何时候都不能走都对方棋子所在的位置。如果有一方的棋子走不了了，则另一方获胜。

如果小 A 和小 B 每次都使用最优的走法，求最终的胜者。如果游戏无法决出胜负，则双方打平。

输入格式

第一行输入整数 $n$，表示结点的数量。

第二行输入整数 $a,b$，表示小 A 和小 B 棋子的初始位置。

接下来的 $n-1$ 行，每行输入两个整数 $u,v$ 和一个字符串 $s$。如果 $s$ 为 plava，则表示连接 $u,v$ 的边的颜色为蓝色；如果为 crvena，则表示颜色为红色；如果为 magenta 则为紫色。

输出格式

如果小 A 获胜，则输出 Paula。

如果小 B 获胜，则输出 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

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le a,b \le n$，$a \neq b$，$1 \le x,y \le n$。