Problem Description

Given a connected graph with $n$ nodes and $n-1$ edges, where the nodes are numbered from $1$ to $n$. These $n-1$ edges are painted in different colors, including blue, red, and magenta.

Paula and Marin start their pieces at nodes $a$ and $b$ respectively. They take turns moving, with Paula going first. Paula's piece can only move along blue or magenta edges, while Marin's piece can only move along red or magenta edges. However, neither piece can move to the position occupied by the other's piece at any time. If one player cannot move, the other player wins.

Determine the winner if both Paula and Marin play optimally. If the game ends in a draw, it is considered a draw.

Input Format

The first line contains an integer $n$, the number of nodes.

The second line contains two integers $a$ and $b$, the starting positions of Paula and Marin's pieces.

The next $n-1$ lines each contain two integers $x$ and $y$ and a string $\text{color}$. If $\text{color}$ is $\texttt{plava}$, the edge between $x$ and $y$ is blue; if it is $\texttt{crvena}$, the edge is red; if it is $\texttt{magenta}$, the edge is magenta.

Output Format

If Paula wins, output $\texttt{Paula}$.

If Marin wins, output $\texttt{Marin}$.

If the game is a draw, output $\texttt{Magenta}$.

Sample Input and Output

Sample Input #1

3
1 3
3 2 magenta
2 1 magenta

Sample Output #1

Paula

Sample Input #2

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

Sample Output #2

Marin

Sample Input #3

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

Sample Output #3

Magenta

Notes

Sample 1 Explanation

Paula's optimal move is to go to node $2$, leaving Marin unable to move.

Sample 2 Explanation

Paula will move to node $1$, and Marin will move to node $2$. Paula can then only move to node $3$, where Marin moves to node $1$. At this point, Paula cannot move, so Marin wins.

Data Constraints

This problem is group-tested.

For $100\%$ of the data, $2 \le n \le 10^5$, $1 \le a,b \le n$, $a \neq b$, $1 \le x,y \le n$.

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $110$.

Translated from COCI2020-2021 CONTEST #5 T3 Magenta.

见题面 Input 部分

见题面 Output 部分