P7400 [COCI 2020/2021 #5] Magenta

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.

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.

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

#### 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**. |Subtask|Points|Constraints and Notes| | :----------: | :----------: | :----------: | |$1$|$30$|$2 \le n \le 100$| |$2$|$30$|All edges in the connected graph are magenta| |$3$|$50$|None| 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](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf) _T3 Magenta_.** Translated by ChatGPT 5