Description

Given a connected graph with $n$ nodes and $n-1$ edges, where the nodes are numbered $1,2,\cdots,n$. These $n-1$ edges are colored with different colors, including blue, red, and magenta.

Paula’s and Marin’s pieces start from nodes $a$ and $b$, respectively. They move alternately, with Paula moving first. Paula’s piece can move only along blue or magenta edges, and Marin’s piece can move only along red or magenta edges. However, at any time, neither player may move onto the node where the other player’s piece is located. If one player cannot make a move, then the other player wins.

Assuming both Paula and Marin always play optimally, determine who will win in the end. If the game cannot be decided, then it is a draw.

Input Format

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

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

In the next $n-1$ lines, each line contains two integers $x,y$ and a string $\text{color}$. If $\text{color}$ is $\texttt{plava}$, then the edge connecting $x,y$ is blue; if it is $\texttt{crvena}$, then it is red; if it is $\texttt{magenta}$, then it 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}$.

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

Hint

Sample 1 Explanation

Paula’s optimal move is to go to node $2$, and then Marin cannot move.

Sample 2 Explanation

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

Constraints

This problem uses bundled testdata.

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

Notes

The scoring for this problem follows the original COCI problem, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #5 T3 Magenta.

Translated by ChatGPT 5