#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const int mxn=1e5+5;
int d[mxn],p[mxn],rp[mxn][2],sz[mxn][2];
vector<pair<int,int>>g[mxn];
void dfs(int i=1){
d[i]=d[p[i]]+1;
for(auto j:g[i])if(j.F!=p[i]){
p[j.F]=i;
dfs(j.F);
}
}
int fp(int i,bool t){
if(i==rp[i][t])return i;
return rp[i][t]=fp(rp[i][t],t);
}
void mrg(int a,int b,bool t){
a=fp(a,t),b=fp(b,t);
if(sz[a][t]<sz[b][t])swap(a,b);
sz[a][t]+=sz[b][t];
rp[b][t]=a;
}
void upd(int i,int pr,bool t){
for(auto j:g[i]){
if(j.F==pr||(j.S!=2&&j.S!=t))continue;
mrg(i,j.F,t);
upd(j.F,i,t);
}
}
int n,a,b;
bool chk(int x,bool t){
return fp(t?b:a,t)==fp(x,t);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>a>>b;
for(int i=1;i<=n;i++){
rp[i][0]=i;
sz[i][0]=1;
rp[i][1]=i;
sz[i][1]=1;
}
for(int i=1,u,v,t;i<n;i++){
string s;
cin>>u>>v>>s;
if(s[0]=='p')t=0;
else if(s[0]=='c')t=1;
else t=2;
g[u].push_back({v,t});
g[v].push_back({u,t});
}
upd(a,0,0);
upd(b,0,1);
bool flag=1;
for(int i=1;i<=n;i++){
if(chk(i,0)&&chk(i,1))flag=0;
}
if(flag)return cout<<"Magenta",0;
dfs();
bool t=(d[a]+d[b])%2==0;
int chsr=t?b:a;
int chsd=t?a:b;
int dis[n+1];
for(int i=1;i<=n;i++) d[i]=0, p[i]=0, dis[i]=-1;
dfs(chsr);
queue<int>q;
q.push(chsd);
dis[chsd]=0;
while(q.size()){
auto i=q.front();
q.pop();
for(auto[j,_]:g[i]){
if(!chk(j,!t)||dis[i]+2-t>=d[j])continue;
dis[j]=dis[i]+1;
q.push(j);
}
}
flag=0;
for(int i=1;i<=n;i++){
if(chk(i,t)||dis[i]==-1)continue;
for(auto[j,_]:g[i])if(dis[j]!=-1&&!chk(j,t))flag=1;
}
if(flag) cout << "Magenta";
else cout << (t ? "Marin" : "Paula");
}
