#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5;
int dist[maxn+2][2];
vector<pair<int,int> >adj[maxn+2];
int leng=0; int a,b;
void dfs(int cur,int c,int par){
for(auto x : adj[cur]){
if(x.first==par)continue;
if(x.first==b)leng=dist[cur][c]+1;
if(x.second==1-c)continue;
dist[x.first][c]=dist[cur][c]+1;
dfs(x.first,c,cur);
}
}
int siapa=0;
bool oke=false;
void solve(int cur,int par){
for(auto x : adj[cur]){
if(x.first==par || (dist[x.first][siapa]!=-1 && dist[x.first][siapa]<=dist[x.first][1-siapa]))continue;
if(x.second==siapa)continue;
if(dist[x.first][siapa]==-1 && dist[cur][siapa]==-1){
oke=true;
}
solve(x.first,cur);
}
}
signed main(){
memset(dist,-1,sizeof dist);
int n;
cin>>n;
cin>>a>>b;
bool blue=false;
bool red=false;
for(int q=1;q<n;q++){
int u,v;
cin>>u>>v;
string s;
cin>>s;
int col=0;
if(s[0]=='p'){
col=0;
}
else if(s[0]=='c'){
col=1;
}
else{
col=2;
}
adj[u].push_back({v,col});
adj[v].push_back({u,col});
if(col!=0 && (u==b || v==b))red=true;
if(col!=1 && ((u==a && v!=b) || (u!=b && v==a)))blue=true;
}
if(blue==false){
cout<<"Marin"<<endl;
return 0;
}
if(red==false){
cout<<"Paula"<<endl;
return 0;
}
dist[a][0]=dist[b][1]=0;
dfs(a,0,-1);
dfs(b,1,-1);
if(leng%2==1){
siapa=1;
}
else{
siapa=0;
}
if(siapa==0){
solve(b,-1);
if(oke){
cout<<"Magenta"<<endl;
}
else{
cout<<"Paula"<<endl;
}
}
else{
solve(a,-1);
if(oke){
cout<<"Magenta"<<endl;
}
else{
cout<<"Marin"<<endl;
}
}
}
