Optimal Piece Movement in a Colored Tree

Given an undirected tree with \(n\) nodes and \(n-1\) edges, where the nodes are numbered \(1,2,\dots,n\), each edge is painted in a unique color chosen from blue, red, and magenta. Two players, Paula and Marin, place their pieces on nodes \(a\) and \(b\) respectively. They move alternately with Paula moving first.

Rules:

• On her turn, Paula can only traverse an edge if its color is either blue or magenta.
• On his turn, Marin can only traverse an edge if its color is either red or magenta.
• At every move, a player cannot move his/her piece to the node currently occupied by the opponent.
• If a player has no legal move on his/her turn, then that player loses and the opponent wins.
• If both players play optimally and the game can be continued indefinitely without forcing a win for either side, then the game is declared a draw.

Your task is to decide the outcome of the game if both players play optimally. The answer should be either Paula, Marin or Draw.

The moves are defined over the tree which is connected and acyclic although the state‐graph (where positions of both pieces and the turn is considered) may contain cycles due to the possibility of moving back and forth along the same edge.

Note: All formulas are given in \(\LaTeX\) format. For instance, the number of nodes is \(n\), and the nodes are numbered \(1,2,\dots,n\).

inputFormat

The first line contains three integers: \(n\), \(a\) and \(b\) where \(n\) is the number of nodes in the tree, and \(a\) and \(b\) are the starting positions of Paula and Marin respectively.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) and a string color indicating there is an edge between nodes \(u\) and \(v\) of that color. The color is one of blue, red or magenta.

outputFormat

Output a single line containing Paula if Paula wins, Marin if Marin wins, or Draw if the game cannot be decided.

sample

3 1 3
1 2 blue
2 3 red

Paula