마젠타

파울라와 마린이 나무 위에서 게임을 한다. 물론 진짜 나무는 아니다. 그건 위험한 일이겠지만, 노드가 $n$개이고 1부터 $n$까지 정수로 번호가 붙은, 간선이 $n-1$개인 연결 그래프가 완전히 안전하다고 누가 장담할 수 있을까.

게임이 시작되기 전에 파울라는 일부 간선을 파란색으로, 마린은 일부 간선을 빨간색으로 칠했다. 두 사람이 모두 칠한 간선은 최종 색이 마젠타가 된다. 모든 간선은 둘 중 적어도 한 명이 칠했다.

파울라의 말은 노드 $a$에서, 마린의 말은 노드 $b$에서 시작한다. 두 사람은 번갈아 움직이며 파울라가 먼저 둔다. 차례가 되면 플레이어는 자신의 말을 인접한 노드 중 상대의 말이 없는 노드로 옮겨야 한다. 파울라는 빨간 간선을 쓸 수 없고, 마린은 파란 간선을 쓸 수 없다. 두 사람 모두 마젠타 간선은 쓸 수 있다. 움직일 수 없는 플레이어가 진다.

두 사람은 모두 최적으로 둔다. 게임이 영원히 계속될 수 있다면 무승부로 선언한다. 게임의 결과를 구하라.

첫째 줄에 노드의 개수 $n$ ($2 \le n \le 100000$)이 주어진다.

둘째 줄에 파울라와 마린의 시작 노드 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어진다.

이후 $n-1$개의 줄에 간선이 주어진다. 각 줄은 "x y color" 형식이며, $x$와 $y$ ($1 \le x, y \le n$)는 간선의 양 끝점이고, color는 plava (크로아티아어로 파랑), crvena (크로아티아어로 빨강), magenta 중 하나이다.

파울라가 이기면 Paula, 마린이 이기면 Marin, 무승부이면 Magenta를 출력한다.